Column Generation with Dynamic Duty Selection for Railway Crew Rescheduling

Daniel Potthoff (), Dennis Huisman () and Guy Desaulniers ()
Additional contact information
Daniel Potthoff: Econometric Institute and ECOPT, Erasmus University Rotterdam, NL-3000 DR Rotterdam, The Netherlands, and Department of Logistics, Netherlands Railways, NL-3500 HA Utrecht, The Netherlands
Dennis Huisman: Econometric Institute and ECOPT, Erasmus University Rotterdam, NL-3000 DR Rotterdam, The Netherlands, and Department of Logistics, Netherlands Railways, NL-3500 HA Utrecht, The Netherlands
Guy Desaulniers: École Polytechnique de Montréal and GERAD, Department of Mathematics and Industrial Engineering, Montréal, Québec H3C 3AT, Canada

Transportation Science, 2010, vol. 44, issue 4, 493-505

Abstract: The Dutch railway network experiences about three large disruptions per day on average. In this paper, we present an algorithm to reschedule the crews when such a disruption occurs. The algorithm is based on column generation techniques combined with Lagrangian heuristics. Since the number of duties is very large in practical instances, we first define a core problem of tractable size. If some tasks remain uncovered in the solution of the core problem, we perform a neighborhood exploration to improve the solution. Computational experiments with real-life instances show that our method is capable of producing good solutions within a couple of minutes of computation time.

Keywords: railway planning; crew scheduling; column generation (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (33)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0322 (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:4:p:493-505

Access Statistics for this article

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