Neue Routenberechnung arbeitet mit Transitknoten
Vor allem rechenschwache Navigationssysteme haben mit der Routenberechnung zu kämpfen. Max-Planck-Forscher wollen nun die Rechenzeit durch eine einfachere Berechnungsmethode um das Hundertfache verkürzen
- sl
Saarbrücken, 15. Mai 2007 – Navigationssysteme brauchen mitunter eine ganze Weile, bis eine neue Route berechnet ist. Man braucht nur einmal eine Abzweigung zu verpassen, dann rechnet das Gerät lange herum, ehe es einen neuen Weg verkündet. Wissenschaftler vom Max-Planck-Institut für Informatik in Saarbrücken haben jetzt zusammen mit Forschern der Uni Karlsruhe eine Methode entwickelt, die Navigationshilfen um das Hundertfache beschleunigen könnte.
Tabelle statt Rechenarbeit
Während Navigationssysteme bisher den Weg vom Startpunkt zum Ziel jedes Mal neu errechnen, indem die Fahrtzeiten auf verschiedenen Strecken verglichen werden, haben die Forscher aus Saarbrücken eine andere Lösung im Auge: Sie legen eine relativ kleine Zahl so genannter Transitknoten fest – etwa 11.000 für das Straßennetz von ganz Westeuropa. Das Navi sucht die Transitknoten, die am dichtesten an Start und Ziel einer Reise liegen. Die Entfernungen zwischen diesen Knoten braucht ein Routenplaner nur noch in einer Art Tabelle nachzuschlagen. Das Programm wird auf diese Weise deutlich schneller.
Neue Routenberechnung arbeitet mit Transitknoten (1 Bilder)
Eine neue Rechenmethode soll die Berechnung von Routen vereinfachen
Mehr Knoten für kürzere Distanzen
Was passiert auf kurzen Strecken? Zwischen Berlin und Barcelona funktioniert der Routenplaner schnell und zuverlässig, wenn er nur das grobe Netz aus Transitknoten berücksichtigt. Liegen jedoch Start und Ziel zu dicht beieinander, zum Beispiel Berlin Tiergarten und Berlin Mitte, müssen die Forscher anders vorgehen. In diesem Fall rechnet das Programm mit einem etwas feineren Netz von etwa 300.000 Transitknoten. Noch kürzere Distanzen fängt ein Netz von knapp drei Millionen Knoten auf. "Mit unserem Algorithmus können auch rechenschwache Navigationssysteme die Route in Sekundenbruchteilen neu bestimmen, was jetzt manchmal noch Minuten dauert", sagt Stefan Funke, einer der beteiligten Forscher. (imp)