OASIcs.ATMOS.2020.7.pdf
- Filesize: 442 kB
- 16 pages
Document
Analyzing a Family of Formulations for Cyclic Crew Rostering
Authors
Twan Dollevoet 
,
-
Part of:
Volume:
20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-11-10
File
Document Identifiers
Author Details
Cite AsGet BibTex
Thomas Breugem, Twan Dollevoet, and Dennis Huisman. Analyzing a Family of Formulations for Cyclic Crew Rostering. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/OASIcs.ATMOS.2020.7
https://doi.org/10.4230/OASIcs.ATMOS.2020.7
Abstract
In this paper, we analyze a family of formulations for the Cyclic Crew Rostering Problem (CCRP), in which a cyclic roster has to be constructed for a group of employees. Each formulation in the family is based on a partition of the roster. Intuitively, finer partitions give rise to a formulation with fewer variables, but possibly more constraints. Coarser partitions lead to more variables, but might allow to incorporate many of the constraints implicitly. We derive analytical results regarding the relative strength of the different formulations, which can serve as a guideline for formulating a given problem instance. Furthermore, we propose a column generation approach, and use it to compare the strength of the formulations empirically. Both the theoretical and computational results demonstrate the importance of choosing a suitable formulation. In particular, for practical instances of Netherlands Railways, stronger lower bounds are obtained, and more than 90% of the roster constraints can be modeled implicitly.
Subject Classification
ACM Subject Classification
- Applied computing → Transportation
Keywords
- Crew Planning
- Roster Sequence
- Column Generation
- Railway Optimization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
E. Abbink, M. Fischetti, L. Kroon, G. Timmer, and M. Vromans. Reinventing crew scheduling at Netherlands Railways. Interfaces, 35(5):393-401, 2005.
-
R. Borndörfer, M. Reuther, T. Schlechte, C. Schulz, E. Swarat, and S. Weider. Duty rostering in public transport-facing preferences, fairness, and fatigue. In CASPT, 2015.
-
R. Borndörfer, C. Schulz, S. Seidl, and S. Weider. Integration of duty scheduling and rostering to increase driver satisfaction. Public Transport, 9(1):177-191, 2017.
-
T. Breugem, T. Dollevoet, and D. Huisman. Is equality always desirable? Analyzing the trade-off between fairness and attractiveness in crew rostering. Technical Report EI2017-30, Econometric Institute, 2017.
-
Thomas Breugem. Crew Planning at Netherlands Railways: Improving Fairness, Attractiveness, and Efficiency. PhD thesis, Erasmus University Rotterdam, January 2020.
-
A. Caprara, M. Fischetti, P. Toth, D. Vigo, and P. L. Guida. Algorithms for railway crew management. Mathematical Programming, 79(1-3):125-141, 1997.
-
A. T. Ernst, H. Jiang, M. Krishnamoorthy, H. Nott, and D. Sier. An integrated optimization model for train crew management. Annals of Operations Research, 108(1-4):211-224, 2001.
-
M. Grötschel, R. Borndörfer, and A. Löbel. Duty scheduling in public transit. In Mathematics-Key Technology for the Future, pages 653-674. Springer, 2003.
-
A. Hartog, D. Huisman, E. Abbink, and L. Kroon. Decision support for crew rostering at NS. Public Transport, 1(2):121-133, 2009.
-
S. Irnich and G. Desaulniers. Shortest path problems with resource constraints. In Column Generation, pages 33-65. Springer, 2005.
-
M. Mesquita, M. Moz, A. Paias, and M. Pato. A decompose-and-fix heuristic based on multi-commodity flow models for driver rostering with days-off pattern. European Journal of Operational Research, 245(2):423-437, 2015.
-
M. Sodhi and S. Norris. A flexible, fast, and optimal modeling approach applied to crew rostering at London Underground. Annals of Operations Research, 127(1-4):259-281, 2004.
-
L. Xie and L. Suhl. Cyclic and non-cyclic crew rostering problems in public bus transit. OR Spectrum, 37(1):99-136, 2015.