8670
eng
reportzib
0
--
2022-05-06
--
The tropical and zonotopal geometry of periodic timetables
The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetabling problems in public transport. A solution to PESP consists of three parts: a periodic timetable, a periodic tension, and integer periodic offset values. While the space of periodic tension has received much attention in the past, we explore geometric properties of the other two components, establishing novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables, and decompose it into polytropes, i.e., polytopes that are convex both classically and in the sense of tropical geometry. We then study this decomposition and use it to outline a new heuristic for PESP, based on the tropical neighbourhood of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope. We relate its zonotopal tilings back to the hyperrectangle of fractional periodic tensions and to the tropical neighbourhood of the periodic timetable space. To conclude we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis.
1438-0064
2204.13501
publish
false
true
Enrico Bortoletto
Enrico Bortoletto
Niels Lindner
Berenike Masing
ZIB-Report
22-09
eng
uncontrolled
periodic event scheduling
eng
uncontrolled
tropical geometry
eng
uncontrolled
zonotopal tilings
Tropical geometry [See also 12K10, 14M25, 14N10, 52B20]
Polyhedra and polytopes; regular figures, division of spaces [See also 51F15]
Special polytopes (linear programming, centrally symmetric, etc.)
Tilings in n dimensions [See also 05B45, 51M20]
Mixed integer programming
Combinatorial optimization
Programming involving graphs or networks [See also 90C27]
MODAL-Gesamt
Lindner, Niels
Bortoletto, Enrico
Network Optimization
Masing, Berenike
MODAL-MobilityLab
MathPlus-AA3-8
https://opus4.kobv.de/opus4-zib/files/8670/zibrep.pdf