Max-Planck-Institut für Informatik Navigationshilfen lassen sich um das 100-fache beschleunigen

Redakteur: Dipl.-Ing. (FH) Hendrik Härter

Wissenschaftler des Max-Planck-Instituts für Informatik haben eine Möglichkeit gefunden, wie Navigationshilfen um das 100-fache schneller zum Ziel führen können: Mit markanten Punkten, die am dichtesten zwischen Start- und Zielpunkt liegen.

Firmen zum Thema

Forscher haben eine Idee entwickelt, wie Navigationshilfen um das 100-fache beschleunigt werden können
Forscher haben eine Idee entwickelt, wie Navigationshilfen um das 100-fache beschleunigt werden können
( Archiv: Vogel Business Media )

Die Forscher haben dazu gemeinsam mit Kollegen der Universität Karlsruhe relativ wenige Transitknoten ermittelt. Dies sind markante Punkte, wie etwa eine Autobahnauffahrt oder ein Verteilerkreis, die Fahrer immer wieder passieren, wenn sie weiter entfernte Ziele ansteuern.

Es gibt etwa 11.000 dieser Punkte im Straßennetz Westeuropas. Die Navigationshilfe sucht die Transitknoten, die am dichtesten an Start und Ziel einer Reise liegen. Das sind meist weniger als zwei Dutzend. Die Entfernungen zwischen diesen Knoten ermittelt der Routenplaner in wenigen Millionstel Sekunden aus Tabellen.

Schnellste Route zwischen beliebigen Punkten bestimmen

Liegen Start und Ziel dicht beieinander, wie bespielsweise Berlin Tiergarten und Berlin Mitte, reicht das weitmaschige Netz der Knoten nicht. Je nach Distanz arbeitet die Navigationshilfe dann mit 300.000 oder drei Mio. Knoten. „Mit diesem hierarchischen Vorgehen können wir extrem schnell die beste Route zwischen beliebigen Punkten bestimmen“, sagt Hannah Bast, die das neue Navigationssystem am Max-Planck-Institut für Informatik zusammen mit Stefan Funke entwickelt hat.

Derzeit hangelt sich ein Routenplaner von Knotenpunkt zu Knotenpunkt durch das Wirrwarr von Straßen. Quelle: Max-Planck-Institut für Informatik/Universität Karlsruhe. (Archiv: Vogel Business Media)

Bislang tastet sich ein Routenplaner im Straßennetz von Knotenpunkt zu Knotenpunkt, alleine 20 Mio. in Westeuropa. Auf kürzeren Strecken funktioniert das zwar ganz gut, die Planung längerer Reisen dauert auf diese Weise aber viel länger als mit den Transitknoten, obwohl der herkömmliche Routenplaner in der Mitte zwischen weit voneinander entfernten Punkten nur Fernstraßen berücksichtigt.

(ID:312711)