A Column Generation Heuristic for Multi-depot Electric Bus Scheduling
(2025) CPAIOR 2025
Files
978-3-031-95976-9.pdf
Open Access - Adobe PDF
- 19.91 MB
Details
- Authors
- Abstract
- In public transit, the multi-depot electric vehicle scheduling problem (MDEVSP) involves assigning a fleet of electric buses to a set of timetabled trips while addressing constraints related to battery recharg- ing. A common approach to solving this problem leverages column gener- ation, wherein a master problem identifies a base solution, and subprob- lems generate additional schedules to enhance it. These subproblems are often modeled as shortest path problems on a graph, where nodes repre- sent trips and potential recharging opportunities. Prior works have used time-space networks with dynamic selection of recharging opportunities. However, this network type introduces practical limitations, such as the inability to enforce ad-hoc constraints on trip sequences. Recently, Ger- baux et al. (2025) proposed a machine-learning-based method to acceler- ate the resolution of the subproblems by heuristically reducing their size. While effective, this approach raises concerns in industrial applications, including data privacy for customers and compliance with legal regula- tions. In this context, we propose a novel approach to model the subprob- lems within a column-generation-based algorithm for the MDEVSP. Our contributions are as follows: (1) A new graph formulation that preselects recharging opportunities, offering greater flexibility in trip assignment and enabling the integration of ad-hoc constraints; (2) A constructive meta-heuristic, based on a greedy randomized adaptive search procedure, to reduce the subproblem size without relying on machine learning or historical data; (3) Additional pruning rules to further reduce the sub- problem size. Experimental results, conducted on hundreds of realistic instances derived from real bus lines in Montreal, show that our app- roach achieves comparable performance to the state-of-the-art method by Gerbaux et al. (2025), while avoiding the use of machine learning.
- Affiliations
Citations
Montanaro, Y. S., Jacquet, T., Cappart, Q., & Desaulniers, G. (2025). A Column Generation Heuristic for Multi-depot Electric Bus Scheduling. CPAIOR 2025, Part II, 15763, 103-118. https://doi.org/10.1007/978-3-031-95976-9_7 (Original work published 2025)