The Electric Vehicle Routing and Overnight Charging Scheduling Problem on a Multigraph.

This article introduces the multigraph-based electric vehicle routing and overnight charging scheduling problem (mE-VRSPTW), which integrates routing a fleet of electric vehicles (EVs) to serve customers within time windows and scheduling their on-site overnight charging at a depot with limited charging infrastructure. The problem is modeled on a multigraph to capture multiple alternative travel paths between locations, reflecting trade-offs between travel distance/time and energy consumption. To solve the mE-VRSPTW, the authors develop a branch-price-and-cut (BPC) algorithm incorporating advanced techniques such as ng-path relaxation, subset-row inequalities, and a specialized backward labeling algorithm for the pricing problem. Computational experiments on benchmark instances with up to 50 customers demonstrate that the algorithm efficiently finds optimal solutions, with the multigraph representation yielding significantly better routing costs compared to classical single-graph models. The study also highlights the computational complexity introduced by the coupling of routing and charging scheduling, showing that relaxing charging capacity constraints substantially reduces solution times.