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.

Additional Metadata
Publisher Erasmus School of Economics (ESE)
Persistent URL hdl.handle.net/1765/14423
Citation
Potthoff, D., Huisman, D., & Desaulniers, G.. (2008). Column generation with dynamic duty selection for railway crew rescheduling (No. EI 2008-28). Report / Econometric Institute, Erasmus University Rotterdam (pp. 1–25). Erasmus School of Economics (ESE). Retrieved from http://hdl.handle.net/1765/14423