TY - GEN A1 - Borndörfer, Ralf A1 - Dovica, Ivan A1 - Nowak, Ivo A1 - Schickinger, Thomas T1 - Robust Tail Assignment N2 - We propose an efficient column generation method to minimize the probability of delay propagations along aircraft rotations. In this way, delay resistant schedules can be constructed. Computational results for large-scale real-world problems demonstrate substantial punctuality improvements. The method can be generalized to crew and integrated scheduling problems. T3 - ZIB-Report - 10-08 KW - Flugzeugumlaufplanung KW - robuste Optimierung KW - Spaltenerzeugung KW - Tail Assignment KW - Robust Optimization KW - Column Generation Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11707 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Neumann, Marika T1 - Models for Line Planning with Transfers N2 - We propose a novel integer programming approach to transfer minimization for line planning problems in public transit. The idea is to incorporate penalties for transfers that are induced by “connection capacities” into the construction of the passenger paths. We show that such penalties can be dealt with by a combination of shortest and constrained shortest path algorithms such that the pricing problem for passenger paths can be solved efficiently. Connection capacity penalties (under)estimate the true transfer times. This error is, however, not a problem in practice. We show in a computational comparison with two standard models on a real-world scenario that our approach can be used to minimize passenger travel and transfer times for large-scale line planning problems with accurate results. T3 - ZIB-Report - 10-11 KW - Linienplanung KW - Umsteigen KW - Ganzzahlige Programmierung KW - Kombinatorische Optimierung KW - line planning KW - transfers KW - integer programming KW - combinatorial optimization Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11742 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Neumann, Marika T1 - Linienoptimierung - reif für die Praxis? N2 - Wir stellen in dieser Arbeit ein mathematisches Optimierungsmodell zur Bestimmung eines optimalen Linienplans vor, das sowohl die Fahrzeiten und die Anzahl der Umstiege berücksichtigt als auch die Kosten des Liniennetzes. Dieses Modell deckt wichtige praktische Anforderungen ab, die in einem gemeinsamen Projekt mit den Verkehrsbetrieben in Potsdam (ViP) formuliert wurden. In diesem Projekt wurde der Linienplan 2010 für Potsdam entwickelt. Unsere Berechnungen zeigen, dass die mathematische Optimierung in nichts einer "Handplanung" des Liniennetzes nachsteht. Im Gegenteil, mit Hilfe des Optimierungsprogramms ist es möglich, durch Veränderung der Parameter mehrere verschiedene Szenarien zu berechnen, miteinander zu vergleichen und Aussagen über minimale Kosten und Fahrzeiten zu machen. T3 - ZIB-Report - 10-20 KW - Linienplanung KW - Optimierung Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11832 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - The Quickest Path to the Goal N2 - We provide an introduction into the mathematics of and with paths. Not on the shortest, but hopefully on an entertaining path! T3 - ZIB-Report - 10-21 KW - shortest paths KW - combinatorial optimization KW - operations research Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11840 SN - 1438-0064 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 - 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 -