Abstract: The multi-depot vehicle scheduling problem (MDVSP) is a critical planning challenge for transit agencies. We introduce a novel approach to MDVSP by incorporating service reliability through chance-constrained programming (CCP), targeting the pivotal issue of travel time uncertainty and its impact on transit service quality. Our model guarantees service reliability measured by on-time performance (OTP), a primary metric for transit agencies, and fairness across different service areas. We propose an exact branch-and-cut scheme to solve our CCP model. We present several cut-generation procedures that exploit the underlying problem structure. Additionally, we design a Lagrangian-based heuristic to handle large-scale instances reflective of real-world transit operations. Our empirical evaluation demonstrates the superiority of our stochastic variant in achieving cost-effective schedules with reliable OTP guarantees compared to alternatives commonly used by practitioners, as well as the computational benefits of our methodologies.

About the Speaker: Dr. Merve Bodur is an Associate Professor in the School of Mathematics at the University of Edinburgh. She obtained her Ph.D. from the University of Wisconsin-Madison, her B.S. in Industrial Engineering and her B.A. in Mathematics from Bogazici University, Turkey. Her main research area is optimization under uncertainty, primarily for discrete optimization problems, with applications in a variety of areas such as scheduling, transportation, healthcare, telecommunications, and power systems. She serves on the editorial boards of Operations Research Letters, Omega, and INFORMS. She is currently the Vice Chair/Chair-Elect of the INFORMS Computing Society, serves on the Committee on Stochastic Programming, and is a former Vice Chair of the INFORMS Optimization Society.

Click here to watch