Wednesday, 16:15 - 16:40 h, Room: H 3021


Daniel Delling
Realistic route planning in road networks

Coauthors: Andrew V. Goldberg, Thomas Pajor, Ilya Razenshteyn, Renato F. Werneck


I will present an extremely practical algorithm to compute shortest paths on continental road networks with arbitrary metrics (cost functions). The approach has very low space usage per metric, supports real-time queries, and can incorporate a new metric in a few seconds. As a result, it can easily handle real-time traffic updates and personalized optimization functions. Unlike most previous methods, ours does not rely on the strong hierarchy observed on road networks with travel times as the cost function, making it much more robust to metric changes. Our algorithm uses the fact that road networks can be partitioned into loosely connected regions. To find such partitions, we developed a new algorithm based on the notion of natural cuts, which are sparse regions separating much denser areas.
This approach is currently used by Bing Maps.


Talk 3 of the invited session Wed.3.H 3021
"Routing in road networks" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Buy Viagra Online has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.