MODALRailLab
The vision of MODAL's RailLab is to increase the attractivity and competitiveness of railbound traffic by developing powerful novel mathematical optimization methods in order to support the planning processes of railways. The core problem is the efficient use of the rolling stock. The RailLab focusses on long distance passenger traffic and, in particular, the use of highspeed railcars. The following research topics are investigated: • fully dated vehicle rotation planning in order to roll out a given cyclic rotation plan onto a concrete calendar period including seasonal changes, holidays, construction sites etc (phase I) • robust vehicle rotation planning in order to enhance the stability of the plan w.r.t. disruptions (phase II) • service oriented vehicle rotation planning in order to use the "the right train on the right relation" (phase III).
RailLab is a cooperation of ZIB, DB Fernverkehr AG, and LBW Optimization GmbH to develop novel optimization algorithms for vehicle rotation planning in order to automate and improve planning processes in railway operations.
Germany has the largest railway network in Europe, containing roughly 33,500 km of tracks and 5,400 stations. Every day, 27,000 long and short distance passenger trains transporting 5.5 million passengers and 5,000 cargo run on this network. This system is highly relevant for society, industry, and the environment. Its maintenance and operation is expensive, infrastructure construction is extremely long termed. Putting the available network capacity to the best possible use is therefore of utmost importance for increasing the attractivity and competitiveness of railbound traffic not only in Germany.
Many planning processes in the railway industry are still operated in a manual way, the use of mathematical optimization technology is rare. The reason for this is the high complexity of railway operations respectively the lack of performance of the existing algorithms, which until recently thwarted all attempts to mathematical railway optimization.
RailLab is based on the results of two forerunner projects Vehicle Rotation Planning for Long Distance Passenger Railways (DBROTOR) and Multiday Cyclic Rotations for Trains (VSRAIL). These projects developed vehicle rotation optimizers ROTOR and VSRAIL, respectively, which allow, for the first time, to solve strategic vehicle rotation planning problems for largescale passenger railways such as the German ICE network. At present, rotation plans for a cyclic standard week can be optimized, aiming at the most efficient use of rolling stock, taking into account maintenance and other treatments of vehicles in facilities of limited capacities as well as operational regularity requirements on the similar use of vehicles on every day of the week. It is also possible to reoptimize a given rotation in order to adapt it to a changed scenario that results, e.g., from construction sites or seasonal changes of the timetable. Such a reoptimization is supposed to preserve the original schedule, as long as this is possible and not too expensive. In this way, scheduled maintenance services and deadhead trips do not have to be planned again, there is no need to apply again for resources like track capacity, and it is easier to adapt the duty schedule in the succeeding planning step.
Now that the principle feasibility of vehicle rotation planning is proved for a significant problem with a role model character for the entire planning chain, further and more complex applications in rolling stocking planning have come within reach. RailLab investigates the following planning problems:
 fully dated vehicle rotation planning (phase I)
 robust vehicle rotation planning (phase II)
 service oriented vehicle rotation planning (phase III).
This longterm program will be carried out in three phases of 45 years each. In addition to basic mathematical research, the projects include software development work packages of specification, collection and analysis of data, system analysis, modelling, algorithmic development, implementation, tests, system integration, dissemination, and the transfer of results to further applications.
Publications
2019 

Ralf Borndörfer, Boris Grimm, Markus Reuther, Thomas Schlechte  Optimization of handouts for rolling stock rotations  Journal of Rail Transport Planning & Management, pp. 18, 2019 (in press, preprint available as ZIBReport ZR1673) 
PDF (ZIBReport)
BibTeX DOI 
Ralf Borndörfer, Boris Grimm, Thomas Schlechte  Reoptimizing ICE Rotations after a Tunnel Breakdown near Rastatt  Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis  RailNorrköping 2019, 2019 (in press, preprint available as ZIBReport 1902) 
PDF (ZIBReport)
BibTeX 
Timo Berthold, Boris Grimm, Markus Reuther, Stanley Schade, Thomas Schlechte  Strategic Planning of Rolling Stock Rotations for Public Tenders  Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis  RailNorrköping 2019, pp. 185196, 2019 (in press) 
BibTeX

2018 

