1066. Incorporating Service Reliability in Multi-depot Vehicle Scheduling: A Chance-Constrained Approach
Invited abstract in session HE-15: Multilevel and Stochastic Optimization , cluster Multilevel and Stochastic Optimization Methods.
Thursday, 16:15-17:45Room: FENP208
Authors (first author is the speaker)
1. | Margarita Castro
|
Pontificia Universidad Católica de Chile | |
2. | Merve Bodur
|
Mechanical and Industrial Engineering, University of Toronto | |
3. | Yongjia Song
|
Industrial Engineering, Clemson University |
Abstract
The multi-depot vehicle scheduling problem (MDVSP) is one of the main planning problems for transit agencies. Only a few works in the literature consider travel time uncertainty, however, and its impact on the service quality for the users. We present a novel stochastic variant of the MDVSP guaranteeing service reliability, measured by on-time performance (OTP) at route terminals. We propose a chance-constrained programming model for this problem and two different optimization approaches to solve it. The first one is an exact approach based on a branch-and-cut procedure. The second approach is a heuristic algorithm based on Lagrangian decomposition utilizing our exact methodology to solve each sub-problem. We test our procedure on randomly generated and real-world instances based on the city of Halifax, Canada. Our experimental evaluation shows the value of our stochastic variant to achieve OTP, compared to alternatives currently used by practitioners, as well as the computational advantages of our methodologies and their theoretical guarantees.
Keywords
- Stochastic Optimization
- Transportation
- Robust optimization
Status: accepted
Back to the list of papers