Journal
COMPUTATIONAL VISUAL MEDIA
Volume 7, Issue 2, Pages 267-281Publisher
SPRINGERNATURE
DOI: 10.1007/s41095-021-0211-2
Keywords
shortest-path; road map; heuristic; GPS navigation; A* search
Categories
Funding
- Anhui Provincial Natural Science Foundation [2008085MF195]
- National Natural Science Foundation of China [62072422]
- Zhejiang Lab [2019NB0AB03]
Ask authors/readers for more resources
In the age of real-time online traffic information and GPS-enabled devices, fast path computation in large road networks is critical, and the A* algorithm is an efficient way to reduce the number of vertices traversed, providing better estimates of minimal cost than other heuristics.
In the age of real-time online traffic information and GPS-enabled devices, fastest-path computations between two points in a road network modeled as a directed graph, where each directed edge is weighted by a travel time value, are becoming a standard feature of many navigation-related applications. To support this, very efficient computation of these paths in very large road networks is critical. Fastest paths may be computed as minimal-cost paths in a weighted directed graph, but traditional minimal-cost path algorithms based on variants of the classical Dijkstra algorithm do not scale well, as in the worst case they may traverse the entire graph. A common improvement, which can dramatically reduce the number of graph vertices traversed, is the A* algorithm, which requires a good heuristic lower bound on the minimal cost. We introduce a simple, but very effective, heuristic function based on a small number of values assigned to each graph vertex. The values are based on graph separators and are computed efficiently in a preprocessing stage. We present experimental results demonstrating that our heuristic provides estimates of the minimal cost superior to those of other heuristics. Our experiments show that when used in the A* algorithm, this heuristic can reduce the number of vertices traversed by an order of magnitude compared to other heuristics.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available