Forscher beschleunigen Navigationssysteme um Faktor 100

Quelle:


1. http://www.pressetext.at/pte.mc?pte=070430014
pte070430014
Computer/Telekommunikation, Auto/Verkehr
Forscher beschleunigen Navigationssysteme um Faktor 100
Netz aus 11.000 Transitknoten garantiert schnellsten Weg
Weg wird mit Hilfe vorberechneter Infos zu den nächsten Transitknoten
(Rauten) berechnet
Saarbrücken (pte/30.04.2007/12:00) - Wissenschaftler am
Max-Planck-Institut für Informatik http://www.mpi-inf.mpg.de 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.
"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.
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.
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. (Ende)
Aussender: pressetext.deutschland
Redakteur: Andreas List
email: list@pressetext.com
Tel. ++43-1-81140-313