Creating an optimal timetable and choosing optimal passenger routes are usually viewed as two separate tasks in traffic optimization: Timetables are built assuming fixed passenger routes, and public transport route planners are based upon a fixed timetable. This project aims for an efficient integration of passenger routing and timetabling. Examples show that this approach is able to produce timetables with much smaller total traveling time for all passengers.

However, there are some difficulties: First, optimizing a timetable is already hard in the case of fixed passenger routes. This project hence attacks these problems in several ways, e.g., by improving the mixed integer program formulations, separating cutting planes and transforming to SAT instances. A second bottleneck is the large amount of routing computations required in the integrated timetabling problem. To this end, we investigate various routing methods beyond Dijkstra's algorithm, in particular time-dependent approaches and exploiting routing structures. Thirdly, integrated passenger routing and timetabling results in a large-scale bilinear integer optimization problem. This can be efficiently linearized, but the computational challenge is still demanding. To this end, we develop heuristics based on modulo network simplex techniques. In the long run, the goal of this project is to lead to a better understanding of the structure of public transportation networks and the characteristics of passenger paths.

This research is carried out in the framework of MATHEON supported by Einstein Foundation Berlin.

 

The video shows an optimized bus timetable. Overcrowded stations are colored dark.

Publications

2020
A Concurrent Approach to the Periodic Event Scheduling Problem Journal of Rail Transport Planning & Management, p. 100175, 2020 (preprint available as ZIB-Report 19-07) Ralf Borndörfer, Niels Lindner, Sarah Roth PDF (ZIB-Report)
BibTeX
DOI
Routing Structures & Periodic Timetabling
Hypersurfaces with defect Journal of Algebra, Vol.555, pp. 1-35, 2020 Niels Lindner BibTeX
DOI
arXiv
Routing Structures & Periodic Timetabling
Separation of cycle inequalities in periodic timetabling Discrete Optimization, p. 100552, 2020 (preprint available as ZIB-Report 18-16) Ralf Borndörfer, Heide Hoppmann, Marika Karbstein, Niels Lindner PDF (ZIB-Report)
BibTeX
DOI
Routing Structures & Periodic Timetabling
The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing Operations Research Proceedings 2019, Janis S. Neufeld, Udo Buscher, Rainer Lasch, Dominik Möst, Jörn Schönberger (Eds.), pp. 757-763, 2020, ISBN: 978-3-030-48438-5 (preprint available as ZIB-Report 19-36) Fabian Löbel, Niels Lindner, Ralf Borndörfer PDF (ZIB-Report)
BibTeX
DOI
Routing Structures & Periodic Timetabling
2019
Multi-Period Line Planning with Resource Transfers ZIB-Report 19-51 Guvenc Sahin, Amin Ahmadi, Ralf Borndörfer, Thomas Schlechte PDF
BibTeX
URN
Routing Structures & Periodic Timetabling
New Perspectives on PESP: T-Partitions and Separators 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019), Valentina Cacchiani, Alberto Marchetti-Spaccamela (Eds.), pp. 2:1-2:18, Vol.75, OpenAccess Series in Informatics (OASIcs), 2019 (preprint available as ZIB-Report 19-35) Niels Lindner, Christian Liebchen PDF (ZIB-Report)
BibTeX
DOI
Routing Structures & Periodic Timetabling
2018
A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018), pp. 16:1-16:15, Vol.65, OpenAccess Series in Informatics (OASIcs), 2018 (preprint available as ZIB-Report 18-38) Ralf Borndörfer, Marika Karbstein, Christian Liebchen, Niels Lindner PDF (ZIB-Report)
BibTeX
DOI
Routing Structures & Periodic Timetabling
Demand-Driven Line Planning with Selfish Routing Operations Research Proceedings 2017, pp. 687-692, 2018 (preprint available as ZIB-Report 17-38) Malte Renken, Amin Ahmadi, Ralf Borndörfer, Guvenc Sahin, Thomas Schlechte PDF (ZIB-Report)
BibTeX
DOI
Routing Structures & Periodic Timetabling
Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems Ralf Borndörfer, Sabine Storandt (Eds.), Dagstuhl Publishing, Saarbrücken/Wadern, Germany, 2018, ISBN: ISBN 978-3-95977-096-5 BibTeX
DOI
Routing Structures & Periodic Timetabling