Project B15 – Service Design in Public Transport

Project-Description

Service design in public transport deals with network design, line planning, timetabeling, and fare planning. These problems can be dealt with using mathematical methods. We have developped such approaches in the first Matheon funding period in two separate projects: Project B1 (Strategic Planning in public transport) studied line planning and fare planning, project B5 (Line planning and periodic timetabling in railway traffic) dealt mainly with timetabling.

Figures (a)-(c) illustrate some of the models, methods, and results of this work. Figure (a) shows a part of a timetable for the Berlin subway network, in which connections have been optimized. Figure (b) sketches a line plan with associated frequencies for the city of Potsdam, which optimizes a weighted sum of operation costs and total passenger travelling time. Figure (c) visualizes a Logit-model for passenger demand with respect to fares, which forms the basis our work on fare optimization.

(a) Connection optimization,	(b) line planning,	(c) demand with respect to prices.

Our timetabling model is based on a periodic event scheduling problem. We extended the timetable optimization by vehicle and duty scheduling aspects and tested this approach in a study for our cooperation partner ViP. Furthermore, we investigated delay resistant timetables by including certain buffer times. The line planning model integrates line planning and passenger routing and uses a column generation approach. It can be solved to near optimality for the instances provided by ViP. We are currently preparing the computation of the 2010 line plan for Potsam.

A major chanllenge 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 combinatorial context of line planning.

Poster

• Poster [ps]

Partners

• ViP Verkehrsbetrieb Potsdam GmbH
• IVU Traffic Technologies AG
• City of Potsdam
• Algorithms for Robust and online Railway optimization: Improving the Validity and reliAbility of Large scale systems (ARRIVAL)


• Ramiro Torres and Luis M. Torres (EPN Quito)
• DFG Research Center Matheon "Mathematics for key technologies",
  Project B3: Integrated planning of multi-level/multi-layer networks
  
• DFG Forschungszentrum Matheon "Mathematik für Schlüsseltechnologien",
  Projekt B20: Optimization of Gas Transport
  
• DFG Research Center Matheon "Mathematics for key technologies",
  Project F4: Visualization algorithms and web based software
  

Lectures

Winter 2007	Angewandte kombinatorische Optimierung (Seminar).
Summer 2007	Netzwerkoptimierung in Verkehr und Telekommunikation (Seminar).
Winter 2006	Ganzzahlige Optimierung im öffentlichen Verkehr (Lecture).

Conferences / Workshops

• ATMOS 2008
• ALENEX 2008
• ATMOS 2007
• ARRIVAL/Matheon Fall School 2006 on Timetabling and Line Planning

Publications

