Auf schnellstem Weg durchs Straßennetz

Wer einen Routenplaner im Auto hat, braucht vor einer roten Ampel nicht mehr hektisch Karten zu lesen. Dafür gerät die Navigationshilfe manchmal in Hektik – wenn der Fahrer nämlich einen angesagten Abzweig verpasst. Eine ganze Weile rechnet das Navigationsprogramm dann, ehe es einen neuen Weg verkündet.

Wissenschaftler vom Max-Planck-Institut für Informatik in Saarbrücken haben jetzt zusammen mit Forschern der Universität Karlsruhe eine Methode entwickelt, die Navigationshilfen um das 100fache beschleunigen könnte. Sie ermitteln dazu eine relativ kleine Menge so genannter Transitknoten, etwa 11 000 für das Straßennetz Westeuropas.

Die Navigationshilfe sucht dann die Transitknoten, die am dichtesten an 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.

Kürzeste Wege schnell und zuverlässig zu ermitteln, ist für Logistikunternehmen ein Kostenfaktor. Aber auch Routenplaner im Internet könnten die Tausende von Anfragen, mit denen sie pro Sekunde bestürmt werden, auf diese Weise besser bewältigen. (dsc)