Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • search hit 1 of 99
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Enrico BortolettoORCiD, Niels LindnerORCiD, Berenike MasingORCiD
Document Type:ZIB-Report
Tag:periodic event scheduling; tropical geometry; zonotopal tilings
MSC-Classification:14-XX ALGEBRAIC GEOMETRY / 14Txx Tropical geometry [See also 12K10, 14M25, 14N10, 52B20] / 14T05 Tropical geometry [See also 12K10, 14M25, 14N10, 52B20]
51-XX GEOMETRY (For algebraic geometry, see 14-XX) / 51Mxx Real and complex geometry / 51M20 Polyhedra and polytopes; regular figures, division of spaces [See also 51F15]
52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B12 Special polytopes (linear programming, centrally symmetric, etc.)
52-XX CONVEX AND DISCRETE GEOMETRY / 52Cxx Discrete geometry / 52C22 Tilings in n dimensions [See also 05B45, 51M20]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
Date of first Publication:2022/05/06
Series (Serial Number):ZIB-Report (22-09)
ArXiv Id:http://arxiv.org/abs/2204.13501
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.