Algebraic and Tropical Methods for Periodic Timetabling

The mathematical optimization of periodic timetables in public transport relies on the Periodic Event Scheduling Problem (PESP), which has so far been studied almost exclusively with classical discrete optimization methods. During the course of the MATH+ Incubator Project Algebraic and Tropical Methods for Periodic Timetabling, we want to open up algebraic perspectives on periodic timetabling, invoking linear algebra over residue class rings and tropical geometry.

In particular, we will pursue the following research directions:

• Use linear algebra over Z/TZ (e.g., invoking Hermite and Smith normal forms) to parametrize the solution space for PESP and to explore new algorithmic perspectives.
• Find tropical interpretations of PESP beyond timetable stability analysis in the framework of the max-plus algebra.
• Investigate tropically inspired polyhedral decompositions of the space of periodic timetables and of passenger paths in integrated periodic timetabling and passenger routing, in order to understand routing structures in public transportation networks.