  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 classic 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 traversed graph vertices, 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 computed efficiently in a preprocessing stage. We present
experimental results demonstrating that our heuristic provides estimates of the
minimal cost which are 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.
