We present an algorithm to compute shortest paths on continental road networks with arbitrary metrics (cost functions). The approach supports turn costs, enables real-time queries, and can incorporate a new metric in a few seconds---fast enough to support real-time traffic updates and personalized optimization functions. The amount of metric-specific data is a small fraction of the graph itself, which allows us to maintain several metrics in

memory simultaneously.

PDF file

In  Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11)

Publisher  Springer Verlag

Details