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

Computing All Shortest Passenger Routes with a Tropical Dijkstra Algorithm

  • Given a public transportation network, which and how many passenger routes can potentially be shortest paths, when all possible timetables are taken into account? This question leads to shortest path problems on graphs with interval costs on their arcs and is closely linked to multi-objective optimization. We introduce a Dijkstra algorithm based on polynomials over the tropical semiring that computes complete or minimal sets of efficient paths. We demonstrate that this approach is computationally feasible by employing it on the public transport network of the city of Wuppertal and instances of the benchmarking set TimPassLib, and we evaluate the resulting sets of passenger routes.

Export metadata

Additional Services

Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Berenike Masing, Niels Lindner, Enrico Bortoletto
Document Type:Article
Parent Title (English):EURO Journal on Transportation and Logistics
Volume:14
Year of first publication:2025
ArXiv Id:http://arxiv.org/abs/2412.14654
DOI:https://doi.org/10.1016/j.ejtl.2025.100163
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.