Project
PaA-3
Timetabling for S-Bahn Berlin with Duality and Zonotopes
Project Heads
Ralf Borndörfer, Niels Lindner
Project Members
Enrico Bortoletto
Project Duration
01.01.2024 − 31.12.2025
Located at
ZIB
Description
Transportation networks are a daily encounter for us all. Maintaining smooth operations is a paramount objective both for quality of service and public finances. For the S-Bahn Berlin, optimizing periodic timetables is a complex challenge, especially due to turning constraints that arise at terminals and stations. Addressing these issues is crucial for preventing conflicts and ensuring reliable service. Our project tackles this problem by employing geometry-inspired duality approaches, integrating advanced mathematical techniques such as mixed-integer programming, Benders decomposition, matroids, hyperplane arrangements, and zonotopes. The aim of these innovations is to create robust and efficient timetables to enable better performance.
We focus on timetable optimization, particularly on the Periodic Event Scheduling Problem (PESP), the cornerstone of periodic timetable optimization. Its geometry is of special interest, showcasing an interesting duality in its variables, linking polytropes and zonotopes. These properties were recently used to devise novel solving heuristics, and we intend to keep working on this line. Our primary tool are mixed-integer linear programs, to extend PESP and integrate various constraints of practical interest. Within them, geometric insight drives the nature of our models, allowing for novel and more effective use of cutting planes, such as with cyclic order constraints.
This project canvasses periodic timetabling, discrete geometry, and railway operations practice, leveraging interdisciplinary experience to develop innovative solutions for the S-Bahn Berlin network. By bridging these fields, we provide advanced theoretical understanding of periodic timetabling in general, but also comprehensive strategies to be implemented in real-world scenarios, ultimately enhancing the efficiency and reliability of the S-Bahn Berlin network.
Project Webpages
Related Publications
- E. Bortoletto, N. Lindner, B. Masing. The Tropical and Zonotopal Geometry of Periodic Timetables. arXiv:2204.13501.
- E. Bortoletto, N. Lindner, B. Masing. Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling. 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022).
- B. Masing, N. Lindner, C. Liebchen. Periodic Timetabling with Integrated Track Choice for Railway Construction Sites. Journal of Rail Transport Planning & Management, Vol.28, p.100416, 2023.
- E. Bortoletto, N. Lindner, B. Masing. Periodic Timetabling with Cyclic Order Constraints. 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023).
- N. Lindner, B. Masing. SAT-Generated Initial Solutions for Integrated Line Planning and Turn-Sensitive Periodic Timetabling with Track Choice. ZIB Report.
Related Picture
