Railway Crew Rostering: Tailored Optimization Solutions in Daily Use in Berlin

Abstract

We are presenting a crew planning optimization project for the train drivers of an urban rail transportation company. The core is about crew rostering, i.e., defining over a certain period of time (e.g., one year) for each train driver sequences of working days and rest days, and also specifying whether working days shall contain either some early, late, or night shift. But the project was not only about solving just one classical crew rostering problem. Rather, during the last three years, the entire process of crew rostering had been investigated. Apart from having modeled, solved, and implemented two different variants of crew rostering—a cyclic and an acyclic one—there have been designed and used three further optimization models for less typical surrounding sub-processes, as well as a simple crew assignment model. During the design and implementation process of these six optimization models, the focus had been put on their annual and daily usability, respectively. In particular, many practical requirements had been collected and implemented in rather straightforward ways. The result is a family of mathematical optimization models, whose results cover the valid annual crew rosters from the year 2024 on, as well as the daily assignment of specific duties to train drivers from May 2025 on at S-Bahn Berlin GmbH.

Keywords

Railway optimization / Crew planning / Crew rostering / Crew assignment / Integer linear programming

References

[1] Lu K, Zhang L, Li S, Huang Y, Ding X, Hao J, Huang S, Li X, Lu F, Zhang H. Urban rail transit in china: Progress report and analysis (2015–2023). Urban Rail Transit, 2025, 11: 1-27.

[2] Borndörfer R, Grötschel M, Jäger U. Grötschel M, Lucas K, Mehrmann V. Planning Problems in Public Transit, 2010. Heidelberg, Springer, Berlin: 95-121.

[3] Farina F (2018) Optimization of operations in public transportation. PhD thesis, DTU, Lyngby, Denmark

[4] Kroon LG, Huisman D, Abbink EJW, Fioole P, Fischetti M, Maróti G, Schrijver A, Steenbeek A, Ybema R. The new Dutch timetable: the OR revolution. Interfaces, 2009, 39(1): 6-17.

[5] Lu K, Han B, Zhou X. Smart urban transit systems: from integrated framework to interdisciplinary perspective. Urban Rail Transit, 2018, 4: 49-67.

[6] Freling R, Wagelmans APM, Paixão JMP. Wilson NHM. An overview of models and techniques for integrating vehicle and crew scheduling. Computer-aided transit scheduling, 1999. Berlin, Heidelberg, Springer: 441-460.

[7] Van den Bergh J, Beliën J, Bruecker PD, Demeulemeester E, Boeck LD. Personnel scheduling: a literature review. Eur J Oper Res, 2013, 226(3): 367-385.

[8] Lavoie S, Minoux M, Odier E. A new approach for crew pairing problems by column generation with an application to air transportation. Eur J Oper Res, 1988, 35(1): 45-58.

[9] Barnhart C, Belobaba P, Odoni AR. Applications of operations research in the air transport industry. Transp Sci, 2003, 37(4): 368-391.

[10] Emden-Weinert T, Proksch M. Best practice simulated annealing for the airline crew scheduling problem. J Heuristics, 1999, 5(4): 419-436.

[11] Kohl N, Karisch SE. Airline crew rostering: problem types, modeling, and optimization. Ann Oper Res, 2004, 127(1–4): 223-257.

[12] Deveci M, Demirel NÇ. A survey of the literature on airline crew scheduling. Eng Appl Artif Intell, 2018, 74: 54-69.

[13] Breugem T, Dollevoet T, Huisman D. Is equality always desirable? Analyzing the trade-off between fairness and attractiveness in crew rostering. Manag Sci, 2022, 68(4): 2619-2641.

[14] Kohl N (2003) Solving the world’s largest crew scheduling problem. ORbit Xtra

[15] Abbink EJW, Fischetti M, Kroon LG, Timmer G, Vromans MJCM. Reinventing crew scheduling at Netherlands railways. Interfaces, 2005, 35(5): 393-401.

[16] Heil J, Hoffmann K, Buscher U. Railway crew scheduling: models, methods and applications. Eur J Oper Res, 2020, 283(2): 405-425.

[17] Zhao C, Chen J, Zhang X, Cui Z. Solution of multi-crew depots railway crew scheduling problems: the Chinese high-speed railway case. Sustainability, 2022.

[18] Ernst A, Jiang H, Krishnamoorthy M, Nott H, Sier D. Voß S, Daduna JR. Rail crew scheduling and rostering optimization algorithms, 2001. Heidelberg, Springer, Berlin: 53-71.

[19] Sodhi MS, Norris S. A flexible, fast, and optimal modeling approach applied to crew rostering at London underground. Ann Oper Res, 2004, 127(1–4): 259-281.

