Document Open Access Logo

Analyzing a Family of Formulations for Cyclic Crew Rostering

Authors Thomas Breugem, Twan Dollevoet , Dennis Huisman

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.7.pdf
  • Filesize: 442 kB
  • 16 pages

Document Identifiers

Author Details

Thomas Breugem
  • Technology and Operations Management, INSEAD, Fontainebleau, France
Twan Dollevoet
  • Erasmus University Rotterdam, The Netherlands
Dennis Huisman
  • Erasmus University Rotterdam, The Netherlands
  • Netherlands Railways, The Netherlands

Cite As Get 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

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)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. E. Abbink, M. Fischetti, L. Kroon, G. Timmer, and M. Vromans. Reinventing crew scheduling at Netherlands Railways. Interfaces, 35(5):393-401, 2005. Google Scholar
  2. 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. Google Scholar
  3. 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. Google Scholar
  4. 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. Google Scholar
  5. Thomas Breugem. Crew Planning at Netherlands Railways: Improving Fairness, Attractiveness, and Efficiency. PhD thesis, Erasmus University Rotterdam, January 2020. Google Scholar
  6. 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. Google Scholar
  7. 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. Google Scholar
  8. 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. Google Scholar
  9. A. Hartog, D. Huisman, E. Abbink, and L. Kroon. Decision support for crew rostering at NS. Public Transport, 1(2):121-133, 2009. Google Scholar
  10. S. Irnich and G. Desaulniers. Shortest path problems with resource constraints. In Column Generation, pages 33-65. Springer, 2005. Google Scholar
  11. 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. Google Scholar
  12. 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. Google Scholar
  13. L. Xie and L. Suhl. Cyclic and non-cyclic crew rostering problems in public bus transit. OR Spectrum, 37(1):99-136, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact