A Time-Space Network Approach for the Integrated Vehicle- and Crew-Scheduling Problem with Multiple Depots
-
- Ingmar Steinzen
- Decision Support and OR Lab and International Graduate School of Dynamic Intelligent Systems, University of Paderborn, D-33100 Paderborn, Germany
-
- Vitali Gintner
- Decision Support and OR Lab and International Graduate School of Dynamic Intelligent Systems, University of Paderborn, D-33100 Paderborn, Germany
-
- Leena Suhl
- Decision Support and OR Lab and International Graduate School of Dynamic Intelligent Systems, University of Paderborn, D-33100 Paderborn, Germany
-
- Natalia Kliewer
- Freie Universität Berlin, 14195 Berlin, Germany
説明
<jats:p> This paper discusses the integrated vehicle- and crew-scheduling problem in public transit with multiple depots. It is well known that the integration of both planning steps discloses additional flexibility that can lead to gains in efficiency, compared to sequential planning. We present a new modeling approach that is based on a time-space network representation of the underlying vehicle-scheduling problem. The integrated problem is solved with column generation in combination with Lagrangian relaxation. The column generation subproblem is modeled as a resource-constrained shortest-path problem based on a novel time-space network formulation. Feasible solutions are generated by a heuristic branch-and-price method that involves fixing service trips to depots. Numerical results show that our approach outperforms other methods from the literature for well-known test problems. </jats:p>
収録刊行物
-
- Transportation Science
-
Transportation Science 44 (3), 367-382, 2010-08
Institute for Operations Research and the Management Sciences (INFORMS)
