Fast Route Planning

Dieser Vortrag stellt den schnellen Routingalgorithmus Contraction Hierarchies [1] und eine spezielle Implementierung für Mobilgeräte vor. Contraction Hierarchies sind die derzeitige Grundlage unserer täglichen Forschungsarbeit. Das Verfahren ist auf einem Westeuropäischen Straßennetz etwa 20.000 mal schneller als Dikstras klassischer Algorithmus, was bedeutet, dass eine Suchanfrage deutlich schneller als in einer Millisekunde beantwortet werden kann. Wird nur die Distanz und nicht eine Route abgefragt, dann verbrauchen Contraction Hierarchies sogar weniger Speicher für die Datenstrukturen als Dijkstras klassischer Algorithmus. Das Problem der Suche nach kürzesten Wegen zwischen zwei Punkten wird klassischer Weise mit Dijkstras Algorithmus gelöst. Dieses Verfahren ist seit Jahrzehnten bekannt, funktioniert aber zu langsam für große Straßennetzwerke, die große Länder oder ganze Kontinent abdecken. Teilweise wird deshalt sogar darauf verzichten wirklich eine kürzeste oder schnellste Route zu finden. Die heutige algorithmische Forschung untersucht exakte Algorithmen, die immer optimale Routen berechnen. Diese Verfahren sind nicht nur exakt, sondern auch deutlich schneller als die meisten in der Industrie eingesetzten Verfahren. In unserer Forschung untersuchen wir hierarchische Algorithmen, die eine intensive Vorberechnungsphase verwenden.

[1] Geisberger et al: Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks, WEA 2008.