Route planning for electric vehicles using Adaptive Large Neighborhood Search

Abstract

The Electric Vehicle Routing Problem (EVRP) is an extension of the well-known Traveling Salesperson Problem (TSP) including battery limitations and multiple vehicles. Variants of this problem are formulated as mathematical optimization models consisting of objective functions and constraints, that may vary depending on the specific variant and the assumptions made. A method that can be used to solve this problem is the Adaptive Large Neighborhood Search (ALNS) which is a so-called meta-heuristic method where the solution is destroyed and repaired iteratively to improve the solution over time. ALNS is flexible and can be designed to fit various formulations of the EVRP. In this project the aim is to investigate how our design and its implementation performs on different variants of the problem. To evaluate the performance, ALNS was compared against a MILP solver by giving them the same initial solution and time limit. The evaluations were performed on data of different sizes as well as with different customer distributions. The bestfound objective value from an article using the same data instances and a problem formulation similar to ours was used as an additional reference. Our evaluation displays the efficiency of the ALNS, even if it was not possible to make any strong conclusions due to the quality of the reference solutions for the larger data instances. However, the algorithm and its implementation show great promise for further development, both for adapting it to other problem formulations and for improving the overall computational performance.