Forscher beschleunigen Navigationshilfen

Wissenschaftler vom Max-Planck-Institut für Informatik in Saarbrücken und der Universität Karlsruhe haben eine Methode entwickelt, die Navigationshilfen um das 100-fache beschleunigen könnte. "Wir reduzieren die Zahl der Knotenpunkte, die ein solches Programm berücksichtigen muss, drastisch", sagt Forscher Stefan Funke. Von knapp 20 Mio. Knotenpunkten im Straßenverkehr Westeuropas blieben beim neuen Verfahren nur rund 11.000 übrig. Das Navigationsgerät suche bei einer Routen-Neuberechnung dann jene Transitknoten, die am dichtesten an Start- und Zielpunkt liegen. Die Berechnung der Entfernungen zwischen diesen Knoten schaffe ein Routenplaner in wenigen Millionstel Sekunden. Bisher brauche ein Routenplaner dafür 100-mal länger, da er sich von Knotenpunkt zu Knotenpunkt vortastet. Laut Funke könnten mit dem Algorithmus auch relativ rechenschwache mobile Navigationssysteme die Route in Sekundenbruchteilen neu bestimmen. (ab)