License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2021.6
URN: urn:nbn:de:0030-drops-137780
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13778/
Go to the corresponding LIPIcs Volume Portal


Strasser, Ben ; Zeitz, Tim

A Fast and Tight Heuristic for A* in Road Networks

pdf-format:
LIPIcs-SEA-2021-6.pdf (2 MB)


Abstract

We study exact, efficient and practical algorithms for route planning in large road networks. Routing applications often require integrating the current traffic situation, planning ahead with traffic predictions for the future, respecting forbidden turns, and many other features depending on the exact application. While Dijkstra’s algorithm can be used to solve these problems, it is too slow for many applications. A* is a classical approach to accelerate Dijkstra’s algorithm. A* can support many extended scenarios without much additional implementation complexity. However, A*’s performance depends on the availability of a good heuristic that estimates distances. Computing tight distance estimates is a challenge on its own. On road networks, shortest paths can also be quickly computed using hierarchical speedup techniques. They achieve speed and exactness but sacrifice A*’s flexibility. Extending them to certain practical applications can be hard. In this paper, we present an algorithm to efficiently extract distance estimates for A* from Contraction Hierarchies (CH), a hierarchical technique. We call our heuristic CH-Potentials. Our approach allows decoupling the supported extensions from the hierarchical speed-up technique. Additionally, we describe A* optimizations to accelerate the processing of low degree nodes, which often occur in road networks.

BibTeX - Entry

@InProceedings{strasser_et_al:LIPIcs.SEA.2021.6,
  author =	{Strasser, Ben and Zeitz, Tim},
  title =	{{A Fast and Tight Heuristic for A* in Road Networks}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13778},
  URN =		{urn:nbn:de:0030-drops-137780},
  doi =		{10.4230/LIPIcs.SEA.2021.6},
  annote =	{Keywords: route planning, shortest paths, realistic road networks}
}

Keywords: route planning, shortest paths, realistic road networks
Collection: 19th International Symposium on Experimental Algorithms (SEA 2021)
Issue Date: 2021
Date of publication: 31.05.2021
Supplementary Material: Software (Source Code): https://github.com/kit-algo/ch_potentials archived at: https://archive.softwareheritage.org/swh:1:dir:816552e5789f95afc8d6a2afe5b3dc40de537165


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI