  We study efficient and exact shortest path algorithms for routing on road
networks with realistic traffic data. For navigation applications, both current
(i.e., live) traffic events and predictions of future traffic flows play an
important role in routing. While preprocessing-based speedup techniques have
been employed successfully to both settings individually, a combined model
poses significant challenges. Supporting predicted traffic typically requires
expensive preprocessing while live traffic requires fast updates for regular
adjustments. We propose an A*-based solution to this problem. By generalizing
A* potentials to time dependency, i.e. the estimate of the distance from a
vertex to the target also depends on the time of day when the vertex is
visited, we achieve significantly faster query times than previously possible.
Our evaluation shows that our approach enables interactive query times on
continental-sized road networks while allowing live traffic updates within a
fraction of a minute. We achieve a speedup of at least two orders of magnitude
over Dijkstra's algorithm and up to one order of magnitude over
state-of-the-art time-independent A* potentials.
