Contraction Hierarchies with A* for digital road maps

Curt Nowak (), Felix Hahne () and Klaus Ambrosi ()
Additional contact information
Curt Nowak: Universität Hildesheim
Felix Hahne: Universität Hildesheim
Klaus Ambrosi: Universität Hildesheim

A chapter in Operations Research Proceedings 2011, 2012, pp 311-316 from Springer

Abstract: Abstract 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.

Keywords: Optimal Path; Query Time; Forward Search; Query Algorithm; Bridge Node (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-642-29210-1_50

Ordering information: This item can be ordered from
http://www.springer.com/9783642292101

DOI: 10.1007/978-3-642-29210-1_50

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().