TY - JOUR
T1 - Efficient fastest-path computations for road maps
AU - Chen, Renjie
AU - Gotsman, Craig
N1 - Funding Information:
We would like to thank the anonymous reviewers for their constructive suggestions and comments. This work was partly supported by the Anhui Provincial Natural Science Foundation (2008085MF195), the National Natural Science Foundation of China (62072422), and Zhejiang Lab (2019NB0AB03).
Publisher Copyright:
© 2021, The Author(s).
PY - 2021/6
Y1 - 2021/6
N2 - 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.
AB - 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.
KW - A search
KW - GPS navigation
KW - heuristic
KW - road map
KW - shortest-path
UR - http://www.scopus.com/inward/record.url?scp=85103407115&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85103407115&partnerID=8YFLogxK
U2 - 10.1007/s41095-021-0211-2
DO - 10.1007/s41095-021-0211-2
M3 - Article
AN - SCOPUS:85103407115
SN - 2096-0433
VL - 7
SP - 267
EP - 281
JO - Computational Visual Media
JF - Computational Visual Media
IS - 2
ER -