An adaptive VNS with randomized VND for the capacitated electric vehicle routing problem

Abstract

The emergence of electric vehicle (EV) technologies has given rise to a new variant of the vehicle routing problem known as the capacitated electric vehicle routing problem (CEVRP). In the CEVRP, not only the customer service order is considered but also the recharging schedules of EVs, which become crucial due to the limited number of charging stations and the restricted driving range of EVs. In this paper, we propose a novel adaptive variable neighborhood search combined with a randomized variable neighborhood descent (RVND) to solve the CEVRP. Our approach incorporates a dynamic shaking phase, where a set of problem‐specific route selection methods is employed to guide the search effectively. Additionally, the RVND component introduces a new route optimization operator that balances geographical proximity, charging station dependency, and battery‐level similarity to refine solutions during the local search phase. Extensive testing conducted on the CEVRP benchmark instances demonstrates the effectiveness of our approach. The algorithm achieves new best‐known solutions for 90% of the large instances, outperforming state‐of‐the‐art methods in terms of solution quality while maintaining competitive computational effort.