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 - Borndörfer, Ralf A1 - Karbstein, Marika T1 - A Note on Menger's Theorem for Hypergraphs N2 - We prove the companion Theorem to Menger's Theorem for hypergraphs. This result gives rise to a new class of blocking pairs of ideal matrices, that generalize the incidence matrices of cuts and paths. T3 - ZIB-Report - 12-03 KW - ideal matrices Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14471 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika ED - Delling, Daniel ED - Liberti, Leo T1 - A Direct Connection Approach to Integrated Line Planning and Passenger Routing T2 - ATMOS 2012 - 12th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems N2 - The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances. T3 - ZIB-Report - 12-29 KW - combinatorial optimization KW - integer programming KW - line planning KW - transfers Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15812 SN - 1438-0064 VL - 25 SP - 47 EP - 57 PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik ER - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - A Case Study on Optimizing Toll Enforcements on Motorways N2 - In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach. T3 - ZIB-Report - 12-21 KW - Vehicle Routing Problem KW - Duty Rostering KW - Integer Programming KW - Operations Research Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15498 SN - 1438-0064 ER - 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 - 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 T1 - Discrete Optimization in Public Transportation N2 - The mathematical treatment of planning problems in public transit has made significant advances in the last decade. Among others, the classical problems of vehicle and crew scheduling can nowadays be solved on a routine basis using combinatorial optimization methods. This is not yet the case for problems that pertain to the design of public transit networks, and for the problems of operations control that address the implementation of a schedule in the presence of disturbances. The article gives a sketch of the state and important developments in these areas, and it addresses important challenges. The vision is that mathematical tools of computer aided scheduling (CAS) will soon play a similar role in the design and operation of public transport systems as CAD systems in manufacturing. N2 - Die mathematische Behandlung von Planungsproblemen im öffentlichen Verkehr hat im letzten Jahrzehnt große Fortschritte gemacht. Klassische Probleme wie die Umlauf- und die Dienstplanung können heutzutage routinemäßig mit kombinatorischen Optimierungsmethoden gelöst werden. Die Behandlung von Problemen der Angebotsplanung und der Betriebssteuerung sind dagegen noch nicht ganz auf diesem Stand. Dieser Artikel gibt einen Überblick über den Stand der Forschung, über wichtige Entwicklungen und einige Herausforderungen in diesem Gebiet. Die Vision ist, dass mathematische Planungswerkzeuge im öffentlichen Verkehr (Computer Aided Scheduling, CAS) in Zukunft eine ähnliche Rolle spielen werden wie CAD-Systeme in der industriellen Fertigung. T3 - ZIB-Report - 08-56 KW - Öffentlicher Verkehr KW - Nahverkehr KW - Optimierung KW - Public Transit KW - Optimization Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11207 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Cardonha, Carlos T1 - A Set Partitioning Approach to Shunting N2 - The Vehicle Positioning Problem (VPP) is a classical combinatorial optimization problem in public transport planning. A number of models and approaches have been suggested in the literature, which work for small problems, but not for large ones. We propose in this article a novel set partitioning model and an associated column generation solution approach for the VPP. The model provides a tight linear description of the problem. The pricing problem, and hence the LP relaxation itself, can be solved in polynomial resp. pseudo-polynomial time for some versions of the problems. T3 - ZIB-Report - 09-18 KW - integer programming KW - set partitioning KW - combinatorial packing KW - vehicle positioning Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11326 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Cardonha, Carlos T1 - A Binary Quadratic Programming Approach to the Vehicle Positioning Problem N2 - The Vehicle Positioning Problem (VPP) consists of the assignment of vehicles (buses, trams or trains) of a public transport or railway company to parking positions in a depot and to timetabled trips. Such companies have many different types of vehicles, and each trip can be performed only by vehicles of some of these types. These assignments are non-trivial due to the topology of depots. The parking positions are organized in tracks, which work as one- or two-sided stacks or queues. If a required type of vehicle is not available in the front of any track, shunting movements must be performed in order to change vehicles' positions, which is undesirable and should be avoided. In this text we present integer linear and non-linear programming formulations for some versions of the problem and compare them from a theoretical and a computational point of view. T3 - ZIB-Report - 09-12 KW - quadratic programming KW - integer programming KW - nonlinear programming KW - vehicle positioning Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11242 SN - 1438-0064 ER -