Solving large scale crew scheduling problems in practice
Document Type
Journal Article
Publication Date
2011
Subject Area
mode - rail, place - europe, organisation - workforce planning
Keywords
Crew scheduling, Large-scale optimization, Column generation
Abstract
This paper deals with large-scale crew scheduling problems arising at the main Dutch railway operator, Netherlands Railways (NS). NS operates about 30000 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.
Rights
Permission to publish the abstract has been given by Journal of Public Transport, copyright remains with them.
Recommended Citation
Abbink, E.J.W., Albino, L., Dollevoet, T., Huisman, D., Roussado, J., & Saldanha, R.L. (2011). Solving large scale crew scheduling problems in practice. Journal of Public Transport, Vol. 3, (2), pp. 149-164.
