A Variable Neighborhood Search-based Algorithm for the Electric Vehicle Routing Problem with Time Windows

This paper presents a flexible algorithm based on variable neighborhood search (VNS), called Flexi-VNS, for the electric vehicle routing problem with time windows (E-VRPTW). This problem is a variant of the classic Electric Vehicle Routing Problem, with the addition of the time window constraint. Flexi-VNS includes Randomized Variable Neighborhood Descent (RVND) as a local search procedure. RVND incorporates a new intra-RVND procedure, which is called every time a solution is modified, being applied only to the changed routes. We evaluated the performance of Flexi-VNS on E-VRPTW reference instances and compared it with the best algorithms in the literature. The results showed that the Flexi-VNS algorithm found all the best solutions in the literature on small-scale instances. Among the 56 large-scale instances, it improved seven and equaled the results in 22.