Computing All Shortest Passenger Routes with a Tropical Dijkstra Algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929641738993664 |
|---|---|
| author | Masing, Berenike Lindner, Niels Bortoletto, Enrico |
| author_facet | Masing, Berenike Lindner, Niels Bortoletto, Enrico |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_14654 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing All Shortest Passenger Routes with a Tropical Dijkstra Algorithm Masing, Berenike Lindner, Niels Bortoletto, Enrico Optimization and Control Discrete Mathematics 90-02, 90C27 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. |
| title | Computing All Shortest Passenger Routes with a Tropical Dijkstra Algorithm |
| topic | Optimization and Control Discrete Mathematics 90-02, 90C27 |
| url | https://arxiv.org/abs/2412.14654 |