Schnelle und genaue Routenplanung
- Ansprechperson:
G. V. Batz, M. Kobitzsch, D. Luxen, D. Schieferdecker, P. Sanders
Die Berechnung kürzester Pfade in einem Graphen ist ein bekanntes Problem aus der Graphentheorie. Eine der naheliegendsten praktischen Anwendungen ist die Routenplanung in einem Straßennetz, also die Bestimmung einer optimalen Route von einem Start- zu einem Zielort. Wir gehen davon aus, dass ein gegebenes Straßennetz sich nicht sehr oft ändert und dass viele Start-Ziel-Suchen im gleichen Straßennetz durchgeführt werden. Dadurch lohnt es sich, zunächst etwas Zeit in einen Vorverarbeitungsschritt zu investieren, der dann alle nachfolgenden Suchanfragen beschleunigt.
Für das Problem der Routenplanung stellen wir eine neue Beschleunigungstechnik vor, die die hierarchischen Eigenschaften von
realen Straßengraphen ausnutzt. In einem Vorverarbeitungsschritt untersuchen wir das gegebene Straßennetz, um eine hierarchische
Darstellung zu gewinnen und aufzubereiten. Der Routenplanungsalgorithmus profitiert dann von den gewonnenen Daten. Es handelt sich dabei um eine Anpassung der bidirektionalen Variante des Algorithmus von Dijkstra, die den Suchraum deutlich einschränkt.
In mehreren Experimenten beschäftigen wir uns mit der Berechnung von schnellsten Routen in Westeuropa und den USA. Beide Netze bestehen aus jeweils ca. 20 Millionen Knoten. Die Vorverarbeitung dieser Straßennetze dauert eine halbe Stunde, wobei nur ein linearer zusätzlicher Platzbedarf anfällt. Suchanfragen dauern dann ungefähr 2,5 Millisekunden, um optimale Routen zu bestimmen. Dies ist mehr als 4 000 mal schneller als die Verwendung von Dijkstras Algorithmus. Es gibt zahlreiche Möglichkeiten, diesen Ansatz weiter zu verbessern und auszubauen.