This paper deals with large-scale crew scheduling problems arising at the Dutch railway operator, Netherlands Railways (NS). NS operates about 30,000 trains a week. All these trains need a driver and a certain number of guards. Some labor rules restrict the duties of a certain crew base over the complete week. Therefore splitting the problem in several subproblems per day leads to suboptimal solutions. In this paper, we present an algorithm, called LUCIA, which can solve such huge instances without splitting. This algorithm combines Lagrangian heuristics, column generation and fixing techniques. We compare the results with existing practice. The results show that the new method significantly improves the solution.

Additional Metadata
Keywords column generation, crew scheduling, large-scale optimization
Publisher Erasmus School of Economics
Persistent URL
Series Econometric Institute Research Papers
Journal Report / Econometric Institute, Erasmus University Rotterdam
Abbink, E.J.W, Albino, L, Dollevoet, T.A.B, Huisman, D, Roussado, J, & Saldanha, R.L. (2010). Solving Large Scale Crew Scheduling Problems in Practice (No. EI 2010-63). Report / Econometric Institute, Erasmus University Rotterdam (pp. 1–19). Erasmus School of Economics. Retrieved from