Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing

Please always quote using this URN: urn:nbn:de:0030-drops-247580
  • We offer a geometric perspective on the problem of integrated periodic timetabling and passenger routing in public transport. Inside the space of periodic tensions, we single out those regions, where the same set of paths provides shortest passenger routes. This results in a polyhedral subdivision, which we combine with the known decomposition by polytropes. On each maximal region of the common refinement, the integrated problem is solvable in polynomial time. We transform these insights into a new geometry-driven primal heuristic, integrated tropical neighborhood search (ITNS). Computationally, we compare implementations of ITNS and the integrated (restricted) modulo network simplex algorithm on the TimPassLib benchmark set, and contribute better solutions in terms of total travel time for all but one of the twenty-five instances for which a proven optimal solution is not yet known.
Metadaten
Author:Fabian LöbelORCiD, Niels LindnerORCiD
Editor:Jonas Sauer, Marie Schmidt
Document Type:In Proceedings
Parent Title (English):25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)
Volume:137
First Page:2:1
Last Page:2:19
Series:Open Access Series in Informatics (OASIcs)
Publisher:Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
Place of publication:Dagstuhl, Germany
Tag:Passenger Routing; Periodic Timetabling; Polyhedral Complexes
Date of first Publication:2025/10/17
ISSN:2190-6807
DOI:https://doi.org/10.4230/OASIcs.ATMOS.2025.2
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.