@phdthesis{Reuther, author = {Reuther, Markus}, title = {Mathematical Optimization of Rolling Stock Rotations}, abstract = {We show how to optimize rolling stock rotations that are required for the operation of a passenger timetable. The underlying mathematical ptimization problem is called rolling stock rotation problem (RSRP) and the leitmotiv of the thesis is RotOR, i.e., a highly integrated optimization algorithm for the RSRP. RotOR is used by DB Fernverkehr AG (DBF) in order to optimize intercity express (ICE) rotations for the European high-speed network. In this application, RSRPs have to be solved which (A) require many different aspects to be simultaneously considered, (B) are typically of large scale, and (C) include constraints that have a difficult combinatorial structure. This thesis suggests answers to these issues via the following concepts. (A) The main model, which RotOR uses, relies on a hypergraph. The hypergraph provides an easy way to model manifold industrial railway requirements in great detail. This includes well known vehicle composition requirements as well as relatively unexplored regularity stipulations. At the same time, the hypergraph directly leads to a mixed-integer programming (MIP) model for the RSRP. (B) The main algorithmic ingredient to solve industrial instances of the RSRP is a coarse-to-fine (C2F) column generation procedure. In this approach, the hypergraph is layered into coarse and fine layers that distinguish different levels of detail of the RSRP. The coarse layers are algorithmically utilized while pricing fine columns until proven optimality. Initially, the C2F approach is presented in terms of pure linear programming in order to provide an interface for other applications. (C) Rolling stock rotations have to comply to resource constraints in order to ensure, e.g., enough maintenance inspections along the rotations. These constraints are computationally hard, but are well known in the literature on the vehicle routing problem (VRP). We define an interface problem in order to bridge between the RSRP and the VRP and derive a straightforward algorithmic concept, namely regional search (RS), from their common features and, moreover, differences. Our RS algorithms show promising results for classical VRPs and RSRPs. In the first part of the thesis we present these concepts, which encompass its main mathematical contribution. The second part explains all modeling and solving components of RotOR that turn out to be essential in its industrial application. The thesis concludes with a solution to a complex re-optimization RSRP that RotOR has computed successfully for DBF. In this application all ICE vehicles of the ICE-W fleets of DBF had to be redirected past a construction site on a high-speed line in the heart of Germany.}, language = {en} } @article{BorndoerferGrimmReutheretal., author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Reuther, Markus and Schlechte, Thomas}, title = {Optimization of handouts for rolling stock rotations}, series = {Journal of Rail Transport Planning \& Management}, journal = {Journal of Rail Transport Planning \& Management}, number = {10}, doi = {10.1016/j.jrtpm.2019.02.001}, pages = {1 -- 8}, abstract = {A railway operator creates (rolling stock) rotations in order to have a precise master plan for the operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply traverses a set of operational days while covering trips of the timetable. As it is well known, the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging and still a topical research subject. Nevertheless, we study a completely different but strongly related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In our industrial application at DB Fernverkehr AG, the handout is exactly as important as the rotation itself. Moreover, it turns out that also other European railway operators use exactly the same methodology (but not terminology). Since a rotation can have many handouts of different quality, we show how to compute optimal ones through an integer program (IP) by standard software. In addition, a construction as well as an improvement heuristic are presented. Our computational results show that the heuristics are a very reliable standalone approach to quickly find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a computational comparison to the IP approach.}, language = {en} } @inproceedings{GrimmBorndoerferReutheretal., author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance}, series = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, volume = {75}, booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, editor = {Cacchiani, Valentina and Marchetti-Spaccamela, Alberto}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2019.1}, pages = {1:1 -- 1:12}, abstract = {For providing railway services the company's railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see [Mar{\´o}ti and Kroon, 2005; G{\´a}bor Mar{\´o}ti and Leo G. Kroon, 2007], or [Cordeau et al., 2001] for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in [Ralf Bornd{\"o}rfer et al., 2015]. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of [Reuther, 2017] that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.}, language = {en} } @misc{GrimmBorndoerferReutheretal., author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance}, series = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, journal = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, issn = {1438-0064}, doi = {https://doi.org/10.4230/OASIcs.ATMOS.2019.1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75501}, abstract = {For providing railway services the company's railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see Maroti and Kroon 2005, or Cordeau et. al. 2001 for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in Bornd{\"o}rfer et. al. 2015. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of Reuther 2017 that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.}, language = {en} } @article{BorndoerferEsserFrankenbergeretal., author = {Bornd{\"o}rfer, Ralf and Eßer, Thomas and Frankenberger, Patrick and Huck, Andreas and Jobmann, Christoph and Krostitz, Boris and Kuchenbecker, Karsten and Moorhagen, Kai and Nagl, Philipp and Peterson, Michael and Reuther, Markus and Schang, Thilo and Schoch, Michael and Sch{\"u}lldorf, Hanno and Sch{\"u}tz, Peter and Therolf, Tobias and Waas, Kerstin and Weider, Steffen}, title = {Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization}, series = {Informs Journal on Applied Analytics}, volume = {51}, journal = {Informs Journal on Applied Analytics}, number = {1}, doi = {10.1287/inte.2020.1069}, pages = {42 -- 62}, abstract = {Deutsche Bahn (DB) operates a large fleet of rolling stock (locomotives, wagons, and train sets) that must be combined into trains to perform rolling stock rotations. This train composition is a special characteristic of railway operations that distinguishes rolling stock rotation planning from the vehicle scheduling problems prevalent in other industries. DB models train compositions using hyperarcs. The resulting hypergraph models are ad-dressed using a novel coarse-to-fine method that implements a hierarchical column genera-tion over three levels of detail. This algorithm is the mathematical core of DB's fleet em-ployment optimization (FEO) system for rolling stock rotation planning. FEO's impact within DB's planning departments has been revolutionary. DB has used it to support the company's procurements of its newest high-speed passenger train fleet and its intermodal cargo locomotive fleet for cross-border operations. FEO is the key to successful tendering in regional transport and to construction site management in daily operations. DB's plan-ning departments appreciate FEO's high-quality results, ability to reoptimize (quickly), and ease of use. Both employees and customers benefit from the increased regularity of operations. DB attributes annual savings of 74 million euro, an annual reduction of 34,000 tons of CO2 emissions, and the elimination of 600 coupling operations in cross-border operations to the implementation of FEO.}, language = {en} } @inproceedings{BertholdGrimmReutheretal., author = {Berthold, Timo and Grimm, Boris and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {Strategic Planning of Rolling Stock Rotations for Public Tenders}, series = {Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrköping 2019}, volume = {Link{\"o}ping Electronic Conference Proceedings}, booktitle = {Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrköping 2019}, number = {069}, publisher = {Link{\"o}ping University Electronic Press, Link{\"o}pings universitet}, isbn = {978-91-7929-992-7}, issn = {1650-3686}, pages = {148 -- 159}, abstract = {Since railway companies have to apply for long-term public contracts to operate railway lines in public tenders, the question how they can estimate the operating cost for long-term periods adequately arises naturally. We consider a rolling stock rotation problem for a time period of ten years, which is based on a real world instance provided by an industry partner. We use a two stage approach for the cost estimation of the required rolling stock. In the first stage, we determine a weekly rotation plan. In the second stage, we roll out this weekly rotation plan for a longer time period and incorporate scheduled maintenance treatments. We present a heuristic approach and a mixed integer programming model to implement the process of the second stage. Finally, we discuss computational results for a real world tendering scenario.}, language = {en} } @book{AbbinkBaermannBešinovicetal., author = {Abbink, Erwin and B{\"a}rmann, Andreas and Bešinovic, Nikola and Bohlin, Markus and Cacchiani, Valentina and Caimi, Gabrio and de Fabris, Stefano and Dollevoet, Twan and Fischer, Frank and F{\"u}genschuh, Armin and Galli, Laura and Goverde, Rob M.P. and Hansmann, Ronny and Homfeld, Henning and Huisman, Dennis and Johann, Marc and Klug, Torsten and T{\"o}rnquist Krasemann, Johanna and Kroon, Leo and Lamorgese, Leonardo and Liers, Frauke and Mannino, Carlo and Medeossi, Giorgio and Pacciarelli, Dario and Reuther, Markus and Schlechte, Thomas and Schmidt, Marie and Sch{\"o}bel, Anita and Sch{\"u}lldorf, Hanno and Stieber, Anke and Stiller, Sebastian and Toth, Paolo and Zimmermann, Uwe}, title = {Handbook of Optimization in the Railway Industry}, volume = {268}, editor = {Bornd{\"o}rfer, Ralf and Klug, Torsten and Lamorgese, Leonardo and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, publisher = {Springer Verlag}, isbn = {978-3-319-72152-1}, doi = {10.1007/978-3-319-72153-8}, abstract = {This book promotes the use of mathematical optimization and operations research methods in rail transportation. The editors assembled thirteen contributions from leading scholars to present a unified voice, standardize terminology, and assess the state-of-the-art. There are three main clusters of articles, corresponding to the classical stages of the planning process: strategic, tactical, and operational. These three clusters are further subdivided into five parts which correspond to the main phases of the railway network planning process: network assessment, capacity planning, timetabling, resource planning, and operational planning. Individual chapters cover: Simulation Capacity Assessment Network Design Train Routing Robust Timetabling Event Scheduling Track Allocation Blocking Shunting Rolling Stock Crew Scheduling Dispatching Delay Propagation}, language = {en} } @inproceedings{BorndoerferBreuerGrimmetal., author = {Bornd{\"o}rfer, Ralf and Breuer, Matthias and Grimm, Boris and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {Timetable Sparsification by Rolling Stock Rotation Optimization}, series = {Operations Research 2017}, booktitle = {Operations Research 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_96}, pages = {723 -- 728}, abstract = {Rolling stock optimization is a task that naturally arises by operating a railway system. It could be seen with different level of details. From a strategic perspective to have a rough plan which types of fleets to be bought to a more operational perspective to decide which coaches have to be maintained first. This paper presents a new approach to deal with rolling stock optimisation in case of a (long term) strike. Instead of constructing a completely new timetable for the strike period, we propose a mixed integer programming model that is able to choose appropriate trips from a given timetable to construct efficient tours of railway vehicles covering an optimized subset of trips, in terms of deadhead kilometers and importance of the trips. The decision which trip is preferred over the other is made by a simple evaluation method that is deduced from the network and trip defining data.}, language = {en} } @inproceedings{GamrathReutherSchlechteetal., author = {Gamrath, Gerwin and Reuther, Markus and Schlechte, Thomas and Swarat, Elmar}, title = {An LP-based heuristic for Inspector Scheduling}, series = {Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021: Volume I}, volume = {1}, booktitle = {Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021: Volume I}, pages = {77 -- 86}, abstract = {We present a heuristic based on linear programming (LP) for the integrated tour and crew roster planning of toll enforcement inspectors. Their task is to enforce the proper paying of a distance-based toll on German motorways. This leads to an integrated tour planning and duty rostering problem; it is called Toll Enforcement Problem (TEP). We tackle the TEP by a standard multi-commodity flow model with some extensions in order to incorporate the control tours. The heuristic consists of two variants. The first, called Price \& Branch, is a column generation approach to solve the model's LP relaxation by pricing tour and roster arc variables. Then, we compute an integer feasible solution by restricting to all variables that were priced. The second is a coarse-to-fine approach. Its basic idea is projecting variables to an aggregated variable space, which is much smaller. The aim is to spend as much algorithmic effort in this coarse model as possible. For both heuristic procedures we will show that feasible solutions of high quality can be computed even for large scale industrial instances.}, language = {en} } @article{SchlechteBorndoerferDenissenetal., author = {Schlechte, Thomas and Bornd{\"o}rfer, Ralf and Denißen, Jonas and Heller, Simon and Klug, Torsten and K{\"u}pper, Michael and Lindner, Niels and Reuther, Markus and S{\"o}hlke, Andreas and Steadman, William}, title = {Timetable Optimization for a Moving Block System}, series = {Journal of Rail Transport Planning \& Management}, volume = {22}, journal = {Journal of Rail Transport Planning \& Management}, issn = {2210-9706}, doi = {10.1016/j.jrtpm.2022.100315}, pages = {100315}, abstract = {We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality.}, language = {en} } @misc{BorndoerferDenissenHelleretal., author = {Bornd{\"o}rfer, Ralf and Denißen, Jonas and Heller, Simon and Klug, Torsten and K{\"u}pper, Michael and Lindner, Niels and Reuther, Markus and Schlechte, Thomas and S{\"o}hlke, Andreas and Steadman, William}, title = {Microscopic Timetable Optimization for a Moving Block System}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82547}, abstract = {We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality.}, language = {en} } @misc{BorndoerferReutherSchlechte, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51009}, abstract = {We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.}, language = {en} } @misc{ReutherBorndoerferSchlechteetal., author = {Reuther, Markus and Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen}, title = {Integrated Optimization of Rolling Stock Rotations for Intercity Railways}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16424}, abstract = {This paper provides a highly integrated solution approach for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a generic hypergraph based mixed integer programming model and an integrated algorithm for the considered rolling stock rotation planning problem. The new developed approach is able to handle a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects. By the integration of this large bundle of technical railway aspects, we show that our approach has the power to produce implementable rolling stock rotations for our industrial cooperation partner DB Fernverkehr. This is the first time that the rolling stock rotations at DB Fernverkehr could be optimized by an automated system utilizing advanced mathematical programming techniques.}, language = {en} } @inproceedings{KlugReutherSchlechte, author = {Klug, Torsten and Reuther, Markus and Schlechte, Thomas}, title = {Does Laziness Pay Off? - A Lazy-Constraint Approach to Timetabling}, series = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, volume = {106}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/OASIcs.ATMOS.2022.11}, pages = {11:1 -- 11:8}, abstract = {Timetabling is a classical and complex task for public transport operators as well as for railway undertakings. The general question is: Which vehicle is taking which route through the transportation network in which order? In this paper, we consider the special setting to find optimal timetables for railway systems under a moving block regime. We directly set up on our work of [8 ], i.e., we consider the same model formulation and real-world instances of a moving block headway system. In this paper, we present a repair heuristic and a lazy-constraint approach utilizing the callback features of Gurobi, see [3]. We provide an experimental study of the different algorithmic approaches for a railway network with 100 and up to 300 train requests. The computational results show that the lazy-constraint approach together with the repair heuristic significantly improves our previous approaches.}, language = {en} }