The Tropical Geometry of Periodic Timetables brings together the mathematical optimization of periodic timetables, a key problem in the planning of public transportation of system, and tropical geometry, a discipline of pure mathematics situated on the intersection of algebraic geometry and discrete mathematics.

The fundamental connection between the two worlds is that a periodic timetabling problem, modeled by means of the Periodic Event Scheduling Problem (PESP), decomposes into minimum cost network tension problems over special polyhedra, namely polytropes. These are convex polytopes that are also tropically convex. This enables a dictionary between classical notions and techniques in periodic timetabling on one side, and features of tropical convexity on the other. The aim of the project is to make use of this dictionary to gain new insight into periodic timetabling algorithms, e.g., tropical neighborhood search, tropical coarse-to-fine methods, or tropical branch-and-bound.

The image (credits: Enrico Bortoletto) shows a 3D decomposition of the space of feasible periodic timetables into red 3-dimensional and green 1-dimensional polytropes. There are, after preprocessing, no codimension 1 polytropes. The less transparent a polytrope is, the better is the total passenger travel time of the best timetable that it contains.

The project is funded by the Berlin Mathematics Research Center MATH+ and belongs to the MATH+ Application Area 3 Networks.

Publications

2024
SAT-Generated Initial Solutions for Integrated Line Planning and Turn-Sensitive Periodic Timetabling with Track Choice ZIB-Report 24-01 Niels Lindner, Berenike Masing PDF
BibTeX
URN
The Tropical Geometry of Periodic Timetables
The Tropical and Zonotopal Geometry of Periodic Timetables Discrete & Computational Geometry, 2024 (in press, preprint available as ZIB-Report 22-09) Enrico Bortoletto, Niels Lindner, Berenike Masing PDF (ZIB-Report)
BibTeX
DOI
The Tropical Geometry of Periodic Timetables
2023
Forward and Line-Based Cycle Bases for Periodic Timetabling Operations Research Forum, 4(3), p. 53, 2023 (preprint available as ZIB-Report 23-05) Berenike Masing, Niels Lindner, Patricia Ebert PDF (ZIB-Report)
BibTeX
DOI
The Tropical Geometry of Periodic Timetables
Incremental Heuristics for Periodic Timetabling ZIB-Report 23-22 (accepted for publication) Niels Lindner, Christian Liebchen PDF
BibTeX
URN
The Tropical Geometry of Periodic Timetables
Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), pp. 5:1-5:15, Vol.115, Open Access Series in Informatics (OASIcs), 2023 Berenike Masing, Niels Lindner, Christian Liebchen BibTeX
DOI
The Tropical Geometry of Periodic Timetables
Introducing TimPassLib – A Library for Integrated Periodic Timetabling and Passenger Routing Operations Research Forum, 4(3), p. 64, 2023 (preprint available as ZIB-Report 23-06) Philine Schiewe, Marc Goerigk, Niels Lindner PDF (ZIB-Report)
BibTeX
DOI
The Tropical Geometry of Periodic Timetables
On the Split Closure of the Periodic Timetabling Polytope ZIB-Report 23-16 Niels Lindner, Berenike Masing PDF
BibTeX
URN
The Tropical Geometry of Periodic Timetables
Periodic Timetabling with Cyclic Order Constraints 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), pp. 7:1-7:18, Vol.115, Open Access Series in Informatics (OASIcs), 2023 Enrico Bortoletto, Niels Lindner, Berenike Masing BibTeX
DOI
The Tropical Geometry of Periodic Timetables
Periodic timetabling with integrated track choice for railway construction sites Journal of Rail Transport Planning & Management, Vol.28, p. 100416, 2023 (preprint available as ZIB-Report 22-26) Berenike Masing, Niels Lindner, Christian Liebchen PDF (ZIB-Report)
BibTeX
DOI
The Tropical Geometry of Periodic Timetables
Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times ZIB-Report 23-23 (accepted for publication) Enrico Bortoletto, Niels Lindner PDF
BibTeX
URN
The Tropical Geometry of Periodic Timetables
2022
An analysis of the parameterized complexity of periodic timetabling Journal of Scheduling, Vol.25, pp. 157-176, 2022 (preprint available as ) Niels Lindner, Julian Reisch BibTeX
DOI
The Tropical Geometry of Periodic Timetables
Benders Decomposition for the Periodic Event Scheduling Problem Operations Research Proceedings 2021, pp. 289-294, 2022 (preprint available as ) Niels Lindner, Rolf van Lieshout BibTeX
DOI
The Tropical Geometry of Periodic Timetables
Timetable merging for the Periodic Event Scheduling Problem EURO Journal on Transportation and Logistics, Vol.11, p. 100081, 2022 (preprint available as ) Niels Lindner, Christian Liebchen BibTeX
DOI
The Tropical Geometry of Periodic Timetables
Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022), pp. 3:1-3:19, Vol.106, Open Access Series in Informatics (OASIcs), 2022 (preprint available as ZIB-Report 22-13) Enrico Bortoletto, Niels Lindner, Berenike Masing PDF (ZIB-Report)
BibTeX
DOI
The Tropical Geometry of Periodic Timetables
2021
Forward Cycle Bases and Periodic Timetabling ZIB-Report 21-18 (appeared in 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)) Niels Lindner, Christian Liebchen, Berenike Masing PDF
BibTeX
URN
DOI
The Tropical Geometry of Periodic Timetables