Heuristics for the Electrical Vehicle Routing Problem

Sammanfattning

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension of the classical Vehicle Routing Problem (VRP) that includes additional energy and time constraints, increasing the complexity of the problem. Solutions found using exact methods are often limited to small instances, while larger instances require the use of heuristics for a solution within reasonable computational time. The purpose of this study is to investigate whether two different types of heuristics, Kernel Search (KS) and Simulated Annealing (SA), can be adapted to solve the EVRPTW. The results are evaluated based primarily on the number of vehicles and secondarily on the total distance needed. KS consistently outperformed SA across all tested benchmark instances, especially for larger problems where the difference in solution quality increased significantly. KS managed to find the optimal solution for almost all of the small instances, whereas SA found the optimal solution for only a fraction of the instances. When the energy constraints were removed, both KS and SA found optimal solutions more frequently, but KS still performed significantly better than SA.