Neues Verfahren

Navigationsgeräte werden bis zu 100 Mal schneller

Zwei Informatiker haben ein Verfahren entwickelt, mit dem die Routenberechnung in Navigationsgeräten deutlich beschleunigt werden kann.

Die Routenplanung, d. h. die Berechnung des kürzesten bzw. schnellsten Wegs von A nach B, ist das Herzstück eines jeden Navigationsgeräts. Prof. Stefan Funke von der Uni Greifswald hat zusammen mit Dr. Bast vom Max-Planck-Institut für Informatik einen Durchbruch bei dieser komplexen Berechnung erzielt.

Die beiden Wissenschaftler haben in dem Projekt Ultrafast Shortest-Path Queries via Transit Nodes ein Verfahren entwickelt, das um den Faktor 100 schneller als der schnellste bislang bekannte Ansatz ist. Es errechnet mit Garantie den optimalen Weg.

Dies bedeutet, dass die Wartezeit nach Eingabe von Start- und Zielort, bis das Navigationsgerät den optimalen Weg berechnet hat, statt zehn bis 20 Sekunden nur noch den Bruchteil einer Sekunde beträgt. Betreiber von Routenplanern im Internet können zukünftig die gleiche Anzahl an Anfragen, für die bislang 100 Server nötig waren, mit nur einem Rechner bedienen.

Das Verfahren wurde inzwischen beim US-Patentamt angemeldet. Es hat den beiden Autoren den mit 25.000 Euro dotierten SaarLB-Wissenschaftspreis eingebracht. (dsc)