TY - THES A1 - Schlechte, Thomas T1 - Railway Track Allocation: Models and Algorithms N2 - This thesis is about mathematical optimization for the efficient use of railway infrastructure. We address the optimal allocation of the available railway track capacity - the track allocation problem. This track allocation problem is a major challenge for a railway company, independent of whether a free market, a private monopoly, or a public monopoly is given. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense sizes of the problem instances. Mathematical models and optimization techniques can result in huge gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. We tackle this challenge by developing novel mathematical models and associated innovative algorithmic solution methods for large scale instances. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland. The opening chapter gives a comprehensive overview on railway planning problems. This provides insights into the regulatory and technical framework, it discusses the interaction of several planning steps, and identifies optimization potentials in railway transportation. The remainder of the thesis is comprised of two major parts. The first part is concerned with modeling railway systems to allow for resource and capacity analysis. Railway capacity has basically two dimensions, a space dimension which are the physical infrastructure elements as well as a time dimension that refers to the train movements, i.e., occupation or blocking times, on the physical infrastructure. Railway safety systems operate on the same principle all over the world. A train has to reserve infrastructure blocks for some time to pass through. Two trains reserving the same block of the infrastructure within the same point in time is called block conflict. Therefore, models for railway capacity involve the definition and calculation of reasonable running and associated reservation and blocking times to allow for a conflict free allocation. In the second and main part of the thesis, the optimal track allocation problem for macroscopic models of the railway system is considered. The literature for related problems is surveyed. A graph-theoretic model for the track allocation problem is developed. In that model optimal track allocations correspond to conflict-free paths in special time-expanded graphs. Furthermore, we made considerable progress on solving track allocation problems by two main features - a novel modeling approach for the macroscopic track allocation problem and algorithmic improvements based on the utilization of the bundle method. Finally, we go back to practice and present in the last chapter several case studies using the tools netcast and tsopt. We provide a computational comparison of our new models and standard packing models used in the literature. Our computational experience indicates that our approach, i.e., ``configuration models'', outperforms other models. Moreover, the rapid branching heuristic and the bundle method enable us to produce high quality solutions for very large scale instances, which has not been possible before. In addition, we present results for a theoretical and rather visionary auction framework for track allocation. We discuss several auction design questions and analyze experiments of various auction simulations. The highlights are results for the Simplon corridor in Switzerland. We optimized the train traffic through this tunnel using our models and software tools. To the best knowledge of the author and confirmed by several railway practitioners this was the first time that fully automatically produced track allocations on a macroscopic scale fulfill the requirements of the originating microscopic model, withstand the evaluation in the microscopic simulation tool OpenTrack, and exploit the infrastructure capacity. This documents the success of our approach in practice and the usefulness and applicability of mathematical optimization to railway track allocation. KW - railway track allocation KW - large-scale integer programming KW - network aggregation KW - rapid branching Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:83-opus-34272 UR - http://opus.kobv.de/tuberlin/volltexte/2012/3427/pdf/schlechte_thomas.pdf SN - 978-3-8381-3222-8 PB - Südwestdeutscher Verlag für Hochschulschriften CY - Saarbrücken, Germany ER - TY - GEN A1 - Schlechte, Thomas T1 - Railway Track Allocation N2 - This article gives an overview of the results of the author's PhD thesis. The thesis deals with the mathematical optimization for the efficient use of railway infrastructure. We address the optimal allocation of the available railway track capacity - the track allocation problem. This track allocation problem is a major challenge for a railway company, independent of whether a free market, a private monopoly, or a public monopoly is given. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense sizes of the problem instances. Mathematical models and optimization techniques can result in huge gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. We tackle this challenge by developing novel mathematical models and associated innovative algorithmic solution methods for large scale instances. We made considerable progress on solving track allocation problems by two main features - a novel modeling approach for the macroscopic track allocation problem and algorithmic improvements based on the utilization of the bundle method. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland. T3 - ZIB-Report - 12-38 KW - large-scale integer programming KW - network aggregation KW - configuration models KW - rapid branching Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16402 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Rapid Branching 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. T3 - ZIB-Report - 12-10 KW - large scale optimization KW - rapid branching KW - column generation Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14728 SN - 1438-0064 ER - 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 -