Isabel Beckenbach  A Hypergraph Network Simplex Algorithm  Operations Research Proceedings 2017, Vol.Operations Research Proceedings 2017, pp. 309316, 2018 (preprint available as ZIBReport 1736) 
PDF (ZIBReport)
BibTeX 
Ralf Borndörfer, Marika Karbstein, Christian Liebchen, Niels Lindner  A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable  18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018), pp. 16:116:15, Vol.65, OpenAccess Series in Informatics (OASIcs), 2018 (preprint available as ) 
BibTeX
DOI 
Brady Gilg, Torsten Klug, Rosemarie Martienssen, Joseph Paat, Thomas Schlechte, Christof Schulz, Senan Seymen, Alexander Tesch  Conflictfree railway track assignment at depots  Journal of Rail Transport Planning & Management, 2018 (epub ahead of print) 
PDF
BibTeX DOI 
Malte Renken, Amin Ahmadi, Ralf Borndörfer, Guvenc Sahin, Thomas Schlechte  DemandDriven Line Planning with Selfish Routing  Operations Research Proceedings 2017, pp. 687692, 2018 (preprint available as ZIBReport 1738) 
PDF (ZIBReport)
BibTeX DOI 
Ralf Borndörfer, Ricardo Euler, Marika Karbstein, Fabian Mett  Ein mathematisches Modell zur Beschreibung von Preissystemen im öV  ZIBReport 1847 
PDF
BibTeX URN 
Torsten Klug  Freight Train Routing  Handbook of Optimization in the Railway Industry, Springer International Publishing, pp. 7392, 2018, isbn: 9783319721521 
BibTeX
DOI 
Isabel Beckenbach, Ralf Borndörfer  Hall’s and Kőnig’s theorem in graphs and hypergraphs  Discrete Mathematics, 341(10), pp. 27532761, 2018 (preprint available as ZIBReport 1545) 
PDF (ZIBReport)
BibTeX DOI 
Erwin Abbink, Andreas Bärmann, Nikola Bešinovic, Markus Bohlin, Valentina Cacchiani, Gabrio Caimi, Stefano de Fabris, Twan Dollevoet, Frank Fischer, Armin Fügenschuh, Laura Galli, Rob M.P. Goverde, Ronny Hansmann, Henning Homfeld, Dennis Huisman, Marc Johann, Torsten Klug, Johanna Törnquist Krasemann, Leo Kroon, Leonardo Lamorgese, Frauke Liers, Carlo Mannino, Giorgio Medeossi, Dario Pacciarelli, Markus Reuther, Thomas Schlechte, Marie Schmidt, Anita Schöbel, Hanno Schülldorf, Anke Stieber, Sebastian Stiller, Paolo Toth, Uwe T. Zimmermann  Handbook of Optimization in the Railway Industry  Ralf Borndörfer, Torsten Klug, Leonardo Lamorgese, Carlo Mannino, Markus Reuther, Thomas Schlechte (Eds.), Springer Verlag, 2018, isbn: 9783319721521 
BibTeX
DOI 
Ralf Borndörfer, Ascan Egerer, Marika Karbstein, Ralf Messerschmidt, Marc Perez, Steven Pfisterer, Petra Strauß  Kombilösung: Optimierung des Liniennetzes in Karlsruhe  ZIBReport 1845 (Der Nahverkehr 12, p. 3338, 2019) 
PDF
BibTeX URN 
Ekaterina Oleynikova  Mathematical optimization of joint order batching and picker routing problems  Master's thesis, Freie Universität Berlin, Ralf Borndörfer (Advisor), 2018 
BibTeX

Jakob Witzig, Isabel Beckenbach, Leon Eifler, Konstantin Fackeldey, Ambros Gleixner, Andreas Grever, Marcus Weber  MixedInteger Programming for Cycle Detection in Nonreversible Markov Processes  Multiscale Modeling and Simulation, 16(1), pp. 248265, 2018 (preprint available as ) 
BibTeX
DOI 
Stephan Schwartz, Ralf Borndörfer, Leonardo Balestrieri  On Finding Subpaths With High Demand  Operations Research Proceedings 2017, pp. 355360, 2018 (preprint available as ) 
BibTeX

Markus Reuther, Thomas Schlechte  Optimization of Rolling Stock Rotations  Handbook of Optimization in the Railway Industry, Springer International Publishing, pp. 213241, 2018, isbn: 9783319721521 
BibTeX
DOI 
Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems  Ralf Borndörfer, Sabine Storandt (Eds.), Dagstuhl Publishing, Saarbrücken/Wadern, Germany, 2018, isbn: ISBN 9783959770965 
BibTeX
DOI 

