<  Back to the Polytechnique Montréal portal

Increasing schedule reliability in the multiple depot vehicle scheduling problem with stochastic travel time

Léa Ricard, Guy Desaulniers, Andrea Lodi and Louis-Martin Rousseau

Article (2024)

Open Acess document in PolyPublie and at official publisher
Open Access to the full text of this document
Published Version
Terms of Use: Creative Commons Attribution
Download (2MB)
Show abstract
Hide abstract


The multiple depot vehicle scheduling problem (MDVSP) is one of the most studied problems in public transport service planning. It consists of assigning buses to each timetabled trip while respecting vehicle availability at each depot. Although service quality, and especially reliability, is the core of most transport agencies, the MDVSP is more often than not solved solely in a cost-efficient way. This work introduces a data-driven model to the reliable MDVSP with stochastic travel time (R-MDVSP-STT). The reliability of a schedule is assessed and accounted for by propagating delays using the probability mass function of the travel time of each timetabled trip. We propose a heuristic branch-and-price algorithm to solve this problem and a labeling algorithm with a stochastic dominance criterion for the associated subproblems. The solutions obtained are compared based on three metrics — under normal and extraordinary circumstances. Computational results on real-life instances show that our method can efficiently find good trade-offs between operational costs and reliability, improving the reliability of the solutions with little cost increase.

Uncontrolled Keywords

vehicle scheduling; reliability; column generation; stochastic programming; delay propagation

Subjects: 1600 Industrial engineering > 1600 Industrial engineering
1600 Industrial engineering > 1603 Logistics
2700 Information technology > 2713 Algorithms
2950 Applied mathematics > 2950 Applied mathematics
Department: Department of Mathematics and Industrial Engineering
Funders: NSERC / CRSNG, GIRO Inc., Canada Excellence Research Chair in “Data Science for Real-Time Decision-Making”
Grant number: RDCPJ 520349-17, BESC D3-558645-2021
PolyPublie URL: https://publications.polymtl.ca/58211/
Journal Title: Omega-International Journal of Management Science (vol. 127)
Publisher: Elsevier
DOI: 10.1016/j.omega.2024.103100
Official URL: https://doi.org/10.1016/j.omega.2024.103100
Date Deposited: 13 May 2024 11:33
Last Modified: 14 May 2024 14:23
Cite in APA 7: Ricard, L., Desaulniers, G., Lodi, A., & Rousseau, L.-M. (2024). Increasing schedule reliability in the multiple depot vehicle scheduling problem with stochastic travel time. Omega-International Journal of Management Science, 127, 103100 (19 pages). https://doi.org/10.1016/j.omega.2024.103100


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only

View Item View Item