A Scalable Heuristic for Fastest-Path Computation on Very Large Road Maps
This addresses performance bottlenecks in transportation and navigation systems, but is incremental as it builds on existing A* and heuristic methods.
The paper tackles the problem of accelerating fastest-path queries on large road maps by developing a scalable heuristic based on hierarchical separators, which significantly improves A* search efficiency, especially for small and medium distances, as demonstrated experimentally.
Fastest-path queries between two points in a very large road map is an increasingly important primitive in modern transportation and navigation systems, thus very efficient computation of these paths is critical for system performance and throughput. We present a method to compute an effective heuristic for the fastest path travel time between two points on a road map, which can be used to significantly accelerate the classical A* algorithm when computing fastest paths. Our method is based on two hierarchical sets of separators of the map represented by two binary trees. A preprocessing step computes a short vector of values per road junction based on the separator trees, which is then stored with the map and used to efficiently compute the heuristic at the online query stage. We demonstrate experimentally that this method scales well to any map size, providing a better quality heuristic, thus more efficient A* search, for fastest path queries between points at all distances - especially small and medium range - relative to other known heuristics.