Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.89
URN: urn:nbn:de:0030-drops-170271
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17027/
Werner, Nils ; Zeitz, Tim
Combining Predicted and Live Traffic with Time-Dependent A* Potentials
| pdf-format: |
|
Abstract
We study efficient and exact shortest path algorithms for routing on road networks with realistic traffic data. For navigation applications, both current (i.e., live) traffic events and predictions of future traffic flows play an important role in routing. While preprocessing-based speedup techniques have been employed successfully to both settings individually, a combined model poses significant challenges. Supporting predicted traffic typically requires expensive preprocessing while live traffic requires fast updates for regular adjustments. We propose an A*-based solution to this problem. By generalizing A* potentials to time dependency, i.e. the estimate of the distance from a vertex to the target also depends on the time of day when the vertex is visited, we achieve significantly faster query times than previously possible. Our evaluation shows that our approach enables interactive query times on continental-sized road networks while allowing live traffic updates within a fraction of a minute. We achieve a speedup of at least two orders of magnitude over Dijkstra’s algorithm and up to one order of magnitude over state-of-the-art time-independent A* potentials.
BibTeX - Entry
@InProceedings{werner_et_al:LIPIcs.ESA.2022.89,
author = {Werner, Nils and Zeitz, Tim},
title = {{Combining Predicted and Live Traffic with Time-Dependent A* Potentials}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {89:1--89:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17027},
URN = {urn:nbn:de:0030-drops-170271},
doi = {10.4230/LIPIcs.ESA.2022.89},
annote = {Keywords: realistic road networks, shortest paths, live traffic, time-dependent routing}
}
| Keywords: | realistic road networks, shortest paths, live traffic, time-dependent routing | |
| Seminar: | 30th Annual European Symposium on Algorithms (ESA 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 01.09.2022 | |
| Supplementary Material: | Software (Source Code): https://github.com/kit-algo/tdpot archived at: https://archive.softwareheritage.org/swh:1:dir:f0d810343d53d5ad87db428e89a32cb038dcaeab |
