arbiter
JournalsAccount

Computing all shortest passenger routes with a tropical Dijkstra algorithm

Berenike Masing et al.

EURO Journal on Transportation and Logistics2025https://doi.org/10.1016/j.ejtl.2025.100163article
AJG 2ABDC B
Weight
0.50

Abstract

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 optimisation. 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.

Open via your library →

Cite this paper

https://doi.org/https://doi.org/10.1016/j.ejtl.2025.100163

Or copy a formatted citation

@article{berenike2025,
  title        = {{Computing all shortest passenger routes with a tropical Dijkstra algorithm}},
  author       = {Berenike Masing et al.},
  journal      = {EURO Journal on Transportation and Logistics},
  year         = {2025},
  doi          = {https://doi.org/https://doi.org/10.1016/j.ejtl.2025.100163},
}

Paste directly into BibTeX, Zotero, or your reference manager.

Flag this paper

Computing all shortest passenger routes with a tropical Dijkstra algorithm

Flags are reviewed by the Arbiter methodology team within 5 business days.

Evidence weight

0.50

Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40

F · citation impact0.50 × 0.4 = 0.20
M · momentum0.50 × 0.15 = 0.07
V · venue signal0.50 × 0.05 = 0.03
R · text relevance †0.50 × 0.4 = 0.20

† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.