A Time-Space Network Approach for the Integrated Vehicle- and Crew-Scheduling Problem with Multiple Depots

Ingmar Steinzen (), Vitali Gintner (), Leena Suhl () and Natalia Kliewer ()
Additional contact information
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

Transportation Science, 2010, vol. 44, issue 3, 367-382

Abstract: 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.

Keywords: public transit; column generation; vehicle and crew scheduling (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (32)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1090.0304 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:44:y:2010:i:3:p:367-382

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().