Abstract. Efficiently computing fast paths in large scale dynamic road networks (where
dynamic traffic information is known over a part of the network) is a practical
problem faced by several traffic information service providers who wish to
offer a realistic fast path computation to GPS terminal enabled vehicles. The
heuristic solution method we propose is based on a highway hierarchy-based
shortest path algorithm for static large-scale networks; we maintain a static
highway hierarchy and perform each query on the dynamically evaluated network.