Forscher beschleunigen Routenberechnung um Faktor 100

30. April 2007, 13:15
17 Postings

Netz aus 11.000 Transitknoten garantiert schnellsten Weg

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. Das sind meist weniger als zwei Dutzend. Die Entfernungen zwischen diesen Knoten zu berechnen, schafft ein Routenplaner in wenigen Millionstel Sekunden, heißt es in einer entsprechenden Aussendung.

Fix

"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, im pressetext-Gespräch. "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.

"Hierbei wird oft eine Abkürzung übersehen, die beispielsweise zwei Autobahnen miteinander verbindet."

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.

Optimal

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)

  • Artikelbild
Share if you care.