21802

Neue Methode beschleunigt Routenplanung bei Navigationssystemen

01.05.2007 | 13:50 Uhr |

Die Routenberechnung von Navigationssystemen kann zukünftig um den Faktor 100 beschleunigt werden. Zu dieser neuen Erkenntnis gelangten Wissenschaftler des Max-Planck-Instituts für Informatik.

Dabei werden zur Berechnung des optimalen Weges zwischen Start- und Zielpunkt nun so genannte Transitknoten hinzugezogen. Das Navigationssystem sucht die Transitknoten die am dichtesten am Start- und Zielpunkt liegen – meist weniger als zwei Dutzend. Der Routenplaner schafft es dann in wenigen Millionstel Sekunden, die Entfernung zwischen den entsprechenden Knoten zu berechnen.

„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 Forscher Stefan Funke. „Bei unserer Methode wird die Zahl der Knotenpunkte, die ein Navigationsprogramm berücksichtigen muss, drastisch reduziert“, so Funke. Dabei würden von fast 20 Millionen Knotenpunkten im westeuropäischen Straßennetz lediglich 11.000 Transitknoten übrig bleiben, was die Berechnungen deutlich beschleunigt. Das Navigationssystem soll die Entfernung zwischen den Knoten künftig über eine Tabelle errechnen können.

Laut Funke könne derzeit nicht garantiert werden, dass die vom Navigationssystem errechnete Route wirklich die schnellste oder kürzeste ist, da sich der Routenplaner noch von Knotenpunkt zu Knotenpunkt vortasten muss. Während am Start und Zielpunkt noch alle Straßen berücksichtigt werden, finden in der Mitte der Strecke meist nur die großen Straßen ihren Weg in die Routenplanung. „Hierbei wird oft eine Abkürzung übersehen, die beispielsweise zwei Autobahnen miteinander verbindet.“, so Funke. Da die neue Methode wesentlich mehr Straßen berücksichtigt, soll sich dies vor allem für Logistikunternehmen auszahlen. „Mit unserem Algorithmus können auch relativ rechenschwache mobile Navigationssysteme die Route in Sekundenbruchteilen neu bestimmen, was jetzt manchmal noch Minuten dauert“, sagt Funke.

0 Kommentare zu diesem Artikel
21802