TY - CHAP A1 - Fischer, Frank A1 - Schlechte, Thomas ED - D'Angelo, Gianlorenzo ED - Dollevoet, Twan T1 - Strong Relaxations for the Train Timetabling Problem using Connected Configurations T2 - 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017) N2 - The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by so called connected configuration subproblems. These subproblems perfectly describe feasible schedules of a small subset of trains (2-3) on consecutive track segments. In a Lagrangian relaxation approach we solve several of these subproblems together in order to produce solutions which consist of combinatorially compatible schedules along the track segments. The computational results on a mostly single track corridor taken from the INFORMS RAS Problem Solving Competition 2012 data indicate that our new solution approach is rather strong. Indeed, for this instance the solution of the Lagrangian relaxation is already integral. Y1 - 2017 SN - 978-3-95977-042-2 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2017.11 VL - 59 ER - TY - GEN A1 - Schlechte, Thomas A1 - Borndörfer, Ralf T1 - Balancing Efficiency and Robustness – A Bi-criteria Optimization Approach to Railway Track Allocation N2 - Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to be propagated causing delays of subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bi-criteria optimization approach. On the one hand we want to maximize the profit of a schedule, that is more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in [BorndoerferSchlechte2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see [Ehrgott2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional $\epsilon$-constraint remains solvable in polynomial time. Finally, we present some preliminary results on macroscopic real-world data of a part of the German long distance railway network. T3 - ZIB-Report - 08-22 KW - Train Timetabling Problem KW - Bicriteria Optimization KW - Column Generation Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10763 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Lukac, Sascha A1 - Mitusch, Kay A1 - Schlechte, Thomas A1 - Schultz, Sören A1 - Tanner, Andreas T1 - An Auctioning Approach to Railway Slot Allocation N2 - We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity. T3 - ZIB-Report - 05-45 KW - Railway Slot Allocation KW - Train Dispatching KW - Combinatorial Auctions Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8786 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Models for Railway Track Allocation N2 - This article is about the optimal track allocation problem (OPTRA) to find, in a given railway network, a conflict free set of train routes of maximum value. We study two types of integer programming formulations: a standard formulation that models block conflicts in terms of packing constraints, and a new extended formulation that is based on additional configuration' variables. We show that the packing constraints in the standard formulation stem from an interval graph, and that they can be separated in polynomial time. It follows that the LP relaxation of a strong version of this model, including all clique inequalities from block conflicts, can be solved in polynomial time. We prove that the extended formulation produces the same LP bound, and that it can also be computed with this model in polynomial time. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view, because it features a constant number of rows and is therefore amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hannover-Fulda-Kassel region of the German long distance railway network are reported. T3 - ZIB-Report - 07-02 KW - Railway Slot Allocation KW - Train Timetabling KW - Combinatorial Optimization KW - Linear and Integer Programming Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9451 ER - TY - THES A1 - Borndörfer, Ralf T1 - Mathematical Optimization and Public Transportation N2 - This cumulative thesis collects the following six papers for obtaining the habilitation at the Technische Universität Berlin, Fakultät II – Mathematik und Naturwissenschaften: (1) Set packing relaxations of some integer programs. (2) Combinatorial packing problems. (3) Decomposing matrices into blocks. (4) A bundle method for integrated multi-depot vehicle and duty scheduling in public transit. (5) Models for railway track allocation. (6) A column-generation approach to line planning in public transport. Some changes were made to the papers compared to the published versions. These pertain to layout unifications, i.e., common numbering, figure, table, and chapter head layout. There were no changes with respect to notation or symbols, but some typos have been eliminated, references updated, and some links and an index was added. The mathematical content is identical. The papers are about the optimization of public transportation systems, i.e., bus networks, railways, and airlines, and its mathematical foundations, i.e., the theory of packing problems. The papers discuss mathematical models, theoretical analyses, algorithmic approaches, and computational aspects of and to problems in this area. Papers 1, 2, and 3 are theoretical. They aim at establishing a theory of packing problems as a general framework that can be used to study traffic optimization problems. Indeed, traffic optimization problems can often be modelled as path packing, partitioning, or covering problems, which lead directly to set packing, partitioning, and covering models. Such models are used in papers 4, 5, and 6 to study a variety of problems concerning the planning of line systems, buses, trains, and crews. The common aim is always to exploit as many degrees of freedom as possible, both at the level of the individual problems by using large-scale integer programming techniques, as well as on a higher level by integrating hitherto separate steps in the planning process. KW - set packing KW - set partitioning KW - set covering KW - polyhedral combinatorics KW - public transport KW - railways Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13613 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Railway Track Allocation - Simulation, Aggregation, and Optimization N2 - Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway company. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market in Europe. This leads to more potential conflicts between trains caused by an increasing demand of train paths. 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 size of the problem instances. In order to make best use of the infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithms can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and an associated concept for track allocation, that consists of three important parts, simulation, aggregation, and optimization. Furthermore, we present results of our general framework for real world data. T3 - ZIB-Report - 11-35 KW - railway models, railway capacity, track allocation framework Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14031 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Mura, Annette A1 - Schlechte, Thomas ED - Fleischmann, Bernhard ED - Borgwardt, Karl ED - Klein, Robert ED - Tuma, Axel T1 - Vickrey Auctions for Railway Tracks T2 - Operations Research Proceedings 2008 Y1 - 2009 UR - http://opus.kobv.de/zib/volltexte/2008/1122/ SP - 551 EP - 556 PB - Springer-Verlag ER - TY - BOOK A1 - Borndörfer, Ralf T1 - Mathematical Optimization and Public Transportation Y1 - 2010 PB - TU Berlin ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Weider, Steffen ED - Erlebach, Thomas ED - Lübbecke, Marco T1 - Railway Track Allocation by Rapid Branching T2 - Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems Y1 - 2010 UR - http://drops.dagstuhl.de/opus/volltexte/2010/2746 U6 - https://doi.org/http://dx.doi.org/10.4230/OASIcs.ATMOS.2010.13 VL - 14 SP - 13 EP - 23 PB - Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schlechte, Thomas ED - Kalcsics, Jörg ED - Nickel, Stefan T1 - Solving Railway Track Allocation Problems T2 - Operations Research Proceedings 2007 Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2007/974/ SP - 117 EP - 122 PB - Springer-Verlag ER - TY - GEN A1 - Schlechte, Thomas A1 - Tanner, Andreas T1 - Railway capacity auctions with dual prices N2 - Railway scheduling is based on the principle of the construction of a conflict-free timetable. This leads to a strict definition of capacity: in contrast with road transportation, it can be said in advance whether a given railway infrastructure can accommodate - at least in theory - a certain set of train requests. Consequently, auctions for railway capacity are modeled as auctions of discrete goods -- the train slots. We present estimates for the efficiency gain that may be generated by slot auctioning in comparison with list price allocation. We introduce a new class of allocation and auction problems, the feasible assignment problem, that is a proper generalization of the well-known combinatorial auction problem. The feasible assignment class was designed to cover the needs for an auction mechanism for railway slot auctions, but is of interest in its own right. As a practical instance to state and solve the railway slot allocation problem, we present an integer programming formulation, briefly the ACP, which turns out to be an instance of the feasible assignment problem and whose dual problem yields prices that can be applied to define a useful activity rule for the linearized version of the Ausubel Milgrom Proxy auction. We perform a simulation aiming to measure the impact on efficiency and convergence rate. T3 - ZIB-Report - 10-10 KW - Combinatorial Auction Problem KW - Railway Track Allocation KW - Ausubel Milgrom Proxy Auction Mechanism Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11729 SN - 1438-0064 ER - TY - GEN A1 - Fischer, Frank A1 - Schlechte, Thomas T1 - Comparing two dual relaxations of large scale train timetabling problems N2 - 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. T3 - ZIB-Report - 15-43 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56068 SN - 1438-0064 ER - TY - CHAP A1 - Fischer, Frank A1 - Schlechte, Thomas T1 - Comparing two dual relaxations of large scale train timetabling problems T2 - Proceedings of Conference on Advanced Systems in Public Transport 2015 N2 - 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. Y1 - 2015 ER - TY - CHAP A1 - Blanco, Marco A1 - Schlechte, Thomas T1 - Analysis of Micro–Macro Transformations of Railway Networks T2 - Operations Research Proceedings 2013 N2 - 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 inconveniently by underestimating the global optimal value. Y1 - 2014 U6 - https://doi.org/10.1007/978-3-319-07001-8_6 SP - 37 EP - 42 ER -