Gabrio Caimi, Frank Fischer, Thomas Schlechte  Railway Track Allocation  Handbook of Optimization in the Railway Industry, Springer International Publishing, pp. 141160, 2018, isbn: 9783319721521 
BibTeX
DOI 
Ralf Borndörfer, Heide Hoppmann, Marika Karbstein, Niels Lindner  Separation of Cycle Inequalities in Periodic Timetabling  ZIBReport 1816 
PDF
BibTeX URN 
Adam Schienle  Solving the TimeDependent Shortest Path Problem Using SuperOptimal Wind  Operations Research Proceedings 2017, Natalia Kliewer, Jan Fabian Ehmke, Ralf Borndörfer (Eds.), 2018 
BibTeX

Stanley Schade, Thomas Schlechte, Jakob Witzig  Structurebased Decomposition for PatternDetection for Railway Timetables  Operations Research Proceedings 2017, pp. 715721, 2018 (preprint available as ZIBReport 1740) 
PDF (ZIBReport)
BibTeX DOI 
Ralf Borndörfer, Stephan Schwartz, Gerald Bartz  The Graph Segmentation Problem  INOC 2017 – 8th International Network Optimization Conference, pp. 3544, Vol.64, Electronic Notes in Discrete Mathematics, 2018 (preprint available as ) 
BibTeX

Boris Grimm, Ralf Borndörfer, Christof Schulz, Steffen Weider  The Rolling Stock Rotation Planning Problem under Revenue Considerations  Proceedings of the Rail Transport Demand Management Conference, 2018 (preprint available as ZIBReport 1901) 
PDF (ZIBReport)
BibTeX 
Isabel Beckenbach, Meike Hatzel, Sebastian Wiederrecht  The Tight Cut Decomposition of Matching Covered Uniformable Hypergraphs  ZIBReport 1861 
PDF
BibTeX URN 
Ralf Borndörfer, Matthias Breuer, Boris Grimm, Markus Reuther, Stanley Schade, Thomas Schlechte  Timetable Sparsification by Rolling Stock Rotation Optimization  Operations Research 2017, pp. 723728, 2018 (preprint available as ZIBReport 1763) 
PDF (ZIBReport)
BibTeX DOI 
2017 

Isabel Beckenbach, Britta Peis, Oliver Schaudt, Robert Scheidweiler  A Combinatorial Proof of a Königtype Theorem for Unimodular Hypergraphs  ZIBReport 1727 (under review) 
PDF
BibTeX URN 
Boris Grimm, Ralf Borndörfer, Markus Reuther, Stanley Schade, Thomas Schlechte  A Propagation Approach to Acyclic Rolling Stock Rotation Optimization  Proceedings of the IAROR conference RailLille, 2017 (preprint available as ZIBReport 1724) 
PDF (ZIBReport)
BibTeX 
Frank Fischer, Boris Grimm, Torsten Klug, Thomas Schlechte  A Reoptimization Approach for Train Dispatching  Operations Research Proceedings 2016, pp. 645651, 2017 (preprint available as ZIBReport 1649) 
PDF (ZIBReport)
BibTeX DOI 
ChengLung Wu, Stephen J. Maher  Airline scheduling and disruption management  L. Budd, S. Ison, eds., Air transportation management: an international perspective, Routledge: New York, pp. 151167, 2017, isbn: 9781472451064 
BibTeX

Brady Gilg, Torsten Klug, Rosemarie Martienssen, Joseph Paat, Thomas Schlechte, Christof Schulz, Sinan Seymen, Alexander Tesch  ConflictFree Railway Track Assignment at Depots  Proceedings of the IAROR conference RailLille, 2017 (preprint available as ZIBReport 1723) 
PDF (ZIBReport)
BibTeX 
Marco Blanco, Ralf Borndörfer, Nam Dung Hoang, Anton Kaier, Pedro Maristany de las Casas, Thomas Schlechte, Swen Schlobach  Cost Projection Methods for the Shortest Path Problem with Crossing Costs  17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), Gianlorenzo D'Angelo, Twan Dollevoet (Eds.), Vol.59, 2017 (preprint available as ) 
BibTeX

Stephan Schwartz, Thomas Schlechte, Elmar Swarat  Designing Inspector Rosters with Optimal Strategies  Operations Research Proceedings 2016, pp. 217223, 2017 (preprint available as ) 
BibTeX
DOI 
Ralf Borndörfer, Oytun Arslan, Ziena Elijazyfer, Hakan Güler, Malte Renken, Guvenc Sahin, Thomas Schlechte  Line Planning on Path Networks with Application to the Istanbul Metrobüs  Operations Research Proceedings 2016, pp. 235241, 2017 (preprint available as ) 
BibTeX
DOI 
Markus Reuther  Mathematical Optimization of Rolling Stock Rotations  Doctoral thesis, Technische Universität Berlin, Ralf Borndörfer, Martin Grötschel (Advisors), 2017 
BibTeX

