TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Vehicle Rotation Planning for Intercity Railways N2 - This paper provides a generic formulation for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a graph theoretical model and a Mixed-Integer-Programming formulation that integrate all main requirements of the considered Vehicle-Rotation-Planning problem (VRPP). We show that it is possible to solve this model for real-world instances provided by our industrial partner DB Fernverkehr AG using modern algorithms and computers. T3 - ZIB-Report - 12-11 KW - rolling-stock-planning KW - mixed-integer-programming KW - hypergraphs KW - column generation KW - rapid branching Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14731 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - A Hypergraph Model for Railway Vehicle Rotation Planning N2 - We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved. T3 - ZIB-Report - 11-36 KW - Rolling Stock Planning, Hypergraph Modeling, Integer Programming, Column Generation, Rapid Branching Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-32746 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Mehrgardt, Julika A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Waas, Kerstin T1 - Re-Optimization of Rolling Stock Rotations N2 - The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, such as vehicle composition, maintenance constraints, and regularity aspects. In industrial applications existing vehicle rotations often have to be re-optimized to deal with timetable changes or construction sites. We present an integrated modeling and algorithmic approach to this task as well as computational results for industrial problem instances of DB Fernverkehr AG. Y1 - 2014 U6 - https://doi.org/10.1007/978-3-319-07001-8_8 SP - 49 EP - 55 PB - Springer International Publishing ET - Operations Research Proceedings 2013 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Lamorgese, Leonardo A1 - Klug, Torsten A1 - Mannino, Carlo A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Recent Success Stories on Optimization of Railway Systems T2 - Proceedings of the IAROR conference RailTokyo N2 - Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway cus- tomers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain devel- oping mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice, with a few notable exceptions. In this paper we address three success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will dis- cuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that math- ematical optimization can support the planning of rolling stock resources. Thus, mathematical models and optimization can lead to a greater effi- ciency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry. Y1 - 2015 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Waas, Kerstin A1 - Weider, Steffen T1 - Integrated Optimization of Rolling Stock Rotations for Intercity Railways JF - Transportation Science N2 - This paper proposes a highly integrated solution approach for rolling stock planning problems in the context of long distance passenger traffic between cities. The main contributions are a generic hypergraph-based mixed-integer programming model for the considered rolling stock rotation problem and an integrated algorithm for its solution. The newly developed algorithm is able to handle a large spectrum of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacities, and regularity aspects. We show that our approach has the power to produce rolling stock rotations that can be implemented in practice. In this way, the rolling stock rotations at the largest German long distance operator Deutsche Bahn Fernverkehr AG could be optimized by an automated system utilizing advanced mathematical programming techniques. Y1 - 2016 U6 - https://doi.org/10.1287/trsc.2015.0633 VL - 50 IS - 3 SP - 863 EP - 877 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Mehrgahrdt, Julika A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - The Cycle Embedding Problem T2 - Operations Research Proceedings 2014 N2 - Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-28697-6_65 SP - 465 EP - 472 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Klug, Torsten A1 - Lamorgese, Leonardo A1 - Mannino, Carlo A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Recent success stories on integrated optimization of railway systems JF - Transportation Research Part C: Emerging Technologies N2 - Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain developing mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice (e.g. Cacchiani et al., 2014; Borndörfer et al., 2010), with a few notable exceptions. In this paper we address three individual success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will discuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that mathematical optimization can support the planning of railway resources. Thus, mathematical models and optimization can lead to a greater efficiency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry. Y1 - 2017 U6 - https://doi.org/10.1016/j.trc.2016.11.015 VL - 74 IS - 1 SP - 196 EP - 211 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - A Hypergraph Model for Railway Vehicle Rotation Planning JF - 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems N2 - We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved. Y1 - 2011 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2011.146 VL - OpenAccess Series in Informatics (OASIcs) IS - 20 SP - 146 EP - 155 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen ED - Muñoz, J. C. ED - Voß, S. T1 - Rapid Branching JF - Public Transport N2 - We propose rapid branching (RB) as a general branch-and-bound heuristic for solving large scale optimization problems in traffic and transport. The key idea is to combine a special branching rule and a greedy node selection strategy in order to produce solutions of controlled quality rapidly and efficiently. We report on three successful applications of the method for integrated vehicle and crew scheduling, railway track allocation, and railway vehicle rotation planning. Y1 - 2013 VL - 5 IS - 1 SP - 3 EP - 23 PB - Springer Berlin Heidelberg ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen ED - Muñoz, J. C. ED - Voß, S. T1 - Vehicle Rotation Planning for Intercity Railways JF - Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12) N2 - This paper provides a generic formulation for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a graph theoretical model and a Mixed-Integer-Programming formulation that integrate all main requirements of the considered Vehicle-Rotation-Planning problem (VRPP). We show that it is possible to solve this model for real-world instances provided by our industrial partner DB Fernverkehr AG using modern algorithms and computers. Y1 - 2012 ER - TY - THES A1 - Brückner, Michael T1 - Polyedrische Approximation von Punktwolke und ihre Anwendung in der ICE-Abstellungsplanung Y1 - 2012 ER - TY - THES A1 - Mehrgardt, Julika T1 - Kreiseinbettungen von Hypergraphen und ihre Anwendung in der Umlaufoptimierung Y1 - 2013 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Optimization of Handouts for Rolling Stock Rotations Visualization N2 - 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. T3 - ZIB-Report - ZR-16-73 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61430 SN - 1438-0064 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Template-based Re-optimization of Rolling Stock Rotations JF - Public Transport N2 - Rolling stock, i.e., the set of railway vehicles, is among the most expensive and limited assets of a railway company and must be used efficiently. We consider in this paper the re-optimization problem to recover from unforeseen disruptions. We propose a template concept that allows to recover cost minimal rolling stock rotations from reference rotations under a large variety of operational requirements. To this end, connection templates as well as rotation templates are introduced and their application within a rolling stock rotation planning model is discussed. We present an implementation within the rolling stock rotation optimization framework rotor and computational results for scenarios provided by DB Fernverkehr AG, one of the leading railway operators in Europe. Y1 - 2017 U6 - https://doi.org/10.1007/s12469-017-0152-4 SP - 1 EP - 19 PB - Springer ER - TY - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Mehrgardt, Julika A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - The Cycle Embedding Problem N2 - Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach. T3 - ZIB-Report - 14-37 KW - cycle embedding problem KW - railway vehicle rotation scheduling KW - sequential coarse-first-fine-second planning approach Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52788 SN - 1438-0064 ER - TY - CHAP A1 - Reuther, Markus T1 - Local Search for the Resource Constrained Assignment Problem T2 - 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems N2 - The resource constrained assignment problem (RCAP) is to find a minimal cost cycle partition in a directed graph such that a resource constraint is fulfilled. The RCAP has its roots in an application that deals with the covering of a railway timetable by rolling stock vehicles. Here, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes several variants of vehicle routing problems. We contribute a local search algorithm for this problem that is derived from an exact algorithm which is similar to the Hungarian method for the standard assignment problem. Our algorithm can be summarized as a k-OPT heuristic, exchanging k arcs of an alternating cycle of the incumbent solution in each improvement step. The alternating cycles are found by dual arguments from linear programming. We present computational results for instances from our railway application at Deutsche Bahn Fernverkehr AG as well as for instances of the vehicle routing problem from the literature. Y1 - 2014 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2014.62 VL - 42 SP - 62 EP - 78 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem T2 - 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems N2 - 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. Y1 - 2014 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2014.79 VL - 42 SP - 79 EP - 91 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Klug, Torsten A1 - Lamorgese, Leonardo A1 - Mannino, Carlo A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Recent Success Stories on Optimization of Railway Systems N2 - Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway cus- tomers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain devel- oping mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice, with a few notable exceptions. In this paper we address three success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will dis- cuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that math- ematical optimization can support the planning of rolling stock resources. Thus, mathematical models and optimization can lead to a greater effi- ciency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry. T3 - ZIB-Report - 14-47 KW - railway planning KW - railway operations KW - capacity optimization Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53726 SN - 1438-0064 ER - TY - THES A1 - Reuther, Markus T1 - Mathematical Optimization of Rolling Stock Rotations N2 - 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. Y1 - 2017 UR - https://depositonce.tu-berlin.de/handle/11303/6309 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Eßer, Thomas A1 - Frankenberger, Patrick A1 - Huck, Andreas A1 - Jobmann, Christoph A1 - Krostitz, Boris A1 - Kuchenbecker, Karsten A1 - Moorhagen, Kai A1 - Nagl, Philipp A1 - Peterson, Michael A1 - Reuther, Markus A1 - Schang, Thilo A1 - Schoch, Michael A1 - Schülldorf, Hanno A1 - Schütz, Peter A1 - Therolf, Tobias A1 - Waas, Kerstin A1 - Weider, Steffen T1 - Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization JF - Informs Journal on Applied Analytics N2 - 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. Y1 - 2021 U6 - https://doi.org/10.1287/inte.2020.1069 VL - 51 IS - 1 SP - 42 EP - 62 ER - TY - BOOK A1 - Abbink, Erwin A1 - Bärmann, Andreas A1 - Bešinovic, Nikola A1 - Bohlin, Markus A1 - Cacchiani, Valentina A1 - Caimi, Gabrio A1 - de Fabris, Stefano A1 - Dollevoet, Twan A1 - Fischer, Frank A1 - Fügenschuh, Armin A1 - Galli, Laura A1 - Goverde, Rob M.P. A1 - Hansmann, Ronny A1 - Homfeld, Henning A1 - Huisman, Dennis A1 - Johann, Marc A1 - Klug, Torsten A1 - Törnquist Krasemann, Johanna A1 - Kroon, Leo A1 - Lamorgese, Leonardo A1 - Liers, Frauke A1 - Mannino, Carlo A1 - Medeossi, Giorgio A1 - Pacciarelli, Dario A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Schmidt, Marie A1 - Schöbel, Anita A1 - Schülldorf, Hanno A1 - Stieber, Anke A1 - Stiller, Sebastian A1 - Toth, Paolo A1 - Zimmermann, Uwe ED - Borndörfer, Ralf ED - Klug, Torsten ED - Lamorgese, Leonardo ED - Mannino, Carlo ED - Reuther, Markus ED - Schlechte, Thomas T1 - Handbook of Optimization in the Railway Industry N2 - 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 Y1 - 2018 SN - 978-3-319-72152-1 U6 - https://doi.org/10.1007/978-3-319-72153-8 VL - 268 PB - Springer Verlag ER - TY - GEN ED - Borndörfer, Ralf ED - Storandt, Sabine T1 - Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems N2 - Running and optimizing transportation systems give rise to very complex and large-scale optimization problems requiring innovative solution techniques and ideas from mathematical optimization, theoretical computer science, and operations research. Since 2000, the series of Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) workshops brings together researchers and practitioners who are interested in all aspects of algorithmic methods and models for transportation optimization and provides a forum for the exchange and dissemination of new ideas and techniques. The scope of ATMOS comprises all modes of transportation. The 18th ATMOS workshop (ATMOS’18) was held in connection with ALGO’18 and hosted by Aalto University in Helsinki, Finland, on August 23–24, 2018. Topics of interest were all optimization problems for passenger and freight transport, including, but not limited to, demand forecasting, models for user behavior, design of pricing systems, infrastructure planning, multi-modal transport optimization, mobile applications for transport, congestion modelling and reduction, line planning, timetable generation, routing and platform assignment, vehicle scheduling, route planning, crew and duty scheduling, rostering, delay management, routing in road networks, traffic guidance, and electro mobility. Of particular interest were papers applying and advancing techniques like graph and network algorithms, combinatorial optimization, mathematical programming, approximation algorithms, methods for the integration of planning stages, stochastic and robust optimization, online and real-time algorithms, algorithmic game theory, heuristics for real-world instances, and simulation tools. There were twenty-nine submissions from eighteen countries. All of them were reviewed by at least three referees in ninety-one reviews, among them five external ones, and judged on their originality, technical quality, and relevance to the topics of the workshop. Based on the reviews, the program committee selected sixteen submissions to be presented at the workshop (acceptance rate: 55%), which are collected in this volume in the order in which they were presented. Together, they quite impressively demonstrate the range of applicability of algorithmic optimization to transportation problems in a wide sense. In addition, Dennis Huisman kindly agreed to complement the program with an invited talk on Railway Disruption Management: State-of-the-art in practice and new research directions. Based on the reviews, Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner won the Best Paper Award of ATMOS’18 with their paper A simple way to compute the number of vehicles that Are required to operate a periodic timetable. In addition, we awarded Tomas Lidén the Best VGI Paper Award of ATMOS’18 for his paper Reformulations for railway traffic and maintenance planning. We would like to thank the members of the Steering Committee of ATMOS for giving us the opportunity to serve as Program Chairs of ATMOS’18, all the authors who submitted papers, Dennis Huisman for accepting our invitation to present an invited talk, the members of the Program Committee and the additional reviewers for their valuable work in selecting the papers appearing in this volume, our sponsors MODAL, TomTom, and VGIscience for their support of the prizes, and the local organizers for hosting the workshop as part of ALGO’18. We acknowledge the use of the EasyChair system for the great help in managing the submission and review processes, and Schloss Dagstuhl for publishing the proceedings of ATMOS’18 in its OASIcs series. Y1 - 2018 SN - ISBN 978-3-95977-096-5 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2018.0 PB - Dagstuhl Publishing, Saarbrücken/Wadern, Germany ER - TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem N2 - 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. T3 - ZIB-Report - 14-26 KW - column generation KW - coarse-to-fine approach KW - multi-layer approach KW - rolling stock rotation problem Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51009 SN - 1438-0064 ER - TY - GEN A1 - Reuther, Markus A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Integrated Optimization of Rolling Stock Rotations for Intercity Railways N2 - 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. T3 - ZIB-Report - 12-39 KW - Mixed Integer Programming KW - Railway Optimization KW - Rolling Stock Rostering Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16424 SN - 1438-0064 ER -