[20] Hartog A, Huisman D, Abbink EJW, Kroon LG. Decision support for crew rostering at NS. Public Transp, 2009, 1(2): 121-133.

[21] Xie L, Suhl L. Cyclic and non-cyclic crew rostering problems in public bus transit. OR Spectr, 2015, 37(1): 99-136.

[22] Breugem T, Schlechte T, Schulz C, Borndörfer R. A three-phase heuristic for the fairness-oriented crew rostering problem. Comput Oper Res, 2023, 154. ArticleID: 106186

[23] van Rossum B, Dollevoet T, Huisman D. Railway crew planning with fairness over time. Eur J Oper Res, 2024, 318(1): 55-70.

[24] Heer T (2024) Optimierung zyklischer Wochenschemata mit Simulated Annealing. In: Heureka 2024 Optimierung in Transport und Verkehr–Tagungsband. FGSV Verlag, Köln (in German)

[25] Li JM, Nie L (2014) Crew planning optimization model of high-speed railway. In: Li H, Li Q, Xu Q (ed) Sustainable development of industry and economy. Advanced materials research, Vol 869. Trans Tech Publications Ltd, Bäch, Switzerland, pp 298–304. https://doi.org/10.4028/www.scientific.net/AMR.869-870.298

[26] Wang Y, Guo Q (2023) Optimization method of railway crew planning based on column generation and tabu search. In: 2023 IEEE 3rd international conference on electronic technology, communication and information (ICETCI), pp 338–342. https://doi.org/10.1109/ICETCI57876.2023.10176964

[27] Borndörfer R, Schulz C, Seidl S, Weider S (2015) Integration of duty scheduling and rostering to increase driver satisfaction. Technical Report 15-50, Zuse Institute Berlin (ZIB), Germany

[28] Zhou J, Xu X, Long J, Ding J. Integrated optimization approach to metro crew scheduling and rostering. Transport Res Part C Emerg Technol, 2021, 123. ArticleID: 102975

[29] Feng T, Lusby RM, Zhang Y, Tao S, Zhang B, Peng Q. A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems. Transport Res Part B Methodol, 2024, 183. ArticleID: 102941

[30] Zeghal FM, Minoux M. Modeling and solving a crew assignment problem in air transportation. Eur J Oper Res, 2006, 175(1): 187-209.

[31] Liebchen C, Schülldorf H. A collection of aspects why optimization projects for railway companies could risk not to succeed—a multi-perspective approach. J Rail Transp Plan Manag, 2019.

[32] Liebchen C, Türk C, Vornhusen B, Brose J, Göb T, Schaar F. Individuelle Optimierungslösungen für die Personaleinsatzplanung eines Verkehrsunternehmens. Der Nahverkehr, 2024, 42(3): 63-68. in German.

[33] Liebchen C, Türk C, Vornhusen B (2025) An integer programming model to assign train drivers to good positions in basic turni. In: Glomb L (ed) Operations research proceedings 2024. Springer, Cham, pp 272–278. https://doi.org/10.1007/978-3-031-92575-7_38

[34] Rählmann C, Wagener F, Thonemann UW. Robust tactical crew scheduling under uncertain demand. Transp Sci, 2021, 55(6): 1392-1410.

[35] Bundestag D (2024) Arbeitszeitgesetz - ArbZG. Bundesgesetzblatt (in German). https://www.gesetze-im-internet.de/arbzg/

[36] Schnieder L (2018) Betriebsplanung im Öffentlichen Verkehr. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-57318-1

[37] Eisenbahn- und Verkehrsgewerkschaft (EVG) und Arbeitgeber- und Wirtschaftsverband der Mobilitäts- und Verkehrsdienstleister e. V. (AGV MOVE) (2023) Funktionsgruppenspezifischer Tarifvertrag für Tätigkeiten der Funktionsgruppe 4 – Lokfahrdienst - (in German)

[38] Breugem T, Schlechte T, Schulz C, Borndörfer R. A three-phase heuristic for the fairness-oriented crew rostering problem. Comput Oper Res, 2023, 154. ArticleID: 106186

[39] Gewerkschaft Deutscher Lokomotivführer (GDL) und Arbeitgeber- und Wirtschaftsverband der Mobilitäts- und Verkehrsdienstleister e. V. (AGV MOVE) (2025) Bundes-Rahmentarifvertrag für das Zugpersonal der Schienenbahnen des Personen- und Güterverkehrs in der Bundesrepublik Deutschland. (in German)

[40] IBM corporation (2025) IBM ILOG CPLEX Optimization Studio. www.ibm.com. Version 22.1.2

RIGHTS & PERMISSIONS

The Author(s)