Branch‐and‐Cut POPMUSIC for the Electric Vehicle Routing Problem With Time Windows

Advancements in computer hardware and commercial software have enabled the use of branch‐and‐cut (BC) methodologies to address medium‐scale vehicle routing problems (VRPs). Despite the introduction of efficient heuristics in the literature, tailoring these approaches to suit various VRP variants, such as the electric vehicle routing problem with time windows (EVRPTW), remains a difficult task. EVRPTW is an extension of the classic VRP with time windows in which internal combustion engine vehicles are replaced by electric vehicles. In this study, we develop a POPMUSIC matheuristic to solve the EVRPTW that relies solely on BC (termed BC‐POPMUSIC), and can be implemented using commercial optimisation software such as Gurobi. We introduce new battery infeasibility inequalities, along with capacity cuts, reachability cuts, ‐path cuts and polar cuts, and incorporate them into Gurobi to tighten the linear programming (LP) relaxation of the mixed integer linear program (MILP) model. Through extensive experiments, we show that this tightening can improve the quality of solutions. Since the EVRPTW requires visits to recharging stations when the battery is depleted, we propose an improvement heuristic to efficiently manage these recharging stops. We demonstrate the effectiveness of BC‐POPMUSIC on known benchmark instances of EVRPTW and compare it with state‐of‐the‐art exact solutions. Our result shows that the approach achieves comparable or better performance, especially on larger problems. In addition, we present new best known solutions for several benchmark instances.