**Project Heads**

Ralf Borndörfer, Niels Lindner

**Project Members**

Berenike Masing

**Project Duration**

01.01.2021 − 31.12.2022

**Located at**

ZIB

*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 first image 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. This observation gives rise to an improving heuristic, in which neighbouring polytropes are explored. This method provides the means to escape some local minima obtained by the modulo network simplex and, in general, to speed up the search.

The second and the third image depict a 2D decomposition of the space of feasible periodic timetables into 2-dimensional polytropes. Due to periodicity, this space is naturally the surface of a torus, the 2D plane being its universal cover.

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

**External Website**

**Related Publications
**

- N. Lindner, C. Liebchen, B. Masing. Forward Cycle Bases and Periodic Timetabling. 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
- N. Lindner, J. Reisch. An analysis of the parameterized complexity of periodic timetabling. Journal of Scheduling (2022).
- N. Lindner, C. Liebchen. Timetable Merging for the Periodic Event Scheduling Problem. ZIB-Report 21-06, Zuse Institute Berlin, 2021.
- N. Lindner, C. Liebchen. Determining All Integer Vertices of the PESP Polytope by Flipping Arcs. 20th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), 2020.
- M. Joswig, K. Kulas. Tropical and ordinary convexity combined. Advances in Geometry 10 (2), 2010.