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 - 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 - 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 - 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 - 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 - 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 - 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 -