Min-Max Electric Vehicle Routing Problem: Exact Model and Heuristic Approach

The growing adoption of electric vehicles (EVs) represents both a challenge and an opportunity for sustainable logistics. While EVs reduce greenhouse gas emissions, they introduce new operational complexities related to limited battery autonomy and the uneven distribution of charging stations. In this context, the electric vehicle routing problem plays a central role in transportation planning. This thesis addresses the Min-Max Electric Vehicle Routing Problem (MEVRP), a variant of the classical Vehicle Routing Problem (VRP) that focuses on minimizing the maximum distance traveled by a vehicle in the fleet. Unlike the traditional objective of minimizing total distance, the min-max criterion ensures a more balanced distribution of routes, reducing the risk of overloading certain vehicles and contributing to longer battery lifespans. The work is developed in two main phases. First, an exact mathematical model of the problem was formulated and implemented in Python using the PuLP library, solved through a branch-and-cut approach, and tested on small-scale instances. Then, to overcome the computational limits of the exact model, a heuristic algorithm in Python was developed, capable of solving larger instances within reasonable computation times. Experimental results show that the exact approach guarantees optimal solutions for small datasets, whereas the heuristic, while giving up absolute optimality, is able to provide high-quality solutions in significantly shorter times. The comparison between the two methods highlights the trade-offs between accuracy and scalability, offering valuable insights both from a methodological perspective and for practical applications. The thesis concludes with a discussion of the contributions achieved, the limitations of the work, and possible future extensions, including the introduction of time windows, multi-depot settings, and real-world applications in urban logistics