TY - JOUR A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf A1 - Knoben, Loes A1 - Kretz, David A1 - Uetz, Marc J. T1 - The S-Bahn Challenge in Berlin JF - OR News Y1 - 2015 UR - https://gor.uni-paderborn.de/index.php?id=362 IS - 53 SP - 10 EP - 14 ER - TY - JOUR A1 - Hoppmann, Heide T1 - Linienplanung und Minimale Konfigurationen JF - OR News Y1 - 2015 VL - 55 SP - 22 EP - 23 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Löbel, Fabian T1 - The Modulo Network Simplex with Integrated Passenger Routing T2 - Operations Research Proceedings 2016 N2 - Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration. Y1 - 2016 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Arslan, Oytun A1 - Elijazyfer, Ziena A1 - Güler, Hakan A1 - Renken, Malte A1 - Sahin, Guvenc A1 - Schlechte, Thomas T1 - Line Planning on Path Networks with Application to the Istanbul Metrobüs T2 - Operations Research Proceedings 2016 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. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-55702-1_32 SP - 235 EP - 241 ER - TY - GEN A1 - Renken, Malte A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Sahin, Guvenc A1 - Schlechte, Thomas T1 - Demand-Driven Line Planning with Selfish Routing N2 - Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines. T3 - ZIB-Report - 17-38 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64547 SN - 1438-0064 ER - TY - GEN A1 - 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 - 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 - 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 - 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 - Hoppmann, Heide T1 - An Extended Formulation for the Line Planning Problem T2 - Operations Research Proceedings 2015 N2 - In this paper we present a novel extended formulation for the line planning problem that is based on what we call “configurations” of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-42902-1_2 SP - 11 EP - 17 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 - GEN A1 - Hoppmann, Heide T1 - An Extended Formulation for the Line Planning Problem N2 - In this paper we present a novel extended formulation for the line planning problem that is based on what we call “configurations” of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature. T3 - ZIB-Report - 16-08 KW - Line Planning, Extended Formulation, Public Transport Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57467 SN - 1438-0064 ER - TY - THES A1 - Hoppmann, Heide T1 - A Configuration Model for the Line Planning Problem N2 - In this thesis we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations are combinatorial building blocks of primal solutions; they rule out the "capacity numerics" and make the problem purely combinatorial. The concept of configurations can also be adapted to other capacitated network design problems. The configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, multicover, and MIR inequalities. These theoretical findings can be confirmed in computations, however, the enormous number of configurations can blow up the formulation for large instances. We propose a mixed model that enriches the standard model by a judiciously chosen subset of configurations that provide a good compromise between model strength and size. Computational results for large-scale line planning problems are presented. N2 - Das Linienplanungsproblem ist ein wichtiges Teilproblem der Angebotsplanung im öffentlichen Nahverkehr. Dabei werden Routen und Betriebsfrequenzen von Linien in einem gegebenen Infrastrukturnetzwerk gesucht, sodass ein gegebener Beförderungsbedarf gedeckt wird und die Kosten minimal sind. Praktische Ansätze zum Lösen dieser Probleme beruhen auf ganzzahliger Programmierung. Ein Schwachpunkt klassischer Modelle ist, dass schon kleine Änderungen der Eingabeparameter eine Vergrößerung oder Verkleinerung der Menge der zulässigen fraktionalen Lösungen bewirken können, auch wenn die Menge der ganzzahligen Lösungen unverändert bleibt. Wir betrachten in dieser Arbeit einen neuen kombinatorischen Ansatz, welcher die Möglichkeiten den Bedarf auf einer Verbindung im Netzwerk mit Frequenzen zu überdecken mit Hilfe von diskreten "Konfigurationen" beschreibt und dieses Problem eliminiert. Um die Vorteile dieses Konfigurationsmodells aufzuzeigen, vergleichen wir es mit einem klassischen Ansatz, den wir Standardmodell nennen. Wir zeigen, dass das Konfigurationsmodell mehrere facettendefinierende Ungleichungen des Standardmodells impliziert: Setcover-, symmetrische Band-, Multicover- und MIR-Ungleichungen. Diese theoretischen Ergebnisse können wir mit Rechenergebnissen bestätigen. Um die Anzahl dieser Variablen auch für große Instanzen zu beschränken, schlagen wir ein weiteres Modell vor, welches nur eine Teilmenge der Konfigurationsvariablen enthält. Dieses stellt sich als ein sehr guter Kompromiss zwischen der Größe und der Stärke des Modells heraus. Da das Linienplanungsproblem eine Spezialisierung des Netzwerkdesignproblems ist, können unsere Methoden auch auf andere Problemklassen übertragen werden. Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51610 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 - 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 - 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 - Karbstein, Marika T1 - Neue Planungsinstrumente nutzen: Das Verkehrsangebot verbessern und Kosten sparen JF - Verkehr und Technik 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. Y1 - 2015 VL - 68 IS - 7 SP - 239 EP - 243 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - Timetabling and Passenger Routing in Public Transport T2 - 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. KW - Passenger routing KW - Periodic timetabling KW - Public transport Y1 - 2015 ER - TY - GEN A1 - Karbstein, Marika T1 - Integrated Line Planning and Passenger Routing: Connectivity and Transfers N2 - The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity. In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem. T3 - ZIB-Report - 14-42 KW - line planning, transfers,Steiner connectivity problem Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52986 SN - 1438-0064 ER -