A Comparative Study of RCSPP Algorithms for the Multi-Depot Electric Vehicle Scheduling Problem

The Multi-Depot Electric Vehicle Scheduling Problem (MDEVSP) is a complex combinatorial optimization problem crucial for sustainable logistics. Column generation is a powerful technique for solving the MDEVSP, where the pricing subproblem often manifests as a Resource Constrained Shortest Path Problem (RCSPP). The efficiency of the overall solution approach heavily depends on the RCSPP algorithm’s performance. This paper presents a comparative study of four RCSPP algorithms—Small Label First (SLF), A* (with a null heuristic), State-Space Relaxation (SSR-Inspired), and Advanced Pulse—for solving the MDEVSP subproblem. We evaluate these algorithms on a range of instances, considering both elementary and non-elementary path constraints. The results provide insights into the trade-offs between solution time and path cost, offering guidance for selecting appropriate RCSPP solvers in the context of MDEVSP with electric vehicles.