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 - 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 - JOUR A1 - Borndörfer, Ralf A1 - Dittbrenner, Bastian A1 - Langenhan, Andreas A1 - Seidl, Stephan A1 - Weider, Steffen T1 - Integrierte Dienst- und Dienstreihenfolgeplanung zur Erhöhung der Fahrerzufriedenheit JF - Straßenverkehrstechnik Y1 - 2014 IS - 9 SP - 583 EP - 591 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Löbel, Fabian T1 - The Modulo Network Simplex with Integrated Passenger Routing 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. T3 - ZIB-Report - 16-43 KW - periodic timetabling, modulo network simplex, passenger routing Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60319 SN - 1438-0064 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 - Borndörfer, Ralf A1 - Karbstein, Marika T1 - Metric Inequalities for Routings on Direct Connections with Application in Line Planning N2 - We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows. The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers. T3 - ZIB-Report - 15-07 KW - combinatorial optimization KW - integer programming KW - line planning KW - transfers KW - direct connection KW - metric inequalities Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53507 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 - THES A1 - Borndörfer, Ralf T1 - Mathematical Optimization and Public Transportation N2 - This cumulative thesis collects the following six papers for obtaining the habilitation at the Technische Universität Berlin, Fakultät II – Mathematik und Naturwissenschaften: (1) Set packing relaxations of some integer programs. (2) Combinatorial packing problems. (3) Decomposing matrices into blocks. (4) A bundle method for integrated multi-depot vehicle and duty scheduling in public transit. (5) Models for railway track allocation. (6) A column-generation approach to line planning in public transport. Some changes were made to the papers compared to the published versions. These pertain to layout unifications, i.e., common numbering, figure, table, and chapter head layout. There were no changes with respect to notation or symbols, but some typos have been eliminated, references updated, and some links and an index was added. The mathematical content is identical. The papers are about the optimization of public transportation systems, i.e., bus networks, railways, and airlines, and its mathematical foundations, i.e., the theory of packing problems. The papers discuss mathematical models, theoretical analyses, algorithmic approaches, and computational aspects of and to problems in this area. Papers 1, 2, and 3 are theoretical. They aim at establishing a theory of packing problems as a general framework that can be used to study traffic optimization problems. Indeed, traffic optimization problems can often be modelled as path packing, partitioning, or covering problems, which lead directly to set packing, partitioning, and covering models. Such models are used in papers 4, 5, and 6 to study a variety of problems concerning the planning of line systems, buses, trains, and crews. The common aim is always to exploit as many degrees of freedom as possible, both at the level of the individual problems by using large-scale integer programming techniques, as well as on a higher level by integrating hitherto separate steps in the planning process. KW - set packing KW - set partitioning KW - set covering KW - polyhedral combinatorics KW - public transport KW - railways Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13613 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 - Friedow, Isabel A1 - Karbstein, Marika T1 - Optimierung des Linienplans 2010 in Potsdam N2 - Im Zuge der Übernahme von 6 Linien der Havelbus Verkehrsgesellschaft mbH durch die ViP Verkehr in Potsdam GmbH ergab sich 2009 die Notwendigkeit der Entwicklung eines neuen Linien- und Taktplans für das Jahr 2010. Das Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) entwickelt in einem Projekt des DFG-Forschungszentrums Matheon ein Verfahren zur mathematischen Linienoptimierung. Dieses Tool wurde bei der Optimierung des ViP Linienplans 2010 in einer projektbegleitenden Studie eingesetzt, um Alternativen bei verschiedenen Planungs- und Zielvorgaben auszuloten. In dem Artikel wird eine Auswertung der Ergebnisse mit dem Verkehrsanalysesystem Visum der PTV AG beschrieben. Die Auswertungen bestätigen, dass mit Hilfe von mathematischer Optimierung eine weitere Verkürzung der Reisezeit um 1%, eine als um 6% verkürzt empfundene Reisezeit, 10% weniger Fahrzeit im Fahrzeug und eine gleichzeitige Kostenreduktion um 5% möglich sind. T3 - ZIB-Report - 12-04 KW - Fallstudie KW - Linienplan KW - Optimierung Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14486 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Heismann, Olga T1 - Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning N2 - Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially. T3 - ZIB-Report - 11-46 KW - hyperassignments KW - vehicle rotation planning Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14564 UR - http://link.springer.com/chapter/10.1007%2F978-3-642-29210-1_10 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 - 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 - Neumann, Marika A1 - Pfetsch, Marc ED - Fleischmann, Bernhard ED - Borgwardt, Karl ED - Klein, Robert ED - Tuma, Axel T1 - The Line Connectivity Problem T2 - Operations Research Proceedings 2008 Y1 - 2009 UR - http://opus.kobv.de/zib/volltexte/2008/1117/ SP - 557 EP - 562 PB - Springer-Verlag ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas A1 - Weider, Steffen T1 - Integrierte Umlauf- und Dienstplanung im öffentlichen Nahverkehr T2 - Neue Mathematische Verfahren in Industrie und Dienstleistungen Y1 - 2001 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Dienstplanung im öffentlichen Nahverkehr T2 - Mathematische Verfahren zur Lösung von Problemstellungen in Industrie und Wirtschaft Y1 - 1997 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Umlaufplanung im öffentlichen Nahverkehr T2 - Anwendungsorientierte Verbundprojekte auf dem Gebiet der Mathematik Y1 - 1994 ER - TY - BOOK A1 - Borndörfer, Ralf T1 - Mathematical Optimization and Public Transportation Y1 - 2010 PB - TU Berlin ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian ED - Wilson, Nigel T1 - Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System T2 - Proceedings of the 7th International Workshop on Computer-Aided Transit Scheduling Y1 - 1999 U6 - https://doi.org/10.1007/978-3-642-85970-0_19 SP - 391 EP - 422 PB - Springer Verlag CY - Berlin ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Strubbe, Uwe A1 - Völker, Manfred T1 - Zielorientierte Dienstplanoptimierung T2 - Heureka ’99 Y1 - 1999 UR - http://opus.kobv.de/zib/volltexte/1998/385/ SP - 171 EP - 194 PB - Forschungsgesellschaft für Strassen- und Verkehrswesen CY - Köln ER - TY - GEN A1 - Borndörfer, Ralf T1 - Optimierung im Nahverkehr Y1 - 2000 UR - http://www.kompetenznetze.de/inhaltnf\_b1\_c2\_s2\_e1\_d0\_t102\_g14\_n11\_t102\_n11.htm PB - Forschungs- und Anwendungsverbund Verkehr & Initiativgemeinschaft Außeruniversitärer Forschungseinrichtungen in Adlershof e.V. ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - Stable-Set and Other Techniques for Frequency Assignment Problems T2 - Anais da I Oficina Nacional em Problemas de Corte & Empacotamento Y1 - 1996 SP - 17 EP - 21 PB - Universidade de São Paulo, Instituto de Matemática e Estatística ER - TY - THES A1 - Borndörfer, Ralf T1 - Aspects of Set Packing, Partitioning, and Covering Y1 - 1998 UR - http://opus.kobv.de/zib/volltexte/1998/1028/ ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas T1 - Dienstplanoptimierung im ÖPNV Y1 - 2000 UR - http://www.uni-duisburg.de/FB11/PUBL/PRPLIST/prp00.html ER - TY - THES A1 - Borndörfer, Ralf T1 - Mengenpartitionen und ihre Anwendung auf ein Maschinenbelegungsproblem Y1 - 1991 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 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc ED - Fischetti, Matteo ED - Widmayer, Peter T1 - Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System T2 - ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems Y1 - 2008 UR - http://drops.dagstuhl.de/opus/volltexte/2008/1580 PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany CY - Dagstuhl, Germany ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Weider, Steffen ED - Hickman, Mark ED - Mirchandani, Pitu ED - Voß, Stefan T1 - A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit T2 - Computer-aided Systems in Public Transport Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2004/790/ VL - 600 SP - 3 EP - 24 PB - Springer-Verlag 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 - CHAP A1 - Pfetsch, Marc A1 - Borndörfer, Ralf ED - Haasis, Hans-Dietrich T1 - Routing in Line Planning for Public Transportation T2 - Operations Research Proceedings 2005 Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2005/870/ SP - 405 EP - 410 PB - Springer-Verlag ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Weider, Steffen T1 - Integrierte Umlauf- und Dienstplanung im Öffentlichen Verkehr T2 - Heureka ’02 Y1 - 2002 UR - http://opus.kobv.de/zib/volltexte/2002/678/ SP - 77 EP - 98 PB - Forschungsgesellschaft für Straßen- und Verkehrswesen CY - Köln 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 - Neumann, Marika A1 - Pfetsch, Marc T1 - Angebotsplanung im öffentlichen Nahverkehr T2 - HEUREKA’08 Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2008/1084/ PB - FGSV Verlag ER - TY - GEN A1 - Borndörfer, Ralf ED - Grötschel, Martin T1 - Combinatorial Packing Problems T2 - The Sharpest Cut – The Impact of Manfred Padberg and His Work Y1 - 2004 UR - http://opus.kobv.de/zib/volltexte/2003/726/ SP - 19 EP - 32 PB - SIAM CY - Philadelphia ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Liebchen, Christian ED - Kalcsics, Jörg ED - Nickel, Stefan T1 - When Periodic Timetables are Suboptimal T2 - Operations Research Proceedings 2007 Y1 - 2008 SP - 449 EP - 454 PB - SPRINGER ER - TY - GEN A1 - Scheumann, Rene A1 - Fügenschuh, Armin A1 - Schenker, Sebastian A1 - Vierhaus, Ingmar A1 - Borndörfer, Ralf A1 - Finkbeiner, Matthias T1 - Global Manufacturing: How to Use Mathematical Optimisation Methods to Transform to Sustainable Value Creation N2 - It is clear that a transformation to sustainable value creation is needed, because business as usual is not an option for preserving competitive advantages of leading industries. What does that mean? This contribution proposes possible approaches for a shift in existing manufacturing paradigms. In a first step, sustainability aspects from the German Sustainability Strategy and from the tools of life cycle sustainability assessment are chosen to match areas of a value creation process. Within these aspects are indicators, which can be measured within a manufacturing process. Once these data are obtained they can be used to set up a mathematical linear pulse model of manufacturing in order to analyse the evolution of the system over time, that is the transition process, by using a system dynamics approach. An increase of technology development by a factor of 2 leads to an increase of manufacturing but also to an increase of climate change. Compensation measures need to be taken. This can be done by e.g. taking money from the GDP (as an indicator of the aspect ``macroeconomic performance''). The value of the arc from that building block towards climate change must then be increased by a factor of 10. The choice of independent and representative indicators or aspects shall be validated and double-checked for their significance with the help of multi-criteria mixed-integer programming optimisation methods. T3 - ZIB-Report - 12-28 KW - Multi-Criteria Optimisation KW - Sustainability Indicator KW - System Dynamics KW - Value Creation Process Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15703 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 - 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 - 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 - 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 - 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 - 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 - 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 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - A Case Study on Optimizing Toll Enforcements on Motorways T2 - 3rd Student Conference on Operational Research 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. Y1 - 2012 U6 - https://doi.org/10.4230/OASIcs.SCOR.2012.1 VL - 22 SP - 1 EP - 10 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 - 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 - CHAP A1 - Borndörfer, Ralf A1 - Schenker, Sebastian A1 - Skutella, Martin A1 - Strunk, Timo ED - Greuel, G.-M. ED - Koch, Thorsten ED - Paule, Peter ED - Sommese, Andrew T1 - PolySCIP T2 - Mathematical Software – ICMS 2016, 5th International Conference, Berlin, Germany, July 11-14, 2016, Proceedings N2 - PolySCIP is a new solver for multi-criteria integer and multi-criteria linear programs handling an arbitrary number of objectives. It is available as an official part of the non-commercial constraint integer programming framework SCIP. It utilizes a lifted weight space approach to compute the set of supported extreme non-dominated points and unbounded non-dominated rays, respectively. The algorithmic approach can be summarized as follows: At the beginning an arbitrary non-dominated point is computed (or it is determined that there is none) and a weight space polyhedron created. In every next iteration a vertex of the weight space polyhedron is selected whose entries give rise to a single-objective optimization problem via a combination of the original objectives. If the ptimization of this single-objective problem yields a new non-dominated point, the weight space polyhedron is updated. Otherwise another vertex of the weight space polyhedron is investigated. The algorithm finishes when all vertices of the weight space polyhedron have been investigated. The file format of PolySCIP is based on the widely used MPS format and allows a simple generation of multi-criteria models via an algebraic modelling language. Y1 - 2016 SN - 978-3-319-42431-6 U6 - https://doi.org/10.1007/978-3-319-42432-3_32 VL - 9725 SP - 259 EP - 264 PB - Springer International Publishing ET - Mathematical Software – ICMS 2016 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - Passenger routing for periodic timetable optimization BT - Planning and Operations JF - Public Transport N2 - The task of periodic timetabling is to determine trip arrival and departure times in a public transport system such that travel and transfer times are minimized. This paper investigates periodic timetabling models with integrated passenger routing. We show that different routing models can have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems by integrating passenger routing. Y1 - 2016 U6 - https://doi.org/10.1007/s12469-016-0132-0 PB - Springer-Verlag Berlin Heidelberg ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - Separation of Cycle Inequalities for the Periodic Timetabling Problem T2 - 24th Annual European Symposium on Algorithms (ESA 2016) N2 - Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem. Y1 - 2016 U6 - https://doi.org/10.4230/LIPIcs.ESA.2016.21 VL - 57 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Karbstein, Marika T1 - Metric inequalities for routings on direct connections with application to line planning JF - Discrete Optimization N2 - We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the well-known feasibility condition for arc capacities in ordinary multi-commodity flows. The condition can be expressed in terms of a class of metric inequalities for routings on direct connections. We illustrate the concept on the example of the line planning problem in public transport and present an application to large-scale real-world problems. Y1 - 2015 VL - 18 SP - 56 EP - 73 ER - TY - CHAP A1 - Sprösser, Gunther A1 - Schenker, Sebastian A1 - Pittner, Andreas A1 - Borndörfer, Ralf A1 - Rethmeier, Michael A1 - Chang, Ya-Ju A1 - Finkbeiner, Matthias T1 - Sustainable Welding Process Selection based on Weight Space Partitions T2 - Procedia CIRP Y1 - 2016 U6 - https://doi.org/10.1016/j.procir.2016.01.077 VL - 40 SP - 127 EP - 132 ER - TY - CHAP A1 - Schenker, Sebastian A1 - Steingrímsson, Jón Garðar A1 - Borndörfer, Ralf A1 - Seliger, Günther T1 - Modelling of Bicycle Manufacturing via Multi-criteria Mixed Integer Programming T2 - Procedia CIRP Y1 - 2015 U6 - https://doi.org/10.1016/j.procir.2014.07.068 VL - 26 SP - 276 EP - 280 ER - TY - CHAP A1 - Gausemeier, Pia A1 - Seliger, Günther A1 - Schenker, Sebastian A1 - Borndörfer, Ralf T1 - Nachhaltige Technologiepfade für unterschiedliche Entwicklungsniveaus mithilfe mehrkriterieller Entscheidungsfindung T2 - Vorausschau und Technologieplanung Y1 - 2014 SN - 978-3-942647-53-3 VL - 334 SP - 65 EP - 94 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 - 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 - CHAP A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - An IP Approach to Toll Enforcement Optimization on German Motorways T2 - Operations Research Proceedings 2011 N2 - This paper proposes the first model for toll enforcement optimization on German motorways. The enforcement is done by mobile control teams and our goal is to produce a schedule achieving network-wide control, proportional to spatial and time-dependent traffic distributions. Our model consists of two parts. The first plans control tours using a vehicle routing approach with profits and some side constraints. The second plans feasible rosters for the control teams. Both problems can be modeled as Multi-Commodity Flow Problems. Adding additional coupling constraints produces a large-scale integrated integer programming formulation. We show that this model can be solved to optimality for real world instances associated with a control area in East Germany. Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-29210-1_51 SP - 317 EP - 322 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach T2 - Proceedings of INOC'2013 N2 - We present a game-theoretic approach to optimize the strategies of toll enforcement on a motorway network. In contrast to previous approaches, we consider a network with an arbitrary topology, and we handle the fact that users may choose their Origin-Destination path; in particular they may take a detour to avoid sections with a high control rate. We show that a Nash equilibrium can be computed with an LP (although the game is not zero-sum), and we give a MIP for the computation of a Stackelberg equilibrium. Experimental results based on an application to the enforcement of a truck toll on German motorways are presented. Y1 - 2013 U6 - https://doi.org/http://dx.doi.org//10.1016/j.endm.2013.05.100 VL - 41 SP - 253 EP - 260 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Omont, Bertrand A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - A Stackelberg game to optimize the distribution of controls in transportation networks T2 - Proceedings of the 3rd International Conference on Game Theory for Networks (GAMENETS 2012) N2 - We propose a game theoretic model for the spatial distribution of inspectors on a transportation network. The problem is to spread out the controls so as to enforce the payment of a transit toll. We formulate a linear program to find the control distribution which maximizes the expected toll revenue, and a mixed integer program for the problem of minimizing the number of evaders. Furthermore, we show that the problem of finding an optimal mixed strategy for a coalition of $N$ inspectors can be solved efficiently by a column generation procedure. Finally, we give experimental results from an application to the truck toll on German motorways. Y1 - 2012 U6 - https://doi.org/http://dx.doi.org/10.1007/978-3-642-35582-0_17 VL - 105 SP - 224 EP - 235 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 - JOUR A1 - Borndörfer, Ralf A1 - Heismann, Olga T1 - The hypergraph assignment problem JF - Discrete Optimization Y1 - 2015 U6 - https://doi.org/10.1016/j.disopt.2014.11.002 VL - 15 SP - 15 EP - 25 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Jaeger, Ulrich T1 - Planning Problems in Public Transit N2 - Every day, millions of people are transported by buses, trains, and airplanes in Germany. Public transit (PT) is of major importance for the quality of life of individuals as well as the productivity of entire regions. Quality and efficiency of PT systems depend on the political framework (state-run, market oriented) and the suitability of the infrastructure (railway tracks, airport locations), the existing level of service (timetable, flight schedule), the use of adequate technologies (information, control, and booking systems), and the best possible deployment of equipment and resources (energy, vehicles, crews). The decision, planning, and optimization problems arising in this context are often gigantic and “scream” for mathematical support because of their complexity. This article sketches the state and the relevance of mathematics in planning and operating public transit, describes today’s challenges, and suggests a number of innovative actions. The current contribution of mathematics to public transit is — depending on the transportation mode — of varying depth. Air traffic is already well supported by mathematics. Bus traffic made significant advances in recent years, while rail traffic still bears significant opportunities for improvements. In all areas of public transit, the existing potentials are far from being exhausted. For some PT problems, such as vehicle and crew scheduling in bus and air traffic, excellent mathematical tools are not only available, but used in many places. In other areas, such as rolling stock rostering in rail traffic, the performance of the existing mathematical algorithms is not yet sufficient. Some topics are essentially untouched from a mathematical point of view; e.g., there are (except for air traffic) no network design or fare planning models of practical relevance. PT infrastructure construction is essentially devoid of mathematics, even though enormous capital investments are made in this area. These problems lead to questions that can only be tackled by engineers, economists, politicians, and mathematicians in a joint effort. Among other things, the authors propose to investigate two specific topics, which can be addressed at short notice, are of fundamental importance not only for the area of traffic planning, should lead to a significant improvement in the collaboration of all involved parties, and, if successful, will be of real value for companies and customers: • discrete optimal control: real-time re-planning of traffic systems in case of disruptions, • model integration: service design in bus and rail traffic. Work on these topics in interdisciplinary research projects could be funded by the German ministry of research and education (BMBF), the German ministry of economics (BMWi), or the German science foundation (DFG). T3 - ZIB-Report - 09-13 KW - öffentlicher Verkehr KW - diskrete Optimierung KW - ganzzahlige Programmierung KW - public transit KW - discrete optimization KW - integer programming Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11252 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 - Neumann, Marika A1 - Pfetsch, Marc T1 - The Steiner Connectivity Problem N2 - The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role. T3 - ZIB-Report - 09-07 KW - Steiner Tree KW - Partition Inequalities KW - Paths KW - Connectivity KW - Generalization Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11171 SN - 1438-0064 ER - TY - GEN A1 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc T1 - Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System (Extended Abstract) N2 - Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated. T3 - ZIB-Report - 08-53 KW - line planning KW - computational complexity KW - public transport KW - integer programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11076 SN - 1438-0064 ER - TY - GEN A1 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc T1 - On the Line Planning Problem in Tree Networks N2 - We introduce an optimization model for the line planning problem in a public transportation system that aims at minimizing operational costs while ensuring a given level of quality of service in terms of available transport capacity. We discuss the computational complexity of the model for tree network topologies and line structures that arise in a real-world application at the Trolebus Integrated System in Quito. Computational results for this system are reported. T3 - ZIB-Report - 08-52 KW - line planning KW - computational complexity KW - public transport optimization Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11069 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 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc T1 - Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System N2 - Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated. T3 - ZIB-Report - 08-35 KW - line planning KW - computational complexity KW - public transport KW - integer programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10869 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung T1 - Fair Ticket Prices in Public Transport N2 - Ticket pricing in public transport usually takes a welfare or mnemonics maximization point of view. These approaches do not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and integer programming. An application to pricing railway tickets for the intercity network of the Netherlands demonstrates that, in this sense, prices that are much fairer than standard ones can be computed in this way. T3 - ZIB-Report - 08-46 KW - Ticket prices KW - cost allocation game Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10999 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 T1 - Combinatorial Packing Problems N2 - This article investigates a certain class of combinatorial packing problems and some polyhedral relations between such problems and the set packing problem. T3 - ZIB-Report - 03-03 KW - Packing problems KW - polyhedral combinatorics Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7255 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Neumann, Marika A1 - Pfetsch, Marc T1 - Optimal Fares for Public Transport N2 - The \emph{fare planning problem} for public transport is to design a system of fares that maximize the revenue. We introduce a nonlinear optimization model to approach this problem. It is based on a d iscrete choice logit model that expresses demand as a function of the fares. We illustrate our approach by computing and comparing two different fare systems for the intercity network of the Netherlands. T3 - ZIB-Report - 05-35 KW - fare planning KW - demand function KW - discrete choice model Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8698 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 - 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 - JOUR A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung T1 - Fair ticket pricing in public transport as a constrained cost allocation game JF - Annals of Operations Research N2 - Ticket pricing in public transport usually takes a welfare maximization point of view. Such an approach, however, does not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and linear and integer programming. The ticket pricing problem is considered to be a constrained cost allocation game, which is a generalization of cost allocation games that allows to deal with constraints on output prices and on the formation of coalitions. An application to pricing railway tickets for the intercity network of the Netherlands is presented. The results demonstrate that the fairness of prices can be improved substantially in this way. A preliminary version of this paper appeared in the Proceedings of HPSC 2009 (Borndörfer and Hoang 2012). This journal article introduces better model and algorithms. Y1 - 2014 U6 - https://doi.org/10.1007/s10479-014-1698-z VL - 226 SP - 51 EP - 68 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf T1 - An Approximation Result for Matchings in Partitioned Hypergraphs 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})$. T3 - ZIB-Report - 14-30 Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51083 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 - CHAP A1 - Heismann, Olga A1 - Borndörfer, Ralf T1 - A Generalization of Odd Set Inequalities for the Set Packing Problem T2 - Operations Research Proceedings 2013 N2 - The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning. Y1 - 2014 U6 - https://doi.org/10.1007/978-3-319-07001-8_26 SP - 193 EP - 199 ER - TY - GEN A1 - Grötschel, Martin A1 - Borndörfer, Ralf T1 - Mathematik im Verkehr N2 - Nach einem kurzen Abriss über die Bedeutung des Verkehrssektors als eine wichtige Schlüsseltechnologie im gesamten Verlauf der Menschheitsgeschichte skizzieren wir die Rolle der Mathematik für Verkehr und Transport. Wir spekulieren dann über zukünftige Entwicklungen, insbesondere im Bereich des öffentlichen Personenverkehrs, und begründen, dass die in diesem Bereich anstehenden Herausforderungen nur mit dem Einsatz mathematischer Methoden angemessen bewältigt werden können. Die demographischen Prozesse, die in verschiedenen Teilen der Welt unterschiedlich verlaufen, wie z.B. Überalterung in Europa oder dynamische Trends zu Megastädten in Entwicklungsländern, sich ändernde Lebens- und Produktionsverhältnisse, stark wachsender Bedarf nach Mobilität und enormes Anwachsen der Komplexität der Verkehrsplanung und -durchführung, machen einen verstärkten Zugriff auf mathematische Modellierung, Simulation und Optimierung notwendig. Diese Entwicklung stellt sowohl große Herausforderungen an die Mathematik, wo vielfach noch keine geeigneten Methoden vorhanden sind, als auch an die Praktiker im Bereich von Verkehr und Transport, die sich mit neuen Planungs- und Steuerungstechnologien befassen und diese effizient einsetzen müssen. Hier wird intensive Kooperation zwischen vielen beteiligten Akteuren gefragt sein. T3 - ZIB-Report - 14-03 KW - Optimierung KW - öffentlicher Verkehr Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-50287 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Dittbrenner, Bastian A1 - Langenhan, Andreas A1 - Seidl, Stephan A1 - Weider, Steffen T1 - Integrierte Dienst- und Dienstreihenfolgeplanung zur Erhöhung der Fahrerzufriedenheit N2 - Wir stellen einen mathematischen Optimierungsansatz zur integrierten Dienst- und Dienstreihenfolgeplanung im öffentlichen Nahverkehr vor, mit dem sich bei konstanten Personalkosten die Fahrerzufriedenheit deutlich steigern lässt. T3 - ZIB-Report - 14-02 KW - duty scheduling KW - duty rostering KW - integrated scheduling KW - Benders' decomposition Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-50270 SN - 1438-0064 ER - TY - GEN A1 - Heismann, Olga A1 - Borndörfer, Ralf T1 - A Generalization of Odd Set Inequalities for the Set Packing Problem N2 - The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning. T3 - ZIB-Report - 14-28 KW - set packing KW - matching KW - hypergraph KW - inequality KW - facet Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51010 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Omont, Bertrand A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - A Stackelberg game to optimize the distribution of controls in transportation networks N2 - We propose a game theoretic model for the spatial distribution of inspectors on a transportation network. The problem is to spread out the controls so as to enforce the payment of a transit toll. We formulate a linear program to find the control distribution which maximizes the expected toll revenue, and a mixed integer program for the problem of minimizing the number of evaders. Furthermore, we show that the problem of finding an optimal mixed strategy for a coalition of $N$ inspectors can be solved efficiently by a column generation procedure. Finally, we give experimental results from an application to the truck toll on German motorways. T3 - ZIB-Report - 12-15 KW - Stackelberg game KW - Polymatrix game KW - Controls in transportation networks Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14995 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Schwartz, Stephan T1 - An Extended Network Interdiction Problem for Optimal Toll Control N2 - We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways. T3 - ZIB-Report - 15-32 KW - network interdiction Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55405 SN - 1438-0064 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Network spot-checking games: Theory and application to toll enforcing in transportation networks JF - Networks 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. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of arcs to be controlled. 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 (SSE) is more relevant for this problem and we give a mixed integer programming (MIP) formulation for this problem. We show that the computation of such an equilibrium is NP-hard. More generally, we prove that it is NP-hard to compute a SSE in a polymatrix game, even if the game is pairwise zero-sum. Then, we give some bounds on the price of spite, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we report computational experiments on instances constructed from real data, for an application to the enforcement of a truck toll in Germany. These numerical results show the efficiency of the proposed methods, as well as the quality of the bounds derived in this article. Y1 - 2015 U6 - https://doi.org/10.1002/net.21596 VL - 65 SP - 312 EP - 328 PB - Wiley Periodicals, Inc. 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 - 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 - 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 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - Umsteigen ohne Warten T2 - HEUREKA 2017 N2 - Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrplänen vor, bei dem die Umsteigezeiten unter Berücksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Beförderungsqualität. Y1 - 2017 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - Passenger Routing for Periodic Timetable Optimization N2 - The task of periodic timetabling is to schedule the trips in a public transport system by determining arrival and departure times at every station such that travel and transfer times are minimized. To date, the optimization literature generally assumes that passengers do not respond to changes in the timetable, i.e., the passenger routes are fixed. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We show that different routing models have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. to different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems. T3 - ZIB-Report - 15-55 KW - Passenger routing KW - Periodic timetabling KW - Public transport Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56739 SN - 1438-0064 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 - 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 - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika T1 - Neue Planungsinstrumente nutzen: Das Verkehrsangebot verbessern und Kosten sparen N2 - Wir illustrieren anhand des Liniennetzes der Stadt Potsdam das Potenzial mathematischer Methoden der Angebotsplanung. Wir zeigen, dass das "bestmögliche" Verkehrsangebot stark von planerischen Vorgaben beeinflusst wird, mit denen man die Erreichung unterschiedlicher und teilweise gegenläufiger Ziele steuern kann. Die Komplexität des Systems führt zum Auftreten von Rückkoppelungseffekten, die man nicht mit Hilfe von Daumenregeln beherrschen kann. Vielmehr ist der Einsatz moderner Planungsverfahren in einer interdisziplinären Zusammenarbeit von politischen Entscheidungsträgern, Verkehrsingenieuren und Mathematikern notwendig, um die aktuellen Herausforderungen in der Verkehrsplanung zu meistern. Der Artikel dokumentiert einen Beitrag zum 7. ÖPNV Innovationskongress des Ministeriums für Verkehr und Infrastruktur des Landes Baden-Württemberg, der vom 9.-11. März 2015 in Freiburg stattfand. T3 - ZIB-Report - 15-33 KW - Linienplan KW - Optimierung Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55439 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - Timetabling and Passenger Routing in Public Transport T2 - Appeard in: Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015) N2 - The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal. T3 - ZIB-Report - 15-31 KW - Passenger routing KW - Periodic timetabling KW - Public transport Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55305 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - Umsteigen ohne Warten N2 - Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrplänen vor, bei dem die Umsteigezeiten unter Berücksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Beförderungsqualität. T3 - ZIB-Report - 17-05 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62006 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 - Schenker, Sebastian A1 - Vierhaus, Ingmar A1 - Borndörfer, Ralf A1 - Fügenschuh, Armin A1 - Skutella, Martin ED - Stark, Rainer ED - Seliger, Günther ED - Bonvoisin, Jérémy T1 - Optimisation Methods in Sustainable Manufacturing BT - Challenges, Solutions and Implementation Perspectives T2 - Sustainable Manufacturing N2 - Sustainable manufacturing is driven by the insight that the focus on the economic dimension in current businesses and lifestyles has to be broadened to cover all three pillars of sustainability: economic development, social development, and environmental protection. Y1 - 2017 SN - 978-3-319-48514-0 U6 - https://doi.org/10.1007/978-3-319-48514-0_15 SP - 239 EP - 253 PB - Springer International Publishing ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schulz, Christof A1 - Seidl, Stephan A1 - Weider, Steffen T1 - Integration of Duty Scheduling and Rostering to Increase Driver Satisfaction N2 - Integrated treatment of hitherto individual steps in the planning process of public transit companies discloses opportunities to reduce costs and to improve the quality of service. The arising integrated planning problems are complex and their solution requires the development of novel mathematical methods. This article proposes a mathematical optimization approach to integrate duty scheduling and rostering in public transit, which allows to significantly increase driver satisfaction at almost zero cost. This is important in order to to increase the attractiveness of the driver profession. The integration is based on coupling the subproblems by duty templates, which, compared to a coupling by duties, drastically reduces the problem complexity. T3 - ZIB-Report - 15-50 KW - Benders decomposition KW - driver satisfaction KW - duty templates KW - duty scheduling KW - rostering Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56299 SN - 1438-0064 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf T1 - A Hall Condition for Normal Hypergraphs N2 - Conforti, Cornuéjols, Kapoor, and Vusković gave a Hall-type condition for the non-existence of a perfect matching in a balanced hypergraph. We generalize this result to the class of normal hypergraphs. T3 - ZIB-Report - 15-45 KW - Matchings in hypergraphs KW - Normal hypergraphs KW - Hall condition Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56175 SN - 1438-0064 ER -