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" [...]


  online loans . On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.