KIT | KIT-Bibliothek | Impressum | Datenschutz

Using Incremental Many-to-One Queries to Build a Fast and Tight Heuristic for A* in Road Networks

Strasser, Ben 1; Zeitz, Tim 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

We study exact, efficient, and practical algorithms for route planning applications in large road networks. On the one hand, such algorithms should be able to answer shortest path queries within milliseconds. On the other hand, routing applications often require integrating the current traffic situation, planning ahead with predictions for future traffic, respecting forbidden turns, and many other features depending on the specific application. Therefore, such algorithms must be flexible and able to support a variety of problem variants. In this work, we revisit the A* algorithm to build a simple, extensible, and unified algorithmic framework applicable to many route planning problems. A* has been previously used for routing in road networks. However, its performance was not competitive because no sufficiently fast and tight distance estimation function was available. We present a novel, efficient, and accurate A* heuristic using Contraction Hierarchies, another popular speedup technique. The core of our heuristic is a new Contraction Hierarchies query algorithm called Lazy RPHAST, which can efficiently compute shortest distances from many incrementally provided sources toward a common target. ... mehr


Verlagsausgabe §
DOI: 10.5445/IR/1000157387
Veröffentlicht am 17.04.2023
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsdatum 31.12.2022
Sprache Englisch
Identifikator ISSN: 1084-6654
KITopen-ID: 1000157387
Erschienen in ACM Journal of Experimental Algorithmics
Verlag Association for Computing Machinery (ACM)
Band 27
Heft 4
Seiten 1–28
Nachgewiesen in Dimensions
Scopus
Globale Ziele für nachhaltige Entwicklung Ziel 11 – Nachhaltige Städte und Gemeinden
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page