Auf schnellstem Weg durchs Straßennetz

Mit einer neuen Methode können Navigationsgeräte den Weg um das 100fache schneller berechnen als bisher.

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 sogenannter 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 Tausenden von Anfragen, mit denen sie pro Sekunde bestürmt werden, auf diese Weise besser bewältigen.

Abb.1: Um sich in diesem Wirrwarr zurecht zu finden, helfen einem Routenplaner jetzt Orientierungspunkte. Künftig ermittelt er den kürzesten Weg zwischen Start und Ziel (Fähnchen) mithilfe vorberechneter Informationen zu den nächstgelegen Transitknoten (Rauten). (Bild: Max-Planck-Institut für Informatik / Universität Karlsruhe)

Wer sein Auto aus der heimischen Garage gesteuert hat, passiert in der Regel immer wieder dieselben markanten Punkte. Will er in Richtung Norden, mag das eine naheliegende Autobahnauffahrt sein, in Richtung Süden vielleicht auch. Und zu allen westlichen Zielen bringt ihn möglicherweise ein Verteilerkreis, während er gen Osten immer eine bestimmte Kreuzung quert. Aus dieser Idee haben Wissenschaftler vom Max-Planck-Institut für Informatik eine Methode entwickelt, die den gegenwärtig schnellsten Routenplaner um einen Faktor 100 schlägt.

„Wir reduzieren die Zahl der Knotenpunkte, die ein solches Programm berücksichtigen muss, drastisch“, sagt Stefan Funke, einer der beteiligten Forscher vom Max-Planck-Institut für Informatik. Von knapp 20 Millionen Knotenpunkten im Straßennetz Westeuropas bleiben nur noch gut 11.000 Transitknoten übrig. Die Entfernungen zwischen diesen Knoten braucht ein Routenplaner nur noch in einer Tabelle nachzuschlagen. „Das Programm wird auf diese Weise um Größenordnungen schneller, was mit vorherigen Ansätzen nicht möglich gewesen wäre“, sagt Holger Bast, der andere Part des Saarbrücker Forscherduos.

Bislang tastet sich ein Routenplaner von Knotenpunkt zu Knotenpunkt im Straßennetz. Und obwohl er in der Mitte zwischen zwei Zielen nur noch Autobahnen und Bundesstraßen berücksichtigt, braucht er dafür 100 Mal länger als für die Rechnung mit Transitknoten. „Manche kommerziellen Navigationshilfen rechnen zwar schnell, ermitteln aber nicht immer die beste Route“, sagt Bast. Die neue Methode liefert dagegen immer die beste Strecke, was sich insbesondere bei Logistikunternehmen in barer Münze auszahlt. „Mit unserem Algorithmus können auch relativ rechenschwache mobile Navigationssysteme die Route in Sekundenbruchteilen neu bestimmen, was jetzt manchmal noch Minuten dauert“, sagt Funke.

Bleibt noch ein Detail: 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, z. B. Berlin Tiergarten und Berlin Mitte, müssen die Forscher anders vorgehen. Sie könnten hier herkömmliche Methoden einsetzen, da diese für kurze Strecken relativ schnell berechnen. „Wir favorisieren aber eine hierarchische Abfrage“, sagt Funke. Damit meint er, dass das Programm in diesem Fall mit einem etwas feineren Netz von Transitknoten rechnen soll. Das feinere Netz für Westeuropa haben die Wissenschaftler zum Beispiel aus gut 300.000 Transitknoten geknüpft. Und noch kürzere Distanzen fängt ein Netz von knapp drei Millionen Knoten auf. „Auf diese Weise können wir extrem schnell die beste Route zwischen beliebigen Punkten bestimmen“, sagt Bast.

Quelle: MPG/[PH]

Weitere Infos:

• Originalveröffentlichung:
  Holger Bast, Stefan Funke, Peter Sanders und Dominik Schultes, Fast Routing in Road Networks with Transit Nodes, Science 316, 566 (2007).
  http://dx.doi.org/10.1126/science.1137521.
• Max-Planck-Gesellschaft zur Förderung der Wissenschaften e.V.:
  http://www.mpg.de
• Max-Planck-Institut für Informatik, Saarbrücken:
  http://www.mpi-inf.mpg.de