A variable neighborhood search algorithm for a class of electric vehicle routing problems

This thesis presents a flexible General Variable Neighborhood Search based algorithm, named Flexi-VNS, to address three problems in electric vehicle routing: the classical Electric Vehicle Routing Problem (EVRP), the Battery Swap Station Location-routing Problem with Capacitated Electric Vehicles (BSS-EV-LRP), and the Electric Vehicle Routing Problem with Time Windows (E-VRPTW). The Flexi-VNS algorithm incorporates a Randomized Variable Neighborhood Descent (RVND) method as its local search procedure, featuring an intra-RVND mechanism applied exclusively to modified routes upon each solution update. We evaluated the performance of Flexi-VNS on benchmark instances of the problems, comparing its results with existing algorithms from the literature. Computational results demonstrated the efficiency of Flexi-VNS. It improved several best-known solutions and reduced the number of battery swap stations required, getting success rates of 90.38\%, 60\%, and 70.65\% for EVRP, BSS-EV-LRP, and E-VRPTW instances, respectively.