Sebastian Schenker, Ingmar Vierhaus, Ralf Borndörfer, Armin Fügenschuh, Martin Skutella  Optimisation Methods in Sustainable Manufacturing  Sustainable Manufacturing, Rainer Stark, Günther Seliger, Jérémy Bonvoisin (Eds.), Springer International Publishing, pp. 239253, 2017, isbn: 9783319485140 
BibTeX
DOI 
Stanley Schade, Ralf Borndörfer, Matthias Breuer, Boris Grimm, Markus Reuther, Thomas Schlechte, Patrick Siebeneicher  Pattern Detection For LargeScale Railway Timetables  Proceedings of the IAROR conference RailLille, 2017 (preprint available as ZIBReport 1717) 
PDF (ZIBReport)
BibTeX 
Isabel Beckenbach, Robert Scheidweiler  Perfect fMatchings and fFactors in Hypergraphs  A Combinatorial Approach  Discrete Mathematics, 340(10), pp. 24992506, 2017 (preprint available as ZIBReport 1622) 
PDF (ZIBReport)
BibTeX DOI 
Ralf Borndörfer, Torsten Klug, Leonardo Lamorgese, Carlo Mannino, Markus Reuther, Thomas Schlechte  Recent success stories on integrated optimization of railway systems  Transportation Research Part C: Emerging Technologies, 74(1), pp. 196211, 2017 
BibTeX
DOI 
Frank Fischer, Thomas Schlechte  Strong Relaxations for the Train Timetabling Problem using Connected Configurations  17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), Gianlorenzo D'Angelo, Twan Dollevoet (Eds.), Vol.59, 2017, isbn: 9783959770422 (preprint available as ZIBReport 1746) 
PDF
PDF (ZIBReport) BibTeX DOI 
Ralf Borndörfer, Boris Grimm, Markus Reuther, Thomas Schlechte  Templatebased Reoptimization of Rolling Stock Rotations  Public Transport, pp. 119, 2017 
BibTeX
DOI 
Ralf Borndörfer, Heide Hoppmann, Marika Karbstein  Umsteigen ohne Warten  HEUREKA 2017, 2017 (epub ahead of print, preprint available as ) 
BibTeX

2016 

Isabel Beckenbach, Ralf Borndörfer  An Approximation Result for Matchings in Partitioned Hypergraphs  Operations Research Proceedings 2014, pp. 3136, 2016 (preprint available as ZIBReport 1430) 
PDF (ZIBReport)
BibTeX DOI 
Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Kerstin Waas, Steffen Weider  Integrated Optimization of Rolling Stock Rotations for Intercity Railways  Transportation Science, 50(3), pp. 863877, 2016 (preprint available as ZIBReport 1239) 
PDF
PDF (ZIBReport) BibTeX DOI 
Boris Grimm, Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Stanley Schade  Regularity patterns for rolling stock rotation optimization  8th International Conference on Applied Operational Research, Proceedings, pp. 2832, Vol.8, Lecture Notes in Management Science, 2016 
BibTeX

Marco Blanco, Ralf Borndörfer, Nam Dung Hoang, Anton Kaier, Adam Schienle, Thomas Schlechte, Swen Schlobach  Solving Time Dependent Shortest Path Problems on Airway Networks Using SuperOptimal Wind  16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), Goerigk Marc (Ed.), Vol.54, OpenAccess Series in Informatics (OASIcs), 2016 
BibTeX
DOI 
Ralf Borndörfer, Marika Karbstein, Julika Mehrgahrdt, Markus Reuther, Thomas Schlechte  The Cycle Embedding Problem  Operations Research Proceedings 2014, pp. 465472, 2016 (preprint available as ZIBReport 1437) 
PDF (ZIBReport)
BibTeX DOI 
Ralf Borndörfer, Armin Fügenschuh, Torsten Klug, Thilo Schang, Thomas Schlechte, Hanno Schülldorf  The Freight Train Routing Problem for Congested Railway Networks with Mixed Traffic  Transportation Science, 50(2), pp. 408423, 2016 (in press, preprint available as ) 
BibTeX
DOI 
Stanley Schade, Martin Strehler  The Maximum Flow Problem for Oriented Flows  16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), Marc Goerigk, Renato Werneck (Eds.), pp. 113, Vol.54, OpenAccess Series in Informatics (OASIcs), 2016, isbn: 9783959770217 (epub ahead of print) 
BibTeX
DOI URN 
Marco Blanco, Ralf Borndörfer, Nam Dung Hoang, Anton Kaier, Thomas Schlechte, Swen Schlobach  The Shortest Path Problem with Crossing Costs  ZIBReport 1670 
PDF
BibTeX URN 
2015 

