Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Contraction Hierarchies with A* for digital road maps
verfasst von : Curt Nowak, M.Sc., Dr. Felix Hahne, Prof. Dr. Klaus Ambrosi
Erschienen in: Operations Research Proceedings 2011
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
One of the most successful recent approaches for solving single source - single destination problems in graphs is the Contraction Hierarchies (CH) algorithm, originally published by [3]. The general algorithm consists of two phases: Firstly, a total order on the nodes in the graph is calculated. Secondly for queries, a modified bi-directional Dijkstra-search is performed on the hierarchy implied hereby. Relying on Dijkstra’s algorithm, CH makes no use of the geometric information contained within digital road maps. We propose A*-like modifications of the original query algorithm that double query speed. Results are presented in a benchmark using a map from the OpenStreetMap project.