TY - GEN A1 - Borndörfer, Ralf A1 - Erol, Berkan A1 - Graffagnino, Thomas A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Aggregation Methods for Railway Networks N2 - In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run. T3 - ZIB-Report - 10-23 KW - makroskopische Bahnmodellierung KW - Netzwerkaggregation KW - macroscopic railway modeling KW - network aggregation Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11881 UR - http://www.sciencedirect.com/science/article/pii/S2210970611000047 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Erol, Berkan A1 - Graffagnino, Thomas A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Optimizing the Simplon Railway Corridor N2 - This paper presents a case study on a railway timetable optimization for the very dense Simplon corridor, a major railway connection in the Alps between Switzerland and Italy. Starting from a detailed microscopic network as it is used in railway simulation, the data is transformed by an automatic procedure to a less detailed macroscopic network, that is sufficient for the purpose of capacity planning and amenable to state-of-the-art integer programming optimization methods. In this way, the macroscopic railway network is saturated with trains. Finally, the corresponding timetable is re-transformed to the microscopic level in such a way that it can be operated without any conflicts among the slots. Using this integer programming based micro-macro aggregation-disaggregation approach, it becomes for the first time possible to generate a profit maximal and conflict free timetable for the complete Simplon corridor over an entire day by a simultaneous optimization of all trains requests. This also allows to to undertake a sensitivity analysis of various problem parameters. T3 - ZIB-Report - 10-24 KW - Trassenallokation KW - Netzwerkaggregation KW - Fallstudie KW - Simplon Korridor KW - railway track allocation KW - network aggregation KW - case study KW - Simplon corridor Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11892 SN - 1438-0064 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Erol, Berkan A1 - Graffagnino, Thomas A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Optimizing the Simplon railway corridor JF - Annals of Operations Research Y1 - 2012 UR - http://dx.doi.org/10.1007/s10479-012-1260-9 U6 - https://doi.org/10.1007/s10479-012-1260-9 VL - 218 IS - 1 SP - 93 EP - 106 PB - Springer US ET - Annals of Operations Research ER - TY - JOUR A1 - Schlechte, Thomas A1 - Borndörfer, Ralf A1 - Erol, Berkan A1 - Graffagnino, Thomas A1 - Swarat, Elmar T1 - Micro–macro transformation of railway networks JF - Journal of Rail Transport Planning & Management N2 - In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run. Y1 - 2011 U6 - https://doi.org/10.1016/j.jrtpm.2011.09.001 VL - 1 IS - 1 SP - 38 EP - 48 ER - TY - GEN A1 - Breugem, Thomas A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Schulz, Christof T1 - A Three-Phase Heuristic for Cyclic Crew Rostering with Fairness Requirements N2 - In this paper, we consider the Cyclic Crew Rostering Problem with Fairness Requirements (CCRP-FR). In this problem, attractive cyclic rosters have to be constructed for groups of employees, considering multiple, a priori determined, fairness levels. The attractiveness follows from the structure of the rosters (e.g., sufficient rest times and variation in work), whereas fairness is based on the work allocation among the different roster groups. We propose a three-phase heuristic for the CCRP-FR, which combines the strength of column generation techniques with a large-scale neighborhood search algorithm. The design of the heuristic assures that good solutions for all fairness levels are obtained quickly, and can still be further improved if additional running time is available. We evaluate the performance of the algorithm using real-world data from Netherlands Railways, and show that the heuristic finds close to optimal solutions for many of the considered instances. In particular, we show that the heuristic is able to quickly find major improvements upon the current sequential practice: For most instances, the heuristic is able to increase the attractiveness by at least 20% in just a few minutes. T3 - ZIB-Report - 19-43 KW - Crew Planning KW - Column Generation KW - Variable-Depth Neighborhood Search Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74297 SN - 1438-0064 ER - TY - JOUR A1 - Breugem, Thomas A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Borndörfer, Ralf T1 - A three-phase heuristic for the Fairness-Oriented Crew Rostering Problem JF - Computers & Operations Research N2 - The Fairness-Oriented Crew Rostering Problem (FCRP) considers the joint optimization of attractiveness and fairness in cyclic crew rostering. Like many problems in scheduling and logistics, the combinatorial complexity of cyclic rostering causes exact methods to fail for large-scale practical instances. In case of the FCRP, this is accentuated by the additionally imposed fairness requirements. Hence, heuristic methods are necessary. We present a three-phase heuristic for the FCRP combining column generation techniques with variable-depth neighborhood search. The heuristic exploits different mathematical formulations to find feasible solutions and to search for improvements. We apply our methodology to practical instances from Netherlands Railways (NS), the main passenger railway operator in the Netherlands Our results show the three-phase heuristic finds good solutions for most instances and outperforms a state-of-the-art commercial solver. Y1 - 2023 U6 - https://doi.org/https://doi.org/10.1016/j.cor.2023.106186 VL - 154 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schelten, Uwe A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - A Column Generation Approach to Airline Crew Scheduling N2 - The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel rapid branching'' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH. T3 - ZIB-Report - 05-37 KW - Integer Programming KW - Airline Crew Scheduling KW - Branch and Generate Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8713 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 - Heinz, Stefan A1 - Stephan, Rüdiger A1 - Schlechte, Thomas T1 - Solving Steel Mill Slab Problems with Branch and Price N2 - The steel mill slab design problem from the CSPLib is a binpacking problem that is motivated by an application of the steel industry and that has been widely studied in the constraint programming community. Recently, several people proposed new models and methods to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called multiple knapsack problem with color constraints, originated from the same industrial problem, were discussed in the integer programming community. In particular, a simple integer programming for this problem has been given by Forrest et al. [3]. The aim of this paper is to bring these different studies together. Moreover, we adopt the model of [3] for the steel mill slab problem. Using a state of the art integer program solver, this model is capable to solve all instances of the steel mill slab library, mostly in less than one second, to optimality. We improved, thereby, the solution value of 76 instances. T3 - ZIB-Report - 09-14 KW - steel mill slab problem KW - branch-and-price KW - integer programming Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11260 SN - 1438-0064 ER - TY - GEN A1 - Erol, Berkan A1 - Klemenz, Marc A1 - Schlechte, Thomas A1 - Schultz, Sören A1 - Tanner, Andreas T1 - TTPLIB 2008 - A Library for Train Timetabling Problems N2 - We introduce (TTPlib), a data library for train timetabling problems that can be accessed at http://ttplib.zib.de. In version 1.0, the library contains data related to 50 scenarios. Most instances result from the combination of macroscopic railway networks and several train request sets for the German long distance area containing Hannover, Kassel and Fulda, short denoted by Ha-Ka-Fu. In this paper, we introduce the data concepts of TTPlib, describe the scenarios included in the library and provide a free visualization tool TraVis. T3 - ZIB-Report - 08-19 KW - Fahrplanung KW - Problembibliothek KW - Optimierung KW - Train Timetabling Problem KW - Data Library KW - Optimization Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10732 SN - 1438-0064 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 - Mura, Annette A1 - Schlechte, Thomas T1 - Vickrey Auctions for Railway Tracks N2 - We consider an auction of slots to run trains through a railway network. In contrast to the classical setting for combinatorial auctions, there is not only competition for slots, but slots can mutually exclude each other, such that general conflict constraints on bids arise. This turns the winner determination problem associated with such an auction into a complex combinatorial optimization problem. It also raises a number of auction design questions, in particular, on incentive compatibilty. We propose a single-shot second price auction for railway slots, the Vickrey Track Auction (VTA). We show that this auction is incentive compatible, i.e., rational bidders are always motivated to bid their true valuation, and that it produces efficient allocations, even in the presence of constraints on allocations. These properties are, however, lost when rules on the submission of bids such as, e.g., lowest bids, are imposed. Our results carry over to generalized" Vickrey auctions with combinatorial constraints. T3 - ZIB-Report - 08-34 KW - Vickrey Auktion KW - Fahrplanung KW - Vickrey Auction KW - Track Allocation Problem Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10855 SN - 1438-0064 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 - GEN A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Solving Railway Track Allocation Problems N2 - The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported. T3 - ZIB-Report - 07-20 KW - railway track allocation KW - timetabling KW - column generation Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9631 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 - 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 - Borndörfer, Ralf A1 - Fügenschuh, Armin A1 - Klug, Torsten A1 - Schang, Thilo A1 - Schlechte, Thomas A1 - Schülldorf, Hanno T1 - The Freight Train Routing Problem N2 - 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. T3 - ZIB-Report - 13-36 KW - Mixed-Integer Nonlinear Programming KW - multi-commodity flows KW - freight train routing Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18991 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Railway Track Allocation by Rapid Branching N2 - The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported. T3 - ZIB-Report - 10-22 KW - Trassenallokationsproblem KW - Ganzzahlige Programmierung KW - Rapid-Branching-Heuristik KW - Proximale Bündelmethode KW - Optimization KW - Railway Track Allocation KW - Bundle Method KW - Rapid Branching Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11864 SN - 1438-0064 ER - TY - JOUR 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 JF - Competition and Regulation in Network Industries Y1 - 2006 VL - 1 IS - 2 SP - 163 EP - 196 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 - 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 - GEN A1 - Heinz, Stefan A1 - Schlechte, Thomas A1 - Stephan, Rüdiger A1 - Winkler, Michael T1 - Solving steel mill slab design problems N2 - The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results. Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality. T3 - ZIB-Report - 11-38 KW - steel mill slab design problem KW - multiple knapsack problem with color constraints KW - integer programming KW - set partitioning KW - binpacking with side constraints Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14089 SN - 1438-0064 ER - TY - THES A1 - Schlechte, Thomas T1 - Das Resource-Constraint-Shortest-Path-Problem und seine Anwendung in der ÖPNV-Dienstplanung Y1 - 2003 UR - http://www.zib.de/groetschel/students/Diplom-Schlechte-0311.pdf ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schlechte, Thomas ED - Liebchen, Christian ED - Ahuja, Ravindra ED - Mesa, Juan T1 - Models for Railway Track Allocation T2 - ATMOS 2007 - 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems Y1 - 2007 VL - 07001 PB - Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schlechte, Thomas ED - Ehrgott, Matthias ED - Naujoks, Boris ED - Stewart, Theo ED - Wallenius, Jyrki T1 - Balancing Efficiency and Robustness T2 - MCDM for Sustainable Energy and Transportation Systems Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2008/1105/ PB - Lecture Notes in Economics and Mathematical Systems ER - TY - CHAP A1 - Erol, Berkan A1 - Klemenz, Marc A1 - Schlechte, Thomas A1 - Schultz, Sören A1 - Tanner, Andreas ED - Tomii, A. ED - Allan, J. ED - Arias, E. ED - Brebbia, C. ED - Goodman, C. ED - Rumsey, A. ED - Sciutto, G. T1 - TTPlib 2008 - A Library for Train Timetabling Problems T2 - Computers in Railways XI Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2008/1102/ PB - WIT Press ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Erol, Berkan A1 - Schlechte, Thomas ED - Hansen, I. ED - Wendler, E. ED - Weidmann, U. ED - Lüthi, M. ED - Rodriguez, J. ED - Ricci, S. ED - Kroon, Leo T1 - Optimization of macroscopic train schedules via TS-OPT T2 - Proceedings of the 3rd International Seminar on Railway Operations Modelling and Analysis - Engineering and Optimisation Approaches Y1 - 2009 CY - Zürich, Switzerland ER - TY - CHAP A1 - Schlechte, Thomas A1 - Tanner, Andreas T1 - Railway capacity auctions with dual prices T2 - Selected Proceedings of the 12th World Conference on Transport Research Y1 - 2010 UR - http://opus.kobv.de/zib/volltexte/2010/1233/ ER - TY - GEN A1 - Blanco, Marco A1 - Schlechte, Thomas T1 - Analysis of Micro-Macro Transformations of Railway Networks 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 inconvieniently by underestimating the global optimal value. T3 - ZIB-Report - 13-65 Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42710 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 - 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 - GEN A1 - Fischer, Frank A1 - Schlechte, Thomas T1 - Strong Relaxations for the Train Timetabling Problem using Connected Configurations 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. T3 - ZIB-Report - 17-46 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64743 SN - 1438-0064 ER - TY - GEN A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Kaier, Anton A1 - Maristany de las Casas, Pedro A1 - Schlechte, Thomas A1 - Schlobach, Swen T1 - Cost Projection Methods for the Shortest Path Problem with Crossing Costs N2 - Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds. T3 - ZIB-Report - 17-48 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64817 SN - 1438-0064 ER - TY - GEN A1 - Renken, Malte A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Sahin, Guvenc A1 - Schlechte, Thomas T1 - Demand-Driven Line Planning with Selfish Routing N2 - Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines. T3 - ZIB-Report - 17-38 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64547 SN - 1438-0064 ER - 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 - CHAP A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Kaier, Anton A1 - Maristany de las Casas, Pedro A1 - Schlechte, Thomas A1 - Schlobach, Swen ED - D'Angelo, Gianlorenzo ED - Dollevoet, Twan T1 - Cost Projection Methods for the Shortest Path Problem with Crossing Costs T2 - 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017) N2 - Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds. Y1 - 2017 VL - 59 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Arslan, Oytun A1 - Elijazyfer, Ziena A1 - Güler, Hakan A1 - Renken, Malte A1 - Sahin, Guvenc A1 - Schlechte, Thomas T1 - Line Planning on Path Networks with Application to the Istanbul Metrobüs T2 - Operations Research Proceedings 2016 N2 - Bus rapid transit systems in developing and newly industrialized countries often consist of a trunk with a path topology. On this trunk, several overlapping lines are operated which provide direct connections. The demand varies heavily over the day, with morning and afternoon peaks typically in reverse directions. We propose an integer programming model for this problem, derive a structural property of line plans in the static (or single period) ``unimodal demand'' case, and consider approaches to the solution of the multi-period version that rely on clustering the demand into peak and off-peak service periods. An application to the Metrobüs system of Istanbul is discussed. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-55702-1_32 SP - 235 EP - 241 ER - TY - CHAP A1 - Schwartz, Stephan A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Designing Inspector Rosters with Optimal Strategies T2 - Operations Research Proceedings 2016 N2 - We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-55702-1_30 SP - 217 EP - 223 ER - TY - CHAP A1 - Fischer, Frank A1 - Grimm, Boris A1 - Klug, Torsten A1 - Schlechte, Thomas T1 - A Re-optimization Approach for Train Dispatching T2 - Operations Research Proceedings 2016 N2 - 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. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-55702-1_85 SP - 645 EP - 651 ER - TY - JOUR A1 - Heinz, Stefan A1 - Schlechte, Thomas A1 - Stephan, Rüdiger A1 - Winkler, Michael T1 - Solving steel mill slab design problems JF - Constraints N2 - The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. (INFORMS J Comput 18:129–134, 2006). The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. (INFORMS J Comput 18:129–134, 2006) for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results (Schaus et al., Constraints 16:125–147, 2010). Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality. Y1 - 2012 U6 - https://doi.org/10.1007/s10601-011-9113-8 VL - 17 IS - 1 SP - 39 EP - 50 ER - TY - JOUR A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Brückner, Michael A1 - Hoang, Nam-Dung A1 - Schlechte, Thomas T1 - On the Path Avoiding Forbidden Pairs Polytope JF - Electronic Notes in Discrete Mathematics N2 - Given a directed, acyclic graph, a source and a sink node, and a set of forbidden pairs of arcs, the path avoiding forbidden pairs (PAFP) problem is to find a path that connects the source and sink nodes and contains at most one arc from each forbidden pair. The general version of the problem is NP-hard, but it becomes polynomially solvable for certain topological configurations of the pairs. We present the first polyhedral study of the PAFP problem. We introduce a new family of valid inequalities for the PAFP polytope and show that they are sufficient to provide a complete linear description in the special case where the forbidden pairs satisfy a disjointness property. Furthermore, we show that the number of facets of the PAFP polytope is exponential in the size of the graph, even for the case of a single forbidden pair. Y1 - 2015 U6 - https://doi.org/10.1016/j.endm.2015.07.057 VL - 50 SP - 343 EP - 348 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 - CHAP A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Swarat, Elmar A1 - Weider, Steffen T1 - Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue T2 - Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015) N2 - Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively. Y1 - 2015 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 - 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 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Template based re-optimization of rolling stock rotations T2 - Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015) N2 - Rolling stock, i.e., rail vehicles, are among the most expensive and limited assets of a railway company. They must be used efficiently applying optimization techniques. One important aspect is re-optimization, which is the topic that we consider in this paper. We propose a template concept that allows to compute cost minimal rolling stock rotations under a large variety of re-optimization requirements. Two examples, involving a connection template and a rotation template, are discussed. An implementation within the rolling stock rotation optimizer rotor and computational results for scenarios provided by DB Fernverkehr AG, one of the leading railway operators in Europe, are presented. Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57539 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Fügenschuh, Armin A1 - Klug, Torsten A1 - Schang, Thilo A1 - Schlechte, Thomas A1 - Schülldorf, Hanno T1 - The Freight Train Routing Problem for Congested Railway Networks with Mixed Traffic JF - Transportation Science N2 - 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. Y1 - 2016 U6 - https://doi.org/10.1287/trsc.2015.0656 VL - 50 IS - 2 SP - 408 EP - 423 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Optimal duty rostering for toll enforcement inspectors JF - Annals of Operations Research N2 - We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, we developed a personalized crew rostering model, to schedule the crews of the tours. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The main focus of this paper extends our previous publications on how different requirements for the rostering can be modeled in detail. The second focus is on a bi-criteria analysis of the planning problem to find the balance between the control quality and the roster acceptance. Finally, computational results on real-world instances show the practicability of our method and how different input parameters influence the problem complexity. Y1 - 2016 U6 - https://doi.org/10.1007/s10479-016-2152-1 VL - 252(2) SP - 383 EP - 406 PB - Springer US ET - 252 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 - GEN A1 - Fischer, Frank A1 - Grimm, Boris A1 - Klug, Torsten A1 - Schlechte, Thomas T1 - A Re-optimization Approach for Train Dispatching N2 - 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. T3 - ZIB-Report - 16-49 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60493 SN - 1438-0064 ER - TY - GEN A1 - Schwartz, Stephan A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Designing Inspector Rosters with Optimal Strategies N2 - We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances. T3 - ZIB-Report - 16-65 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61123 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Arslan, Oytun A1 - Elijazyfer, Ziena A1 - Güler, Hakan A1 - Renken, Malte A1 - Sahin, Güvenc A1 - Schlechte, Thomas T1 - Line Planning on Path Networks with Application to the Istanbul Metrobüs N2 - Bus rapid transit systems in developing and newly industrialized countries often consist of a trunk with a path topology. On this trunk, several overlapping lines are operated which provide direct connections. The demand varies heavily over the day, with morning and afternoon peaks typically in reverse directions. We propose an integer programming model for this problem, derive a structural property of line plans in the static (or single period) ``unimodal demand'' case, and consider approaches to the solution of the multi-period version that rely on clustering the demand into peak and off-peak service periods. An application to the Metrobüs system of Istanbul is discussed. T3 - ZIB-Report - 16-38 KW - line planning KW - unimodal demand Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60119 SN - 1438-0064 ER - TY - CHAP A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Kaier, Anton A1 - Schienle, Adam A1 - Schlechte, Thomas A1 - Schlobach, Swen ED - Marc, Goerigk T1 - Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind T2 - 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016) N2 - We study the Flight Planning Problem for a single aircraft, which deals with finding a path of minimal travel time in an airway network. Flight time along arcs is affected by wind speed and direction, which are functions of time. We consider three variants of the problem, which can be modeled as, respectively, a classical shortest path problem in a metric space, a time-dependent shortest path problem with piecewise linear travel time functions, and a time-dependent shortest path problem with piecewise differentiable travel time functions. The shortest path problem and its time-dependent variant have been extensively studied, in particular, for road networks. Airway networks, however, have different characteristics: the average node degree is higher and shortest paths usually have only few arcs. We propose A* algorithms for each of the problem variants. In particular, for the third problem, we introduce an application-specific "super-optimal wind" potential function that overestimates optimal wind conditions on each arc, and establish a linear error bound. We compare the performance of our methods with the standard Dijkstra algorithm and the Contraction Hierarchies (CHs) algorithm. Our computational results on real world instances show that CHs do not perform as well as on road networks. On the other hand, A* guided by our potentials yields very good results. In particular, for the case of piecewise linear travel time functions, we achieve query times about 15 times shorter than CHs. Y1 - 2016 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2016.12 VL - 54 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 - GEN A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Kaier, Anton A1 - Schlechte, Thomas A1 - Schlobach, Swen T1 - The Shortest Path Problem with Crossing Costs N2 - We introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions. The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs. In this paper, we provide a comprehensive analysis of the problem. In particular, we identify efficient exact and approximation algorithms for the cases that are most relevant in practice. T3 - ZIB-Report - 16-70 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61240 SN - 1438-0064 ER - TY - CHAP A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Schade, Stanley T1 - Regularity patterns for rolling stock rotation optimization T2 - 8th International Conference on Applied Operational Research, Proceedings N2 - The operation of railways gives rise to many fundamental optimization problems. One of these problems is to cover a given set of timetabled trips by a set of rolling stock rotations. This is well known as the Rolling Stock Rotation Problem (RSRP). Most approaches in the literature focus primarily on modeling and minimizing the operational costs. However, an essential aspect for the industrial application is mostly neglected. As the RSRP follows timetabling and line planning, where periodicity is a highly desired property, it is also desired to carry over periodic structures to rolling stock rotations and following operations. We call this complex requirement regularity. Regularity turns out to be of essential interest, especially in the industrial scenarios that we tackle in cooperation with DB Fernverkehr AG. Moreover, regularity in the context of the RSRP has not been investigated thoroughly in the literature so far. We introduce three regularity patterns to tackle this requirement, namely regular trips, regular turns, and regular handouts. We present a two-stage approach in order to optimize all three regularity patterns. At first, we integrate regularity patterns into an integer programming approach for the minimization of the operational cost of rolling stock rotations. Afterwards regular handouts are computed. These handouts present the rotations of the first stage in the most regular way. Our computational results (i.e., rolling stock rotations evaluated by planners of DB Fernverkehr AG) show that the three regularity patterns and our concept are a valuable and, moreover, an essential contribution to rolling stock rotation optimization. Y1 - 2016 VL - 8 SP - 28 EP - 32 ER - TY - GEN 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, i.e., vehicle composition, maintenance constraints, and regularity aspects. In industrial applications existing schedules often have to be re-optimized to integrate timetable changes or construction sites. We present an integrated modeling and algorithmic approach for this task as well as computational results for industrial problem instances of DB Fernverkehr AG. T3 - ZIB-Report - 13-60 Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42569 SN - 1438-0064 ER - TY - CHAP A1 - Schade, Stanley A1 - Borndörfer, Ralf A1 - Breuer, Matthias A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Siebeneicher, Patrick T1 - Pattern Detection For Large-Scale Railway Timetables T2 - Proceedings of the IAROR conference RailLille N2 - We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner. Y1 - 2017 ER - TY - CHAP A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schade, Stanley A1 - Schlechte, Thomas T1 - A Propagation Approach to Acyclic Rolling Stock Rotation Optimization T2 - Proceedings of the IAROR conference RailLille N2 - The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach. Y1 - 2017 ER - TY - CHAP A1 - Gilg, Brady A1 - Klug, Torsten A1 - Martienssen, Rosemarie A1 - Paat, Joseph A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Seymen, Sinan A1 - Tesch, Alexander T1 - Conflict-Free Railway Track Assignment at Depots T2 - Proceedings of the IAROR conference RailLille N2 - Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables. Y1 - 2017 ER - TY - GEN A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schade, Stanley A1 - Schlechte, Thomas T1 - A Propagation Approach to Acyclic Rolling Stock Rotation Optimization N2 - The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach. T3 - ZIB-Report - 17-24 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-63930 SN - 1438-0064 ER - TY - GEN A1 - Gilg, Brady A1 - Klug, Torsten A1 - Martienssen, Rosemarie A1 - Paat, Joseph A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Seymen, Sinan A1 - Tesch, Alexander T1 - Conflict-Free Railway Track Assignment at Depots N2 - Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables. T3 - ZIB-Report - 17-23 KW - Depot Planning KW - Railway Track Assignment Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-63843 SN - 1438-0064 ER - TY - GEN A1 - Schade, Stanley A1 - Borndörfer, Ralf A1 - Breuer, Matthias A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Siebeneicher, Patrick T1 - Pattern Detection For Large-Scale Railway Timetables N2 - We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner. T3 - ZIB-Report - 17-17 KW - railway timetables KW - visualization KW - pattern detection Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-63390 SN - 1438-0064 ER - TY - JOUR A1 - Harrod, Steven A1 - Schlechte, Thomas T1 - A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations JF - Transportation Research Part E: Logistics and Transportation Review N2 - 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. Y1 - 2013 U6 - https://doi.org/10.1016/j.tre.2013.04.003 VL - 54 SP - 50 EP - 66 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 - Schlechte, Thomas T1 - Railway Track Allocation - Simulation and Optimization JF - Proceedings of 4th International Seminar on Railway Operations Modelling and Analysis (IAROR) N2 - Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway infrastructure provider. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market. This leads to an increase of slot requests and then it is natural that conflicts occur among them. Furthermore, railway infrastructure networks consist of very expensive assets, even more they are rigid due to the long-term upgrade process. In order to make best use of these valuable infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithmic methodology 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 a general framework to support the integration of simulation and optimization for railway capacity allocation. Y1 - 2011 VL - 4 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Railway Track Allocation -- Simulation, Aggregation, and Optimization JF - Proc. 1st International Workshop on High-speed and Intercity Railways (IWHIR 2011) 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. Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-27963-8 VL - 2 IS - 148 SP - 53 EP - 70 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 - CHAP A1 - Schlechte, Thomas T1 - Railway Track Allocation BT - Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012 T2 - Operations Research Proceedings Y1 - 2012 U6 - https://doi.org/10.1007/978-3-319-00795-314 SP - 15 EP - 20 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Breuer, Matthias A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schade, Stanley A1 - Schlechte, Thomas T1 - Timetable Sparsification by Rolling Stock Rotation Optimization N2 - 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. T3 - ZIB-Report - 17-63 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65948 SN - 1438-0064 ER - TY - CHAP A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Optimization of Rolling Stock Rotations T2 - Handbook of Optimization in the Railway Industry N2 - This chapter shows a successful approach how to model and optimize rolling stock rotations that are required for the operation of a passenger timetable. The underlying mathematical optimization problem is described in detail and solved by RotOR, i.e., a complex optimization algorithm based on linear programming and combinatorial methods. RotOR is used by DB Fernverkehr AG (DBF) in order to optimize intercity express (ICE) rotations for the European high-speed network. We focus on main modeling and solving components, i.e. a hypergraph model and a coarse-to-fine column generation approach. Finally, the chapter concludes with a complex industrial re-optimization application showing the effectiveness of the approach for real world challenges. Y1 - 2018 SN - 978-3-319-72152-1 U6 - https://doi.org/https://doi.org/10.1007/978-3-319-72153-8 VL - 268 SP - 213 EP - 241 PB - Springer International Publishing ER - TY - CHAP A1 - Caimi, Gabrio A1 - Fischer, Frank A1 - Schlechte, Thomas T1 - Railway Track Allocation T2 - Handbook of Optimization in the Railway Industry N2 - This chapter addresses the classical task to decide which train runs on which track in a railway network. In this context a track allocation defines the precise routing of trains through a railway network, which usually has only a limited capacity. Moreover, the departure and arrival times at the visited stations of each train must simultaneously meet several operational and safety requirements. The problem to find the 'best possible' allocation for all trains is called the track allocation problem (TTP). Railway systems can be modeled on a very detailed scale covering the behavior of individual trains and the safety system to a large extent. However, those microscopic models are too big and not scalable to large networks, which make them inappropriate for mathematical optimization on a network wide level. Hence, most network optimization approaches consider simplified, so called macroscopic, models. In the first part we take a look at the challenge to construct a reliable and condensed macroscopic model for the associated microscopic model and to facilitate the transition between both models of different scale. In the main part we focus on the optimization problem for macroscopic models of the railway system. Based on classical graph-theoretical tools the track allocation problem is formulated to determine conflict-free paths in corresponding time-expanded graphs. We present standard integer programming model formulations for the track allocation problem that model resource or block conflicts in terms of packing constraints. In addition, we discuss the role of maximal clique inequalities and the concept of configuration networks. We will also present classical decomposition approaches like Lagrangian relaxation and bundle methods. Furthermore, we will discuss recently developed techniques, e.g., dynamic graph generation. Finally, we will discuss the status quo and show a vision of mathematical optimization to support real world track allocation, i.e. integrated train routing and scheduling, in a data-dominated and digitized railway future. Y1 - 2018 SN - 978-3-319-72152-1 U6 - https://doi.org/https://doi.org/10.1007/978-3-319-72153-8 VL - 268 SP - 141 EP - 160 PB - Springer International Publishing ER - TY - JOUR A1 - Gilg, Brady A1 - Klug, Torsten A1 - Martienssen, Rosemarie A1 - Paat, Joseph A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Seymen, Senan A1 - Tesch, Alexander T1 - Conflict-free railway track assignment at depots JF - Journal of Rail Transport Planning & Management N2 - Managing rolling stock with no passengers aboard is a critical component of railway operations. One aspect of managing rolling stock is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with a fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we show that the TAP is NP-hard and present two integer programming models for solving the TAP. We compare both models on a theoretical level. Moreover, to our knowledge, we consider the first approach that integrates track lengths along with the three most common types of parking tracks FIFO, LIFO and FREE tracks in a common model. Furthermore, to optimize against uncertainty in the arrival times of the trains we extend our models by stochastic and robust modeling techniques. We conclude by giving computational results for both models, observing that they perform well on real timetables. Y1 - 2018 U6 - https://doi.org/10.1016/j.jrtpm.2017.12.004 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 - 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 - 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 - 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 - Schelten, Uwe A1 - Schlechte, Thomas A1 - Weider, Steffen ED - Haasis, Hans-Dietrich T1 - A Column Generation Approach to Airline Crew Scheduling T2 - Operations Research Proceedings 2005 Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2005/871/ SP - 343 EP - 348 PB - Springer-Verlag 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 - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Swarat, Elmar A1 - Weider, Steffen T1 - Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue N2 - Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively. T3 - ZIB-Report - 15-44 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56070 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Optimal Toll Enforcement - an Integration of Vehicle Routing and Duty Rostering N2 - We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method. T3 - ZIB-Report - 13-79 KW - vehicle routing KW - crew rostering KW - integer programming KW - bicriteria optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-45107 SN - 1438-0064 ER - TY - JOUR A1 - Raack, Christian A1 - Raymond, Annie A1 - Schlechte, Thomas A1 - Werner, Axel T1 - Standings in sports competitions using integer programming JF - Journal of Quantitative Analysis in Sports Y1 - 2013 U6 - https://doi.org/10.1515/jqas-2013-0111 VL - 10 IS - 2 SP - 131 EP - 137 PB - De Gruyter ER - TY - CHAP A1 - Sagnol, Guillaume A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar ED - Lavi, Ron T1 - The Price of Spite in Spot-checking games T2 - 7th International Symposium on Algorithmic Game Theory (SAGT'2014) N2 - We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways. Y1 - 2014 SN - 978-3-662-44802-1 U6 - https://doi.org/10.1007/978-3-662-44803-8 N1 - Brief Announcement included in Back Matter p. 293 following VL - 8768 SP - 293 PB - Springer ER - TY - GEN A1 - Sagnol, Guillaume A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - The Price of Spite in Spot-checking games N2 - We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways. T3 - ZIB-Report - 14-38 Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52775 SN - 1438-0064 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 - 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 - Brett, Charles A1 - Hoberg, Rebecca A1 - Pacheco, Meritxell A1 - Smith, Kyle A1 - Borndörfer, Ralf A1 - Euler, Ricardo A1 - Gamrath, Gerwin A1 - Grimm, Boris A1 - Heismann, Olga A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Tesch, Alexander T1 - G-RIPS 2014 RailLab - Towards robust rolling stock rotations N2 - The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an opportunity for high-achieving graduate-level students to work in teams on a real-world research project proposed by a sponsor from industry or the public sector. Each G-RIPS team consists of four international students (two from the US and two from European universities), an academic mentor, and an industrial sponsor. This is the report of the Rail-Lab project on the definition and integration of robustness aspects into optimizing rolling stock schedules. In general, there is a trade-off for complex systems between robustness and efficiency. The ambitious goal was to explore this trade-off by implementing numerical simulations and developing analytic models. In rolling stock planning a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects, have to be considered in an integrated model. General hypergraphs provide the modeling power to tackle those requirements. Furthermore, integer programming approaches are able to produce high quality solutions for the deterministic problem. When stochastic time delays are considered, the mathematical programming problem is much more complex and presents additional challenges. Thus, we started with a basic variant of the deterministic case, i.e., we are only considering hypergraphs representing vehicle composition and regularity. We transfered solution approaches for robust optimization from the airline industry to the setting of railways and attained a reasonable measure of robustness. Finally, we present and discuss different methods to optimize this robustness measure. T3 - ZIB-Report - 14-34 KW - robust optimization, rolling stock planning Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53475 SN - 1438-0064 N1 - ZIB-Report 14-34 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 - GEN A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Re-optimizing ICE Rotations after a Tunnel Breakdown near Rastatt N2 - Planning rolling stock movements in industrial passenger railway applications isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for the ICE high speed fleet of DB Fernverkehr AG one of the largest passenger railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended. T3 - ZIB-Report - 19-02 KW - case study KW - re-optimization KW - railway rolling stock optimization KW - mixed integer programming Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73976 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Schlechte, Thomas T1 - Re-optimizing ICE Rotations after a Tunnel Breakdown near Rastatt T2 - Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrköping 2019 N2 - Planning rolling stock movements in industrial passenger railway applications isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for the ICE high speed fleet of DB Fernverkehr AG one of the largest passenger railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended. Y1 - 2019 UR - http://www.ep.liu.se/ecp/article.asp?issue=069&article=011&volume= SN - 978-91-7929-992-7 SN - 1650-3686 VL - Linköping Electronic Conference Proceedings IS - 069 SP - 160 EP - 168 PB - Linköping University Electronic Press, Linköpings universitet CY - Linköping, Sweden ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Optimization of handouts for rolling stock rotations JF - Journal of Rail Transport Planning & Management 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. Y1 - 2019 U6 - https://doi.org/10.1016/j.jrtpm.2019.02.001 IS - 10 SP - 1 EP - 8 ER - TY - GEN A1 - Sahin, Guvenc A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Multi-Period Line Planning with Resource Transfers N2 - Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with transfer of resources during a finite length planning horizon of multiple periods. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of line type designs and question the choice of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions. T3 - ZIB-Report - 19-51 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74662 SN - 1438-0064 ER - TY - CHAP A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas ED - Cacchiani, Valentina ED - Marchetti-Spaccamela, Alberto T1 - A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance T2 - 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) N2 - 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óti and Kroon, 2005; Gábor Maró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ö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. Y1 - 2019 UR - https://drops.dagstuhl.de/opus/volltexte/2019/11413/ U6 - https://doi.org/10.4230/OASIcs.ATMOS.2019.1 VL - 75 SP - 1:1 EP - 1:12 PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany ER - TY - GEN A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance T2 - 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) N2 - 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ö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. T3 - ZIB-Report - 19-61 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-75501 SN - 1438-0064 ER - TY - CHAP A1 - Berthold, Timo A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schade, Stanley A1 - Schlechte, Thomas T1 - Strategic Planning of Rolling Stock Rotations for Public Tenders T2 - Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrköping 2019 N2 - 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. Y1 - 2019 UR - http://www.ep.liu.se/ecp/article.asp?issue=069&article=009&volume= SN - 978-91-7929-992-7 SN - 1650-3686 VL - Linköping Electronic Conference Proceedings IS - 069 SP - 148 EP - 159 PB - Linköping University Electronic Press, Linköpings universitet 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 - CHAP A1 - Renken, Malte A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Sahin, Guvenc A1 - Schlechte, Thomas T1 - Demand-Driven Line Planning with Selfish Routing T2 - Operations Research Proceedings 2017 N2 - Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6_91 SP - 687 EP - 692 PB - Springer International Publishing ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Breuer, Matthias A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schade, Stanley A1 - Schlechte, Thomas T1 - Timetable Sparsification by Rolling Stock Rotation Optimization T2 - Operations Research 2017 N2 - 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. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6_96 SP - 723 EP - 728 PB - Springer International Publishing ER - TY - CHAP A1 - Gamrath, Gerwin A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - An LP-based heuristic for Inspector Scheduling T2 - Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021: Volume I N2 - 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. Y1 - 2021 UR - https://patatconference.org/patat2020/proceedings/ VL - 1 SP - 77 EP - 86 ER - TY - JOUR A1 - Schlechte, Thomas A1 - Borndörfer, Ralf A1 - Denißen, Jonas A1 - Heller, Simon A1 - Klug, Torsten A1 - Küpper, Michael A1 - Lindner, Niels A1 - Reuther, Markus A1 - Söhlke, Andreas A1 - Steadman, William T1 - Timetable Optimization for a Moving Block System JF - Journal of Rail Transport Planning & Management N2 - 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. Y1 - 2022 U6 - https://doi.org/10.1016/j.jrtpm.2022.100315 SN - 2210-9706 VL - 22 SP - 100315 ER - TY - GEN A1 - Fügenschuh, Armin A1 - Junosza-Szaniawski, Konstanty A1 - Klug, Torsten A1 - Kwasiborski, Slawomir A1 - Schlechte, Thomas T1 - Fastest, average and quantile schedule N2 - 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. T3 - ZIB-Report - 14-49 KW - eulerian multigraphs KW - scheduling Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53592 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Denißen, Jonas A1 - Heller, Simon A1 - Klug, Torsten A1 - Küpper, Michael A1 - Lindner, Niels A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Söhlke, Andreas A1 - Steadman, William T1 - Microscopic Timetable Optimization for a Moving Block System N2 - 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. T3 - ZIB-Report - 21-13 KW - Moving Block KW - Railway Track Allocation KW - Railway Timetabling KW - Train Routing Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82547 SN - 1438-0064 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 - TY - CHAP A1 - Klug, Torsten A1 - Junosza-Szaniawski, Konstanty A1 - Kwasiborski, Slawomir A1 - Fügenschuh, Armin A1 - Schlechte, Thomas T1 - Fastest, Average and Quantile Schedule T2 - SOFSEM 2015: Theory and Practice of Computer Science N2 - 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. KW - scheduling KW - eulerian multigraphs Y1 - 2015 U6 - https://doi.org/10.1007/978-3-662-46078-8_17 SP - 201 EP - 216 PB - Springer Berlin Heidelberg ER - 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 - Simulation and Optimization N2 - Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway infrastructure provider. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market. This leads to an increase of slot requests and then it is natural that conflicts occur among them. Furthermore, railway infrastructure networks consist of very expensive assets, even more they are rigid due to the long-term upgrade process. In order to make best use of these valuable infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithmic methodology 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 a general framework to support the integration of simulation and optimization for railway capacity allocation. T3 - ZIB-Report - 11-32 KW - railway models KW - railway capacity KW - track allocation framework Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13632 SN - 1438-0064 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 - Harrod, Steven A1 - Schlechte, Thomas T1 - A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations N2 - 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, HGF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and HGF 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. T3 - ZIB-Report - 13-18 KW - Railway Scheduling KW - Train Timetabling KW - Track Allocation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17946 SN - 1438-0064 ER - TY - GEN A1 - Raack, Christian A1 - Raymond, Annie A1 - Werner, Axel A1 - Schlechte, Thomas T1 - Integer Programming and Sports Rankings N2 - Sports rankings are obtained by applying a system of rules to evaluate the performance of the participants in a competition. We consider rankings that result from assigning an ordinal rank to each competitor according to their performance. We develop an integer programming model for rankings that allows us to calculate the number of points needed to guarantee a team the ith position, as well as the minimum number of points that could yield the ith place. The model is very general and can thus be applied to many types of sports. We discuss examples coming from football (soccer), ice hockey, and Formula~1. We answer various questions and debunk a few myths along the way. Are 40 points enough to avoid relegation in the Bundesliga? Do 95 points guarantee the participation of a team in the NHL playoffs? Moreover, in the season restructuration currently under consideration in the NHL, will it be easier or harder to access the playoffs? Is it possible to win the Formula~1 World Championship without winning at least one race or without even climbing once on the podium? Finally, we observe that the optimal solutions of the aforementioned model are associated to extreme situations which are unlikely to happen. Thus, to get closer to realistic scenarios, we enhance the model by adding some constraints inferred from the results of the previous years. T3 - ZIB-Report - 13-19 KW - sport ranking KW - integer programming Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18068 SN - 1438-0064 ER - TY - CHAP A1 - Klug, Torsten A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Does Laziness Pay Off? - A Lazy-Constraint Approach to Timetabling T2 - 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) N2 - 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. Y1 - 2022 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2022.11 VL - 106 SP - 11:1 EP - 11:8 PB - Schloss Dagstuhl -- Leibniz-Zentrum für Informatik ER - TY - JOUR A1 - Sahin, Guvenc A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Multi-period line planning with resource transfers JF - Transportation Research Part C: Emerging Technologies N2 - Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. We use real-life public transportation network data for our computational results. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions. Y1 - 2020 U6 - https://doi.org/10.1016/j.trc.2020.102726 VL - 119 SP - 102726 ER - TY - GEN A1 - Schade, Stanley A1 - Schlechte, Thomas A1 - Witzig, Jakob T1 - Structure-based Decomposition for Pattern-Detection for Railway Timetables N2 - We consider the problem of pattern detection in large scale railway timetables. This problem arises in rolling stock optimization planning in order to identify invariant sections of the timetable for which a cyclic rotation plan is adequate. We propose a dual reduction technique which leads to an decomposition and enumeration method. Computational results for real world instances demonstrate that the method is able to produce optimal solutions as fast as standard MIP solvers. T3 - ZIB-Report - 17-40 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64525 SN - 1438-0064 ER - TY - CHAP A1 - Schade, Stanley A1 - Schlechte, Thomas A1 - Witzig, Jakob T1 - Structure-based Decomposition for Pattern-Detection for Railway Timetables T2 - Operations Research Proceedings 2017 N2 - We consider the problem of pattern detection in large scale railway timetables. This problem arises in rolling stock optimization planning in order to identify invariant sections of the timetable for which a cyclic rotation plan is adequate. We propose a dual reduction technique which leads to an decomposition and enumeration method. Computational results for real world instances demonstrate that the method is able to produce optimal solutions as fast as standard MIP solvers. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6_95 SP - 715 EP - 721 PB - Springer International Publishing ER - TY - CHAP A1 - Şahin, Güvenç A1 - Lindner, Niels A1 - Schlechte, Thomas ED - Pardalos, P. M. ED - Prokopyev, O. A. T1 - Line Planning Problem T2 - Encyclopedia of Optimization Y1 - 2023 SN - 978-3-030-54621-2 U6 - https://doi.org/10.1007/978-3-030-54621-2_782-1 SP - 1 EP - 6 PB - Springer International Publishing CY - Cham ER - TY - GEN A1 - Schlechte, Thomas A1 - Blome, Christian A1 - Gerber, Stefan A1 - Hauser, Stefan A1 - Kasten, Jens A1 - Müller, Gilbert A1 - Schulz, Christof A1 - Thüring, Michel A1 - Weider, Steffen T1 - The Bouquet of Features in Rolling Stock Rotation Planning T2 - Conference Proceedings RailBelgrade 2023 N2 - Rolling stock is one of the major assets for a railway transportation company. Hence, their utilization should be as efficiently and effectively as possible. Railway undertakings are facing rolling stock scheduling challenges in different forms - from rather idealized weekly strategic problems to very concrete operational ones. Thus, a vast of optimization models with different features and objectives exist. Thorlacius et al. (2015) provides a comprehensive and valuable collection on technical requirements, models, and methods considered in the scientific literature. We contribute with an update including recent works. The main focus of the paper is to present a classification and elaboration of the major features which our solver R-OPT is able to handle. Moreover, the basic optimization model and algorithmic ingredients of R-OPT are discussed. Finally, we present computational results for a cargo application at SBB CARGO AG and other railway undertakings for passenger traffic in Europe to show the capabilities of R-OPT. Y1 - 2023 UR - https://easychair.org/publications/preprint/Nms6 ER -