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 - CHAP A1 - Borndörfer, Ralf A1 - Neumann, Marika T1 - Linienoptimierung - reif für die Praxis? T2 - Heureka '11 : Optimierung in Verkehr und Transport 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. Y1 - 2011 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika ED - Frigioni, Daniele ED - Stiller, Sebastian T1 - A Configuration Model for the Line Planning Problem T2 - ATMOS 2013 - 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems Y1 - 2013 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2013.68 VL - 33 SP - 68 EP - 79 PB - Schloss Dagstuhl--Leibniz-Zentrum für Informatik ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Friedow, Isabel A1 - Karbstein, Marika T1 - Optimierung des Linienplans 2010 in Potsdam JF - Der Nahverkehr Y1 - 2012 VL - 30 IS - 4 SP - 34 EP - 39 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - A Configuration Model for the Line Planning Problem N2 - We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model. T3 - ZIB-Report - 13-40 KW - combinatorial optimization KW - polyhedral combinatorics KW - line planning Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-41903 SN - 1438-0064 ER - TY - JOUR A1 - Karbstein, Marika T1 - Ohne Umsteigen ans Ziel JF - OR News N2 - Die Anforderungen an das Liniennetz eines Verkehrsunternehmens sind vielfältig: kurze Fahrzeiten, viele Direktverbindungen und geringe Kosten. Mathematische Optimierungsmethoden können die Planung von Liniennetzen unterstützen und beste Kompromisse bzgl. aller Anforderungen berechnen. Y1 - 2014 VL - 52 SP - 12 EP - 14 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Borndörfer, Ralf A1 - Grima, Mickaël A1 - Seeling, Matthes A1 - Spies, Claudia T1 - Robust Allocation of Operating Rooms with Lognormal case Durations N2 - The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. In this article, we formulate this problem as a job shop scheduling problem, in which the job durations follow a lognormal distribution. We propose to use a cutting-plane approach to solve a robust version of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations to solve the subproblems that identify worst-case scenarios and generate cut inequalities. The procedure is illustrated with numerical experiments based on real data from a major hospital in Berlin. T3 - ZIB-Report - 16-16 KW - robust optimization KW - lognormal duration KW - Hilbert's projective metric Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-58497 UR - http://www.pms2016.com/congreso/ficha.en.html SN - 1438-0064 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 - CHAP A1 - Karbstein, Marika T1 - Integrated Line Planning and Passenger Routing: Connectivity and Transfers T2 - Operations Research Proceedings 2014 N2 - The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity. In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-28697-6_37 SP - 263 EP - 269 ER - TY - CHAP A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf T1 - An Approximation Result for Matchings in Partitioned Hypergraphs T2 - Operations Research Proceedings 2014 N2 - We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most $2\sqrt{d}$ for partitioned hypergraphs with parts of size $\leq d$. Furthermore, we show that this bound cannot be improved to $\mathcal{O}(d^{0.5-\epsilon})$. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-28697-6_5 SP - 31 EP - 36 PB - Springer International Publishing ER - TY - JOUR A1 - Hoppmann, Heide T1 - Linienplanung und Minimale Konfigurationen JF - OR News Y1 - 2015 VL - 55 SP - 22 EP - 23 ER - TY - CHAP A1 - Liebchen, Christian A1 - Swarat, Elmar ED - Fischetti, Matteo ED - Widmayer, Peter T1 - The Second Chvatal Closure Can Yield Better Railway Timetables T2 - ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-15802 UR - http://drops.dagstuhl.de/opus/volltexte/2008/1580 PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany CY - Dagstuhl, Germany 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 - 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 - 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 - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Der Schnellste Weg zum Ziel N2 - Wir geben eine Einführung in die Mathematik von und mit Wegen. Nicht auf dem kürzesten, aber auf einem hoffentlich kurzweiligen Weg! T3 - ZIB-Report - SC-99-32 KW - Kürzeste Wege KW - Kombinatorische Optimierung KW - Operations Research Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4209 ER - TY - GEN A1 - Schwartz, Stephan A1 - Borndörfer, Ralf A1 - Bartz, Gerald T1 - The Graph Segmentation Problem N2 - We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest. T3 - ZIB-Report - 16-53 KW - toll billing KW - graph segmentation KW - combinatorial optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60750 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Löbel, Fabian T1 - The Modulo Network Simplex with Integrated Passenger Routing T2 - Operations Research Proceedings 2016 N2 - Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration. Y1 - 2016 ER -