Invited Session Wed.3.H 3021

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

Cluster 2: Combinatorial optimization [...]

Routing in road networks


Chair: Andrew Goldberg



Wednesday, 15:15 - 15:40 h, Room: H 3021, Talk 1

Peter Sanders
Advance route planning using contraction hierarchies

Coauthors: Veit Batz, Robert Geisberger, Moritz Kobitzsch, Dennis Luxen, Dennis Schieferdecker


Contraction hierarchies are a simple and powerful way to grasp the hierarchical structure of road networks allowing very fast routing. The talk introduces the technique and gives applications focussing on advanced techniques like taking time-dependent travel times into account or using multiple objective functions. We also discuss applications like fast distance table precomputation for logistics or ride sharing.



Wednesday, 15:45 - 16:10 h, Room: H 3021, Talk 2

Andrew Goldberg
The hub labeling algorithm

Coauthors: Ittai Abraham, Daniel Delling, Amos Fiat, Renato Werneck


The labeling approach to distance oracle design is to precompute a label for every vertex so that distances can be computed from the corresponding labels. This approach has been introduced by [Gavoille et al. '01], who also introduced the Hub Labeling algorithm (HL). HL has been further studied by [Cohen et al. '02].
We study HL in the context of graphs with small highway dimension (e.g., road networks). We show that under this assumption HL labels are small and the queries are sublinear. We also give an approximation algorithm for computing small HL labels that uses the fact that shortest path set systems have small VC-dimension.
Although polynomial-time, precomputation given by theory is too slow for continental-size road networks. However, heuristics guided by the theory are fast, and compute very small labels. This leads to the fastest currently known practical distance oracles for road networks. HL also has efficient (real-time) implementation inside of a relational database (e.g., in SQL).
%Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, and Renato Werneck.



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

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.


  There are three major facts that should be watched out for in all payday loans in the United States. What makes Viagra Strips better than other forms of this medicine is its easiness of usage.