A flexible, fast, and optimal modeling approach applied to crew rostering at London Underground

A flexible, fast, and optimal modeling approach applied to crew rostering at London Underground

0.00 Avg rating0 Votes
Article ID: iaor20043486
Country: Netherlands
Volume: 127
Issue: 1
Start Page Number: 259
End Page Number: 281
Publication Date: Mar 2004
Journal: Annals of Operations Research
Authors: ,
Keywords: transportation: rail, graphs, programming: integer
Abstract:

We present a general modeling approach to crew rostering and its application to computer-assisted generation of rotation-based rosters (or rotas) at the London Underground. Our goals were flexibility, speed, and optimality, and our approach is unique in that it achieves all three. Flexibility was important because requirements at the Underground are evolving and because specialized approaches in the literature did not meet our flexibility-implied need to use standard solvers. We decompose crew rostering into stages that can each be solved with a standard commercial MILP solver. Using a 167 MHz Sun UltraSparc 1 and CPLEX 4.0 MILP solver, we obtained high-quality rosters in runtimes ranging from a few seconds to a few minutes within 2% of optimality. Input data were taken from different depots with crew sizes ranging from 30–150 drivers, i.e., with number of duties ranging from about 200–1000. Using an argument based on decomposition and aggregation, we prove the optimality of our approach for the overall crew rostering problem.

Reviews

Required fields are marked *. Your email address will not be published.