Navi-Systeme um Faktor 100 schneller?
Forscher beschleunigen Routen-Algorithmus

Wissenschaftler am Max-Planck-Institut für Informatik haben eine Methode entwickelt, um die Routenberechnung von Navigationssystemen um den Faktor 100 zu beschleunigen. Bei der Erstellung des optimalen Weges zwischen zwei Punkten werden so genannte Transitknoten herangezogen. Die Navigationshilfe sucht dann die Transitknoten, die am dichtesten am Start und Ziel einer Reise liegen.

"Die Idee hinter den Transitknoten ist, dass man besonders wichtige Punkte im Straßennetz als fixe Verkehrspunkte definiert. Dazu zählen Autobahnknoten, Verteilerkreise in einer Großstadt oder wichtige Kreuzungen von Landstraßen", erläutert Stefan Funke, einer der beteiligten Forscher. "Bei unserer Methode wird die Zahl der Knotenpunkte, die ein Navigationsprogramm berücksichtigen muss, drastisch reduziert", so Funke. Von knapp 20 Mio. Knotenpunkten im Straßennetz Westeuropas bleiben rund 11.000 Transitknoten übrig. Die Entfernungen zwischen diesen Knoten liegen dem Navigationssystem in einer Tabelle vor.

Die beste Strecke in Sekundenbruchteilen
Derzeit tasten sich Routenplaner bei der Berechnung von Knotenpunkt zu Knotenpunkt und "können dabei nicht garantieren, dass die angegebene Route wirklich die schnellste bzw. kürzeste ist", meint Funke. Am Start und Zielpunkt werden zwar alle Straßen berücksichtigt, in der Mitte der Strecke jedoch nur die großen. "Hierbei wird oft eine Abkürzung übersehen, die beispielsweise zwei Autobahnen miteinander verbindet." Die neue Methode liefert dagegen immer die beste Strecke, was sich insbesondere bei Logistikunternehmen in barer Münze auszahlt. "Mit unserem Algorithmus können auch relativ rechenschwache mobile Navigationssysteme die Route in Sekundenbruchteilen neu bestimmen, was jetzt manchmal noch Minuten dauert", sagt Funke.

Andere Systematik für Großstädte
Die neue Rechenmethode funktioniert optimal auf langen Strecken. Liegen jedoch Start und Ziel innerhalb einer Großstadt zu dicht beieinander, müssen die Forscher anders vorgehen. Sie könnten hier herkömmliche Methoden einsetzen, da diese für kurze Strecken relativ schnell berechnen. "Wir favorisieren allerdings eine hierarchische Abfrage", sagt Funke und meint damit, dass das Programm in diesem Fall mit einem etwas feineren Netz von etwa 300.000 Transitknoten rechnen soll. Und noch kürzere Distanzen fängt ein Netz von knapp drei Mio. Knoten auf. "Auf diese Weise können wir extrem schnell die beste Route zwischen beliebigen Punkten bestimmen", so der Forscher. (pte/red)