Service Design in Public Transport
In this project we developed a novel theory of path connectivity that generalizes the Steiner tree problem to a hypergraph setting. Main results include a Menger companion Theorem, approximation algorithms, and a polyhedral characterization, complemented by a new method to handle transfers in public transport applications. We used this theory to optimize the 2010 line plan of Potsdam’s public transport company ViP in a project Stadt+. To our knowledge, this was the first mathematically optimized line plan in operation.
The goal of service design is to construct a public transport system which is both attractive for passengers and can be operated economically. This requires strategic decisions in network design, line planning, timetabeling, and fare planning. Each of these questions deals with difficult optimization problems with multiple objectives. We have developed first mathematical methods for line planning, timetabling, and fare planning in the projects Strategic Planning in Public Transport at ZIB and Line Planning and Periodic Timetabling in Railway Traffic at TU Berlin.
In this project we further improved our models for line planning.
Line planning is a fundamental problem in the design of a public transportation system. It consists in finding a set of lines in an infrastructure network and their frequencies of operation such that a given travel demand can be routed. There are two main objectives, namely, minimization of operation costs and minimization of travel and transfer times.
The Steiner connectivity problem is an abstract combinatorial problem that underlies line planning. This prototype model has the same significance for line planning in public transport as the Steiner tree problem has for telecommunication network design. We investigate the Steiner connectivity problem and showe that main results about complexity, approximation, integer programming formulations, and polyhedra can be generalized from the Steiner tree problem to the Steiner connectivity problem.
The treatment of transfers is a major challenge in line planning. Previous 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.
Our biggest practical success was the optimization of the ViP (Verkehrsbetrieb Potsdam GmbH) line plan for 2010. In close cooperation with ViP, we fine-tuned our model and set up a data base that is suitable for the application of optimization methods. Among other things, we defined possible endpoints for new lines, added missing links, and modeled planning requirements such as a minimum cycle time for the tram, minimum frequency requirements for each station, or minimal and maximal lengths for lines with respect to travel time and distance. The final optimized solution reduces the cost by around 4% and the perceived travel time by around 6%. It further reduces the total number of transfers by around 5%; ViP also certified that this line plan was practicable and implemented the solution almost one-to-one.
A major challenge in service design optimization is the consideration of passenger behavior. The level of service decides whether passengers are attracted to this system or not. Understanding and controlling the interplay between service design and passenger behavior is therefore a main goal in service planning. We will investigate these aspects in the project Infrastructure Design & Passenger Behaviour in Public Transport.
Poster 2012 [pdf]
Publications
2020 |
|||
Guvenc Sahin, Amin Ahmadi, Ralf Borndörfer, Thomas Schlechte | Multi-period line planning with resource transfers | Transportation Research Part C: Emerging Technologies, Vol.119, p. 102726, 2020 (preprint available as ) |
BibTeX
DOI |
2018 |
|||
Erwin Abbink, Andreas Bärmann, Nikola Bešinovic, Markus Bohlin, Valentina Cacchiani, Gabrio Caimi, Stefano de Fabris, Twan Dollevoet, Frank Fischer, Armin Fügenschuh, Laura Galli, Rob M.P. Goverde, Ronny Hansmann, Henning Homfeld, Dennis Huisman, Marc Johann, Torsten Klug, Johanna Törnquist Krasemann, Leo Kroon, Leonardo Lamorgese, Frauke Liers, Carlo Mannino, Giorgio Medeossi, Dario Pacciarelli, Markus Reuther, Thomas Schlechte, Marie Schmidt, Anita Schöbel, Hanno Schülldorf, Anke Stieber, Sebastian Stiller, Paolo Toth, Uwe Zimmermann | Handbook of Optimization in the Railway Industry | Ralf Borndörfer, Torsten Klug, Leonardo Lamorgese, Carlo Mannino, Markus Reuther, Thomas Schlechte (Eds.), Springer Verlag, 2018, ISBN: 978-3-319-72152-1 |
BibTeX
DOI |
Ralf Borndörfer, Ascan Egerer, Marika Karbstein, Ralf Messerschmidt, Marc Perez, Steven Pfisterer, Petra Strauß | Kombilösung: Optimierung des Liniennetzes in Karlsruhe | ZIB-Report 18-45 (Der Nahverkehr 1-2, p. 33-38, 2019) |
PDF
BibTeX URN |
2016 |
|||
Marika Karbstein | Integrated Line Planning and Passenger Routing: Connectivity and Transfers | Operations Research Proceedings 2014, pp. 263-269, 2016 (preprint available as ZIB-Report 14-42) |
PDF (ZIB-Report)
BibTeX DOI |
2015 |
|||
Ralf Borndörfer, Marika Karbstein | Metric inequalities for routings on direct connections with application to line planning | Discrete Optimization, Vol.18, pp. 56-73, 2015 (preprint available as ZIB-Report 15-07) |
PDF (ZIB-Report)
BibTeX |
Ralf Borndörfer, Marika Karbstein | Neue Planungsinstrumente nutzen: Das Verkehrsangebot verbessern und Kosten sparen | Verkehr und Technik, 68(7), pp. 239-243, 2015 (preprint available as ZIB-Report 15-33) |
PDF (ZIB-Report)
BibTeX |
2014 |
|||
Heide Hoppmann | A Configuration Model for the Line Planning Problem | Master's thesis, Technische Universität Berlin, Ralf Borndörfer, Marika Karbstein (Advisors), 2014 |
PDF
BibTeX URN |
Martin Grötschel, Ralf Borndörfer | Mathematik im Verkehr | ZIB-Report 14-03 (Appeared in: HEUREKA '14. FGSV Verl. 2014, ISBN 978-3-86446-074-6 Vorträge der Tagung am 2./3. April 2014 in Stuttgart) |
PDF
BibTeX URN |
Ralf Borndörfer, Marika Karbstein | Metric Inequalities for Routings on Direct Connections | ZIB-Report 14-04 |
PDF
BibTeX URN |
Marika Karbstein | Ohne Umsteigen ans Ziel | OR News, Vol.52, pp. 12-14, 2014 |
BibTeX
|
2013 |
|||
Ralf Borndörfer, Heide Hoppmann, Marika Karbstein | A Configuration Model for the Line Planning Problem | ATMOS 2013 - 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, Daniele Frigioni, Sebastian Stiller (Eds.), pp. 68-79, Vol.33, 2013 (preprint available as ZIB-Report 13-40) |
PDF (ZIB-Report)
BibTeX DOI |
Ralf Borndörfer, Marika Karbstein | A Primal-Dual Approximation Algorithm for the Steiner Connectivity Problem | ZIB-Report 13-54 |
PDF
BibTeX URN |
Ralf Borndörfer, Nam-Dung Hoang, Marika Karbstein, Thorsten Koch, Alexander Martin | How many Steiner terminals can you connect in 20 years? | Facets of Combinatorial Optimization; Festschrift for Martin Grötschel, Michael Jünger, Gerhard Reinelt (Eds.), Springer, pp. 215-244, 2013 (preprint available as ZIB-Report 13-57) |
PDF (ZIB-Report)
BibTeX DOI |
Marika Karbstein | Line Planning and Connectivity | Doctoral thesis, Technische Universität Berlin, Ralf Borndörfer, Martin Grötschel (Advisors), 2013, ISBN: 978-3-8439-1062-0 |
BibTeX
|
Ralf Borndörfer, Marika Karbstein, Marc Pfetsch | The Steiner connectivity problem | Mathematical Programming A, 142(1), pp. 133-167, 2013 (preprint available as ZIB-Report 09-07) |
PDF (ZIB-Report)
PDF (ZIB-Report) BibTeX DOI |
2012 |
|||
Ralf Borndörfer, Marika Karbstein | A Direct Connection Approach to Integrated Line Planning and Passenger Routing | ATMOS 2012 - 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Daniel Delling, Leo Liberti (Eds.), pp. 47-57, Vol.25, 2012 (preprint available as ZIB-Report 12-29) |
PDF (ZIB-Report)
BibTeX DOI |
Ralf Borndörfer, Marika Karbstein | A Note on Menger's Theorem for Hypergraphs | ZIB-Report 12-03 |
PDF
BibTeX URN |
Ralf Borndörfer, Marika Karbstein, Marc Pfetsch | Models for Fare Planning in Public Transport | Discrete Applied Mathematics, 160(18), pp. 2591-2605, 2012 (preprint available as ZIB-Report 08-16) |
PDF (ZIB-Report)
PDF (ZIB-Report) BibTeX DOI |
Ralf Borndörfer, Isabel Friedow, Marika Karbstein | Optimierung des Linienplans 2010 in Potsdam | Der Nahverkehr, 30(4), pp. 34-39, 2012 (preprint available as ZIB-Report 12-04) |
PDF (ZIB-Report)
BibTeX |
2011 |
|||
Ralf Borndörfer, Marika Neumann | Linienoptimierung - reif für die Praxis? | Heureka '11 : Optimierung in Verkehr und Transport, FGSV ; 002/96, 2011 (preprint available as ZIB-Report 10-20) |
PDF (ZIB-Report)
BibTeX |
2010 |
|||
Ralf Borndörfer | Mathematical Optimization and Public Transportation | Habilitation, Technische Universität Berlin, 2010 |
PDF
BibTeX URN |
Ralf Borndörfer | Mathematical Optimization and Public Transportation | TU Berlin, 2010 |
BibTeX
|
Ralf Borndörfer, Marika Neumann | Models for Line Planning with Transfers | ZIB-Report 10-11 |
PDF
BibTeX URN |
Ralf Borndörfer, Martin Grötschel, Ulrich Jäger | Planning Problems in Public Transit | Production Factor Mathematics, pp. 95-122, 2010, ISBN: 978-3-642-11247-8 (preprint available as ZIB-Report 09-13) |
PDF (ZIB-Report)
BibTeX DOI |
Ralf Borndörfer, Martin Grötschel, Andreas Löbel | The Quickest Path to the Goal | Mathematics Everywhere, pp. 27-51, 2010 (preprint available as ZIB-Report 10-21) |
PDF (ZIB-Report)
BibTeX |
2009 |
|||
Ralf Borndörfer | Discrete Optimization in Public Transportation | ZIB-Report 08-56 |
PDF
BibTeX URN |
Ralf Borndörfer, Marika Neumann, Marc Pfetsch | Line Planning and Connectivity | Models and Algorithms for Optimization in Logistics, Cynthia Barnhart, Uwe Clausen, Ulrich Lauther, Rolf Möhring (Eds.), Dagstuhl Seminar Proceedings, 2009 |
BibTeX
|
Ralf Borndörfer, Marika Neumann, Marc Pfetsch | The Line Connectivity Problem | Operations Research Proceedings 2008, Bernhard Fleischmann, Karl Borgwardt, Robert Klein, Axel Tuma (Eds.), pp. 557-562, 2009 (preprint available as ZIB-Report 08-31) |
PDF (ZIB-Report)
BibTeX |
2008 |
|||
Ralf Borndörfer, Marika Neumann, Marc Pfetsch | Angebotsplanung im öffentlichen Nahverkehr | HEUREKA’08, 2008 (preprint available as ZIB-Report 08-04) |
PDF (ZIB-Report)
BibTeX |
Luis Miguel Torres, Ramiro Torres, Ralf Borndörfer, Marc Pfetsch | Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System | ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, Matteo Fischetti, Peter Widmayer (Eds.), 2008 (preprint available as ZIB-Report 08-35) |
PDF (ZIB-Report)
BibTeX |
Luis Miguel Torres, Ramiro Torres, Ralf Borndörfer, Marc Pfetsch | Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System (Extended Abstract) | ZIB-Report 08-53 (Appeared in: ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems. Matteo Fischetti and Peter Widmayer (eds.)Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, Dagstuhl, Germany, 2008. http://drops.dagstuhl.de/opus/volltexte/2008/1583) |
PDF
BibTeX URN |
Ralf Borndörfer, Martin Grötschel, Marc Pfetsch | Models for Line Planning in Public Transport | Computer-aided Systems in Public Transport (CASPT 2004), Mark Hickman, Pitu Mirchandani, Stefan Voß (Eds.), pp. 363-378, Vol.600, Lecture Notes in Economics and Mathematical Systems, 2008 (preprint available as ZIB-Report 04-10) |
PDF (ZIB-Report)
BibTeX DOI |
Mathias Kinder | Models for Periodic Timetabling | Master's thesis, Technische Universität Berlin, Martin Grötschel, Rolf Möhring, Ralf Borndörfer (Advisors), 2008 |
PDF
BibTeX URN |
Luis Miguel Torres, Ramiro Torres, Ralf Borndörfer, Marc Pfetsch | On the Line Planning Problem in Tree Networks | ZIB-Report 08-52 |
PDF
BibTeX URN |
Ralf Borndörfer, Martin Grötschel, Ulrich Jaeger | Planungsprobleme im öffentlichen Verkehr | PRODUKTIONSFAKTOR MATHEMATIK – Wie Mathematik Technik und Wirtschaft bewegt, Martin Grötschel, Klaus Lucas, Volker Mehrmann (Eds.), acatech – Deutsche Akademie der Technikwissenschaften und Springer, pp. 127-153, 2008 (preprint available as ZIB-Report 08-20) |
PDF (ZIB-Report)
BibTeX |
Ralf Borndörfer, Christian Liebchen | When Periodic Timetables are Suboptimal | Operations Research Proceedings 2007, Jörg Kalcsics, Stefan Nickel (Eds.), pp. 449-454, 2008 (preprint available as ZIB-Report 07-29) |
PDF (ZIB-Report)
BibTeX |
2007 |
|||
Ralf Borndörfer, Martin Grötschel, Marc Pfetsch | A Column-Generation Approach to Line Planning in Public Transport | Transportation Science (INFORMS), 41(1), pp. 123-132, 2007 (preprint available as ZIB-Report 05-18) |
PDF (ZIB-Report)
PDF (ZIB-Report) BibTeX DOI |
Marika Neumann | Fare Planning for Public Transport | Operations Research Proceedings 2006, Karl-Heinz Waldmann, Ulrike Stocker (Eds.), Springer-Verlag, pp. 61-66, 2007 (preprint available as ZIB-Report 09-04) |
PDF (ZIB-Report)
BibTeX |
Marika Neumann | Mathematische Preisplanung im ÖPNV | OR News, pp. 29-31, 2007 |
BibTeX
|
2006 |
|||
Ralf Borndörfer, Marika Neumann, Marc Pfetsch | Optimal Fares for Public Transport | Operations Research Proceedings 2005, Hans-Dietrich Haasis, Herbert Kopfer, Jörn Schönberger (Eds.), Springer-Verlag, pp. 29-36, 2006 (preprint available as ZIB-Report 05-35) |
PDF (ZIB-Report)
BibTeX |
Ralf Borndörfer, Martin Grötschel, Marc Pfetsch | Public transport to the fORe | OR/MS Today, pp. 30-40, 2006 (preprint available as ZIB-Report 05-22) |
PDF (ZIB-Report)
BibTeX |
Marc Pfetsch, Ralf Borndörfer | Routing in Line Planning for Public Transportation | Operations Research Proceedings 2005, Hans-Dietrich Haasis (Ed.), pp. 405-410, 2006 (preprint available as ZIB-Report 05-36) |
PDF (ZIB-Report)
BibTeX |
2005 |
|||
Ralf Borndörfer, Marika Neumann, Marc Pfetsch | Fare Planning for Public Transport | ZIB-Report 05-20 |
PDF
BibTeX URN |