Frank Fischer, Thomas Schlechte  Comparing two dual relaxations of large scale train timetabling problems  Proceedings of Conference on Advanced Systems in Public Transport 2015, 2015 (preprint available as ZIBReport 1543) 
PDF (ZIBReport)
BibTeX 
Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Christof Schulz, Elmar Swarat, Steffen Weider  Duty Rostering in Public Transport  Facing Preferences, Fairness, and Fatigue  Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015), 2015 (preprint available as ZIBReport 1544) 
PDF (ZIBReport)
BibTeX 
Torsten Klug, Konstanty JunoszaSzaniawski, Slawomir Kwasiborski, Armin Fügenschuh, Thomas Schlechte  Fastest, Average and Quantile Schedule  SOFSEM 2015: Theory and Practice of Computer Science, pp. 201216, 2015 (preprint available as ZIBReport 1449) 
PDF (ZIBReport)
BibTeX DOI 
Charles Brett, Rebecca Hoberg, Meritxell Pacheco, Kyle Smith, Ralf Borndörfer, Ricardo Euler, Gerwin Gamrath, Boris Grimm, Olga Heismann, Markus Reuther, Thomas Schlechte, Alexander Tesch  GRIPS 2014 RailLab  Towards robust rolling stock rotations  ZIBReport 1434 
PDF
BibTeX URN 
Ralf Borndörfer, Christof Schulz, Stephan Seidl, Steffen Weider  Integration of Duty Scheduling and Rostering to Increase Driver Satisfaction  ZIBReport 1550 
PDF
BibTeX URN 
Ralf Borndörfer, Leonardo Lamorgese, Torsten Klug, Carlo Mannino, Markus Reuther, Thomas Schlechte  Recent Success Stories on Optimization of Railway Systems  Proceedings of the IAROR conference RailTokyo, 2015 (preprint available as ZIBReport 1447) 
PDF (ZIBReport)
BibTeX 
Ralf Borndörfer, Markus Reuther  Regional Search for the Resource Constrained Assignment Problem  15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015), pp. 111129, Vol.48, OpenAccess Series in Informatics (OASIcs), 2015 
BibTeX
DOI 
Sepideh Ahmadi, Sascha F. Gritzbach, Kathryn LundNguyen, Devita McCulloughAmal  Rolling Stock Rotation Optimization in Days of Strike: An Automated Approach for Creating an Alternative Timetable  ZIBReport 1552 
PDF
BibTeX URN 
Ralf Borndörfer, Boris Grimm, Markus Reuther, Thomas Schlechte  Template based reoptimization of rolling stock rotations  Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015), 2015 
PDF
BibTeX URN 
Ralf Borndörfer, Olga Heismann  The hypergraph assignment problem  Discrete Optimization, Vol.15, pp. 1525, 2015 (preprint available as ) 
BibTeX
DOI 
2014 

Ralf Borndörfer, Markus Reuther, Thomas Schlechte  A CoarseToFine Approach to the Railway Rolling Stock Rotation Problem  14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, pp. 7991, Vol.42, OpenAccess Series in Informatics (OASIcs), 2014 (preprint available as ZIBReport 1426) 
PDF (ZIBReport)
BibTeX DOI 
Markus Reuther  Local Search for the Resource Constrained Assignment Problem  14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, pp. 6278, Vol.42, OpenAccess Series in Informatics (OASIcs), 2014 
BibTeX
DOI 
Ralf Borndörfer, Julika Mehrgardt, Markus Reuther, Thomas Schlechte, Kerstin Waas  ReOptimization of Rolling Stock Rotations  pp. 4955, Operations Research Proceedings 2013, 2014 (preprint available as ZIBReport 1360) 
PDF (ZIBReport)
BibTeX DOI 
2013 

Ralf Borndörfer, Andreas Löbel, Markus Reuther, Thomas Schlechte, Steffen Weider  Rapid Branching  Public Transport, 5(1), pp. 323, 2013 (preprint available as ) 
BibTeX

2012 

Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Steffen Weider  Vehicle Rotation Planning for Intercity Railways  Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12), 2012 (preprint available as ZIBReport 1211) 
PDF (ZIBReport)
BibTeX 
2011 

Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Steffen Weider  A Hypergraph Model for Railway Vehicle Rotation Planning  11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, OpenAccess Series in Informatics (OASIcs)(20), pp. 146155, 2011 (preprint available as ZIBReport 1136) 
PDF (ZIBReport)
BibTeX DOI 