Customizable Route Planning

Daniel Delling, Andrew Goldberg, Thomas Pajor, Renato Werneck

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

Published by Springer Verlag

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.