Manchmal suchen gängige Navigationsprogramme minutenlang den Weg, der die Reisenden auf schnellstem Weg zum Ziel bringt. Doch es geht auch deutlich schneller: Deutsche Informatiker haben mit einem neuen Abfragesystem Navigationshilfen um das 100fache beschleunigt.
Bislang tastet sich ein Routenplaner im Straßennetz von Knotenpunkt zu Knotenpunkt, alleine 20 Millionen in Westeuropa. Auf kürzeren Strecken funktioniert das zwar ganz gut, die Planung längerer Reisen dauert auf diese Weise aber recht lange – obwohl der herkömmliche Routenplaner in der Mitte zwischen weit voneinander entfernten Punkten schon nur die Fernstraßen berücksichtigt. Und ist das Ergebnis schnell da, garantiert dies noch nicht die optimale Routenführung. „Manche kommerziellen Navigationshilfen rechnen zwar schnell, ermitteln dann aber nicht immer die schnellste Route“, erklärt Hannah Bast vom Max-Planck- Institut für Informatik.
Transitknoten als erste Abfrage
Bast und ihre Kollegen vom Max-Planck- Institut haben nun gemeinsam mit Forschern der Universität Karlsruhe eine andere Methode der Routenberechnung entwickelt. Im Mittelpunkt stehen dabei so genannte Transitknoten – markante Punkte, wie etwa eine Autobahnauffahrt oder ein Verteilerkreis, die Fahrer immer wieder passieren, wenn sie weiter entfernte Ziele ansteuern. Etwa 11.000 dieser Punkte haben die Forscher im Straßennetz Westeuropas ausfindig gemacht und definiert.
Die optimierte Navigationshilfe sucht nun zunächst 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. Entsprechend schell ist das Ergebnis da. Die neue Methode liefert zudem immer die beste Strecke, wie die Forscher erklären, was sich besonders für Logistikunternehmen bezahlt macht. Kürzeste Wege schnell und zuverlässig zu ermitteln, senkt nämlich deren Kosten.
Optimierung durch hierarchische Abfragen
Liegen Start und Ziel dicht beieinander – wie etwa in Berlin-Tiergarten und Berlin-Mitte -, reicht das weitmaschige Netz dieser Knoten allerdings nicht. Je nach Distanz arbeitet die Navigationshilfe dann mit 300.000 oder drei Millionen Knoten. „Mit diesem hierarchischen Vorgehen können wir extrem schnell die beste Route zwischen beliebigen Punkten bestimmen“, so Bast.
Nicht nur Navigationsgeräte für den mobilen Einsatz auch Routenplaner im Internet könnten damit optimiert werden. Denn dank der schnelleren Berechnung könnten sie die Tausenden von Anfragen, mit denen sie pro Sekunde bestürmt werden, auf diese Weise besser bewältigen.
(Max-Planck-Gesellschaft zur Förderung der Wissenschaften, 29.07.2009 – NPO)
