2024/06/30 by Margarita P. Castro, Castro, Margarita P., Merve Bodur +3 · 1 citation
Engineering · #Advanced Manufacturing and Logistics Optimization #Business #Computer science #Depot #Engineering #FOS: Mathematics #Geography #Operations management #Optimization and Control (math.OC) #Reliability (semiconductor) #Reliability engineering #Scheduling (production processes) #Service (business)
paper · pdf · doi:10.48550/arxiv.2407.00836
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2024/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (B&C) scheme to solve our CCP model. We present several cut-generation procedures that exploit the underlying problem structure and analyze the relationship between the obtained cut families. Additionally, we design a Lagrangian-based heuristic to handle large-scale instances reflective of real-world transit operations. Our approach partitions the set of trips, each subset leading to a subproblem that can be efficiently solved with our B&C algorithm, and then employs a procedure to combine the subproblem solutions to create a vehicle schedule that satisfies all the planning constraints of the MDVSP. 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.