Solving Large Scale Crew Scheduling Problems in Practice

EJW Abbink; L Albino; Twan Dollevoet; Dennis Huisman; J Roussado; RL Saldanha

doi:10.1007/s12469-011-0045-x

Solving Large Scale Crew Scheduling Problems in Practice

EJW Abbink, L Albino, Twan Dollevoet, Dennis Huisman, J Roussado, RL Saldanha

Research output: Contribution to journal › Article › Academic › peer-review

30 Citations (Scopus)

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.

Original language	English
Pages (from-to)	149-164
Number of pages	16
Journal	Public Transport
Volume	3
Issue number	2
DOIs	https://doi.org/10.1007/s12469-011-0045-x
Publication status	Published - 2011

Research programs

EUR ESE 31
EUR ESE 32

Access to Document

10.1007/s12469-011-0045-x

Cite this

@article{00242a4b2194497590e451dd132f2b1f,

title = "Solving Large Scale Crew Scheduling Problems in Practice",

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.",

author = "EJW Abbink and L Albino and Twan Dollevoet and Dennis Huisman and J Roussado and RL Saldanha",

year = "2011",

doi = "10.1007/s12469-011-0045-x",

language = "English",

volume = "3",

pages = "149--164",

journal = "Public Transport",

issn = "1866-749X",

publisher = "Springer-Verlag",

number = "2",

}

TY - JOUR

T1 - Solving Large Scale Crew Scheduling Problems in Practice

AU - Abbink, EJW

AU - Albino, L

AU - Dollevoet, Twan

AU - Huisman, Dennis

AU - Roussado, J

AU - Saldanha, RL

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1007/s12469-011-0045-x

DO - 10.1007/s12469-011-0045-x

M3 - Article

SN - 1866-749X

VL - 3

SP - 149

EP - 164

JO - Public Transport

JF - Public Transport

IS - 2

ER -

Solving Large Scale Crew Scheduling Problems in Practice

Abstract

Research programs

Access to Document

Fingerprint

Cite this