Acceleration of the A*-Algorithm for the Shortest Path Problem in Digital Road Maps

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

A chapter in Operations Research Proceedings 2007, 2008, pp 455-460 from Springer

Abstract: Abstract Using the A*-algorithm to solve point-to-point-shortest path problems, the number of iterations depends on the quality of the estimator for the remaining distance to the target. In digital maps of real road networks, iterations can be saved by using a better estimator than the Euclidian estimator. An approach is to integrate Segmentation Lines (SegLine) into the map modelling large obstacles. An auxiliary graph is constructed using the Seg-Lines wherein a shortest path is calculated yielding a better estimate. Some computational results are presented for a dynamic version of this approach.

Keywords: Short Path; Road Network; Search Tree; Short Path Problem; Short Path Algorithm (search for similar items in EconPapers)
Date: 2008
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-540-77903-2_70

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

DOI: 10.1007/978-3-540-77903-2_70

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 ().