@article{HarrodSchlechte2013, author = {Harrod, Steven and Schlechte, Thomas}, title = {A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations}, volume = {54}, journal = {Transportation Research Part E: Logistics and Transportation Review}, doi = {10.1016/j.tre.2013.04.003}, pages = {50 -- 66}, year = {2013}, abstract = {Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, RCHF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and RCHF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall.}, language = {en} } @book{AbbinkBaermannBešinovicetal.2018, 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}, year = {2018}, 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} } @misc{OPUS4-7166, title = {Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, editor = {Bornd{\"o}rfer, Ralf and Storandt, Sabine}, publisher = {Dagstuhl Publishing, Saarbr{\"u}cken/Wadern, Germany}, isbn = {ISBN 978-3-95977-096-5}, doi = {10.4230/OASIcs.ATMOS.2018.0}, year = {2018}, abstract = {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{\"o}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{\´e}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.}, language = {en} } @misc{BorndoerferFuegenschuhKlugetal.2013, author = {Bornd{\"o}rfer, Ralf and F{\"u}genschuh, Armin and Klug, Torsten and Schang, Thilo and Schlechte, Thomas and Sch{\"u}lldorf, Hanno}, title = {The Freight Train Routing Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18991}, year = {2013}, abstract = {We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that a sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. Here macroscopic refers to an aggregation of complex real-world structures are into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We give a mixed-integer nonlinear programming~(MINLP) formulation for FTRP, which is a multi-commodity flow model on a time-expanded graph with additional routing constraints. The model's nonlinearities are due to an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model~(MILP) by piecewise linear approximation. The latter is solved by a state of the art MILP solver for various real-world test instances.}, language = {en} } @misc{BlancoSchlechte2013, author = {Blanco, Marco and Schlechte, Thomas}, title = {Analysis of Micro-Macro Transformations of Railway Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42710}, year = {2013}, abstract = {A common technique in the solution of large or complex optimization problems is the use of micro-macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconvieniently by underestimating the global optimal value.}, language = {en} } @article{BorndoerferFuegenschuhKlugetal.2016, author = {Bornd{\"o}rfer, Ralf and F{\"u}genschuh, Armin and Klug, Torsten and Schang, Thilo and Schlechte, Thomas and Sch{\"u}lldorf, Hanno}, title = {The Freight Train Routing Problem for Congested Railway Networks with Mixed Traffic}, volume = {50}, journal = {Transportation Science}, number = {2}, doi = {10.1287/trsc.2015.0656}, pages = {408 -- 423}, year = {2016}, abstract = {We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that the sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. In this context, macroscopic refers to an aggregation of complex and large real-world structures into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We provide a mixed-integer nonlinear programming (MINLP) formulation for the FTRP, which is a multicommodity flow model on a time-expanded graph with additional routing constraints. The model's nonlinearities originate from an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model (MILP) by piecewise linear approximation. The latter is solved by a state-of-the art MILP solver for various real-world test instances.}, language = {en} } @incollection{Klug2018, author = {Klug, Torsten}, title = {Freight Train Routing}, volume = {268}, booktitle = {Handbook of Optimization in the Railway Industry}, publisher = {Springer International Publishing}, isbn = {978-3-319-72152-1}, doi = {10.1007/978-3-319-72153-8}, pages = {73 -- 92}, year = {2018}, abstract = {This chapter is about strategic routing of freight trains in railway transportation networks with mixed traffic. A good utilization of a railway transportation network is important since in contrast to road and air traffic the routing through railway networks is more challenging and the extension of capacities is expensive and a long-term projects. Therefore, an optimized routing of freight trains have a great potential to exploit remaining capacity since the routing has fewer restrictions compared to passenger trains. In this chapter we describe the freight train routing problem in full detail and present a mixed-integer formulation. Wo focus on a strategic level that take into account the actual immutable passenger traffic. We conclude the chapter with a case study for the German railway network.}, language = {en} } @article{BorndoerferKlugLamorgeseetal.2017, author = {Bornd{\"o}rfer, Ralf and Klug, Torsten and Lamorgese, Leonardo and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, title = {Recent success stories on integrated optimization of railway systems}, volume = {74}, journal = {Transportation Research Part C: Emerging Technologies}, number = {1}, doi = {10.1016/j.trc.2016.11.015}, pages = {196 -- 211}, year = {2017}, abstract = {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{\"o}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.}, language = {en} } @misc{FischerGrimmKlugetal.2016, author = {Fischer, Frank and Grimm, Boris and Klug, Torsten and Schlechte, Thomas}, title = {A Re-optimization Approach for Train Dispatching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60493}, year = {2016}, abstract = {The Train Dispatching Problem (TDP) is to schedule trains through a network in a cost optimal way. Due to disturbances during operation existing track allocations often have to be re-scheduled and integrated into the timetable. This has to be done in seconds and with minimal timetable changes to guarantee smooth and conflict free operation. We present an integrated modeling approach for the re-optimization task using Mixed Integer Programming. Finally, we provide computational results for scenarios provided by the INFORMS RAS Problem Soling Competition 2012.}, language = {en} } @misc{BorndoerferKlugLamorgeseetal.2015, author = {Bornd{\"o}rfer, Ralf and Klug, Torsten and Lamorgese, Leonardo and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, title = {Recent Success Stories on Optimization of Railway Systems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53726}, year = {2015}, abstract = {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.}, language = {en} } @misc{FuegenschuhJunoszaSzaniawskiKlugetal.2015, author = {F{\"u}genschuh, Armin and Junosza-Szaniawski, Konstanty and Klug, Torsten and Kwasiborski, Slawomir and Schlechte, Thomas}, title = {Fastest, average and quantile schedule}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53592}, year = {2015}, abstract = {We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.}, language = {en} } @inproceedings{KlugJunoszaSzaniawskiKwasiborskietal.2015, author = {Klug, Torsten and Junosza-Szaniawski, Konstanty and Kwasiborski, Slawomir and F{\"u}genschuh, Armin and Schlechte, Thomas}, title = {Fastest, Average and Quantile Schedule}, booktitle = {SOFSEM 2015: Theory and Practice of Computer Science}, publisher = {Springer Berlin Heidelberg}, doi = {10.1007/978-3-662-46078-8_17}, pages = {201 -- 216}, year = {2015}, abstract = {We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.}, language = {en} } @inproceedings{FischerSchlechte2015, author = {Fischer, Frank and Schlechte, Thomas}, title = {Comparing two dual relaxations of large scale train timetabling problems}, booktitle = {Proceedings of Conference on Advanced Systems in Public Transport 2015}, year = {2015}, abstract = {Railway transportation and in particular train timetabling is one of the basic and source application areas of combinatorial optimization and integer programming. We will discuss two well established modeling techniques for the train timetabling problem. In this paper we focus on one major ingredient - the bounding by dual relaxations. We compare two classical dual relaxations of large scale time expanded train timetabling problems - the Lagrangean Dual and Lagrangean Decomposition. We discuss the convergence behavior and show limitations of the Lagrangean Decomposition approach for a configuration based model. We introduce a third dualization approach to overcome those limitations. Finally, we present promising preliminary computational experiments that show that our new approach indeed has superior convergence properties.}, language = {en} }