• R. Borndörfer, M. Neumann, M. E. Pfetsch. The Steiner Connectivity Problem. Technical Report, ZIB 2009.
• C. Liebchen, L. Peeters. Integral Cycle Bases for Cyclic Timetabling. Discrete Optimization 6 (1), 2009, a preliminary version is avalable as Technical Report 2002, TU-Berlin.
• R. Borndörfer, M. Neumann, M. E. Pfetsch. The Line Connectivity Problem. In Operations Research Proceedings 2008, B. Fleischmann, K. H Borgwardt, R. Klein, and A Tuma (eds), pp 557-562, Springer Verlag, 2009. Technical Report, ZIB 2008.
• R. Borndörfer, M. Neumann, M. E. Pfetsch. Models for Fare Planning in Public Transport. Technical Report, ZIB 2008.
• R. Borndörfer, M. Neumann, M. E. Pfetsch. Angebotsplanung im öffentlichen Nahverkehr. In Heureka '08 – Optimierung in Transport und Verkehr, M. Friedrich (ed.), Tagungsbericht, FGSV Verlag.
• L. M. Torres, R. Torres, R. Borndörfer, M. E. Pfetsch. Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System. In ATMOS 2008. Technical Report, ZIB 2008.
• L. M. Torres, R. Torres, R. Borndörfer, M. E. Pfetsch. On the Line Planning Problem in Tree Networks. Technical Report, ZIB 2008.
• C. Huber, C. Liebchen. Optimierungsmodell für integrierte Fahr-, Umlauf- und Dienstplanung In Der Nahverkehr 26, pp 51-55, 2008.
• C. Liebchen. Optimisation of passenger timetables: Are fully-integrated, regular-interval timetables really always the best? In European Rail Technology Review (RTR) 48 (4), 2008.
• C. Liebchen. Linien-, Fahrplan-, Umlauf- und Dienstplanoptimierung: Wie weit können diese bereits integriert werden? In Heureka '08 – Optimierung in Transport und Verkehr, M. Friedrich (ed.), Tagungsbericht, FGSV Verlag.
• C. Liebchen. Planung für den Nah- und Fernverkehr: Mathematische Optimierungsverfahren decken mehr Ziele ab In Eisenbahntechnische Rundschau, pp 363-368, Juni 2008.
• C. Liebchen. The First Optimized Railway Timetable in Practice. In Transportation Science 42 (4), 2008.
• C. Liebchen, Elmar Swarat. The Second Chvatal Closure Can Yield Better Railway Timetables To appear in M. Fischetti and P. Widmayer (eds.): Proceedings of ATMOS 2008.
• C. Liebchen, G. Wünsch. The Zoo of Tree Spanner Problems. Discrete Applied Mathematics 156(5), pp 569-587, 2008.
• R. Borndörfer, C. Liebchen. When Periodic Timetables are Suboptimal. In Operations Research Proceedings 2007, J. Kalcsics and S. Nickel (eds.), pp 449-454, Springer-Verlag, 2008.
• R. Borndörfer, M. Grötschel, M. E. Pfetsch. A Column-Generation Approach to Line Planning in Public Transport. In Transportation Science 41 (1), pp. 123-132, 2007.
• M. Elkin, C. Liebchen, R. Rizzi. New Length Bounds for Cycle Bases. In Information Processing Letters 104 (5), pp. 186-193, 2007.
• C. Liebchen. Periodic Timetable Optimization in Public Transport. In Operations Research Proceedings 2006, K.-H. Waldmann und U.-M. Stocker (eds.), pp. 29-36, Springer-Verlag (2007).
• C. Liebchen, R. Möhring. The Modeling Power of the Periodic Event Scheduling Problem: Railway Timetables – and Beyond. In CASPT Proceedings 2004 and in F. Geraets et al. (eds.): Algorithmic Methods for Railway Optimization, Springer, 2007.
• C. Liebchen, R. Rizzi. Classes of Cycle Bases. In Discrete Applied Mathematics 155 (3), pp. 337-355, 2007.
• C. Liebchen, M. Schachtebeck, A. Schöbel, S. Stiller, A. Prigge. Computing Delay Resistant Railway Timetables. Technical Report, TU-Berlin, 2007. To appear in Computers and Operations Research special issue on Disruption Management and Robust Planning in Optimization.
• C. Liebchen, G. Wünsch, E. Köhler, A. Reich, R. Rizzi. Benchmarks for Strictly Fundamental Cycle Bases. In Experimental and Efficient Algorithms – WEA 2007, Springer.
• M. Neumann. Fare Planning for Public Transport. In Operations Research Proceedings 2006, K.-H. Waldmann und U.-M. Stocker (eds.), pp. 61-66, Springer-Verlag (2007).
• M. Neumann. Mathematische Preisplanung im öPNV. In OR News 30, pp. 29-31, 2007.
• R. Borndörfer, M. Grötschel, M. E. Pfetsch. Public transport to the fORe. In OR/MS Today 33 (2) 2006.
• R. Borndörfer, M. Neumann, M. E. Pfetsch. Optimal Fares for Public Transport. In Operations Research Proceedings 2005, H.-D. Haasis et. al. (eds.), pp. 591-596, Springer-Verlag (2006).
• E. Köhler, C. Liebchen, R. Rizzi, G. Wünsch. Reducing the Optimality Gap of Strictly Fundamental Cycle Bases in Planar Grids. Technical Report 007/2006 TU-Berlin, 2006.
• C. Liebchen. Fahrplanoptimierung im Personenverkehr – Potenzial mathematischer Optimierung. In Eisenbahntechnische Rundschau 55 (7/8), pp. 504-510, 2006.
• C. Liebchen. Taktfahrplanoptimierung im öffentlichen Verkehr. In OR News 28, pp. 32-35, 2006.
• C. Liebchen, G. Wünsch. The Zoo of Tree Spanner Problems. To appear in Discrete Applied Mathematics, TU-Berlin, 2006.
• M. E. Pfetsch, R. Borndörfer. Routing in Line Planning for Public Transport. In Operations Research Proceedings 2005, H.-D. Haasis et. al. (eds.), pp. 405-410, Springer-Verlag (2006).
• R. Borndörfer, M. Neumann, M. E. Pfetsch. Fare Planning in Public Transport. Technical Report 05–20, ZIB, 2005.
• C. Liebchen. A Cut-based Heuristic to Produce Almost Feasible Periodic Railway Timetables. In Experimental and Efficient Algorithms – WEA 2005.
• C. Liebchen. Der Berliner U-Bahn Fahrplan 2005 – Realisierung eines mathematisch optimierten Angebotskonzepts. In Heureka '05 – Optimierung in Transport und Verkehr, M. Boltze (ed.), Tagungsbericht, FGSV Verlag.
• C. Liebchen. Fahrplanoptimierung im Personenverkehr – muss es immer ITF sein? In Eisenbahntechnische Rundschau 54 (11), pp. 689-702, 2005.
• C. Liebchen, R. Rizzi. A Greedy Approach to Compute a Minimum Cycle Bases of a Directed Graph. In Information Processing Letters 94 (3), pp. 107-112, 2005.
• R. Borndörfer, M. Grötschel, M. E. Pfetsch. Models for Line Planning in Public Transport. In Computer-aided Systems in Public Transport (CASPT 2004), M. Hickman et al. (eds.), pp. 363-378, Springer Verlag 2008.
• C. Liebchen, M. Proksch, and F.H. Wagner. Performance of Algorithms for Periodic Timetable Optimization. In Computer-aided Systems in Public Transport (CASPT 2004), M. Hickman et al. (eds.), pp. 117-150, Springer, 2008.
• C. Liebchen. Finding Short Integral Cycle Bases for Cyclic Timetabling. In Algorithms – ESA 2003.
• C. Liebchen. Symmetry for Periodic Railway Timetables. In Proceedings of ATMOS Workshop 2003.
• C. Liebchen, R. Möhring. Information on MIPLIB's timetab-instances. Technical Report 049/2003, TU-Berlin, 2003.
• C. Liebchen, R. Möhring. A Case Study in Periodic Timetabling. In ATMOS 2002, Algorithmic Methods and Models for Optimization of Railways.
• C. Liebchen, K. Nökel. Überführung eines mathematischen Modells zur Taktversatzoptimierung in die Praxis. In Heureka '02 – Optimierung in Transport und Verkehr, Tagungsbericht, M. Boltze (ed.), FGSV Verlag.
• C. Liebchen, L. Peeters. Some Practical Aspects of Periodic Timetabling. In Operations Research Proceedings 2001.

