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.