Computing all shortest passenger routes with a tropical Dijkstra algorithm
Berenike Masing, Niels Lindner, Enrico Bortoletto · EURO Journal on Transportation and Logistics · 2025
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. • Interval shortest path problem for time-dependent transportation networks. • Equivalence to a multi-objective shortest path problem with exponentially many objectives. • Tropical Dijkstra Algorithm using tropical polynomials as labels • Successful computation of complete or minimal set of efficient passenger routes on realistic instances.