  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.