Edited Volumes

• R. K. Ahuja, C. Liebchen, J. A. Mesa Proceedings of ATMOS 2007. Published by Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany.

Phd-theses

• Christian Liebchen. Periodic Timetable Optimization in Public Transport. Phd-thesis, TU Berlin, 2006.

Diploma theses

• Mathias Kinder. Models for Periodic Timetabling. Diplomathesis, TU Berlin, 2008.
• André Prigge. Berechnung verspätungsresistenter Taktfahrpläne. Diplomathesis, TU Berlin, 2008.
• Torsten Ückerdt. Berechnung kurzer ganzzahliger Kreisbasen in Graphen. Diplomathesis, TU Berlin, 2008.
• Christina Puhl. Robuste Linienplanung und das (s,t)-Path Constrained Network Flow Problem. Diplomathesis, TU Berlin, 2007.
• Annegret Dix, Das statische Linienplanungsproblem Diplomathesis, TU Berlin, 2007.
• Thomas Gelzhäuser. Sampling-basierte Evaluation der Verspätungsresistenz von Fahrplänen. Diplomathesis, TU Berlin, 2006.
• Marika Neumann. Mathematische Preisplanung im ÖPNV. Diplomathesis, TU Berlin, 2005.
• Daniel Schmidt, Linien- und Taktfahrplanung – ein integrierter Optimierungsansatz. Diplomathesis, TU Berlin, 2005.
• Rüdiger Stephan. Polytopes Associated with Length-Restricted Directed Circuits. Diplomathesis, TU Berlin, 2005.
• Stephan Haenelt, Taktfahrplanoptimierung mit unterschiedlichen Taktzeiten. Diplomathesis, TU Berlin, 2004.
• Jan Laube, Taktfahrplanoptimierung mit Constraint Programming. Diplomathesis, TU Berlin, 2004.
• Maja Zinke, Fahrlagenplanung und -optimierung zur Erstellung von Taktfahrplänen für den Fernverkehr der Deutschen Bahn AG. Diplomathesis, TU Berlin, 2004.
• William Wieprecht. Mathematische Modellierung von Nahverkehrssystemen. Diplomathesis, TU Berlin, 2003.

A-level theses

• Johanna Ridder. Wegeprobleme der Graphentheorie. A-level thesis, Herder-Gymnasium Berlin, 2008.

Awards

Christian Liebchen:	HEUREKA Förderpreis 2008.
	GOR Dissertationspreis 2006.
	INFORMS TSL Dissertation Prize 2006.
Marika Neumann:	GOR Diplomarbeitspreis 2006.
Johanna Ridder:	DMV Abiturpreis Mathematik 2008.

Media/Links

• "MathFilm Festival 2008".
• "Langeweile im stillen Kämmerlein...", television report in MDR und ARD, 27.01.2008
• "Mathe in U-Bahn, Handy und im Wetterbericht", television report in " Mittagsmagazin" of ARD, 23.01.2008
• "Rechenkünste für die BVG", television report in rbb Abendschau, 26.02.2007
• "Mathematik überall – auch im Hauptbahnhof", radio interview in Inforadio (Wissenswerte), 26.05.2006
• "Klug informiert", radio interview in Deutschlandfunk (Forschung aktuell), 24.05.2006
• "Kürzere Wartezeiten im Nahverkehr" radio interview in Deutschlandfunk (Forschung aktuell), 09.12.2005
• "Schneller umsteigen" newspaper article in Berliner Zeitung, 09.11.2005
• "Ganz Indien fährt täglich in Berlin" newspaper article in Tagesspiegel, 22.10.2005