• Schalter wissen.de
  • Schalter wissenschaft
  • Schalter scinexx
  • Schalter scienceblogs
  • Schalter damals
  • Schalter natur
Scinexx-Logo
Logo Fachmedien und Mittelstand
Scinexx-Claim
Facebook-Claim
Google+ Logo
Twitter-Logo
YouTube-Logo
Feedburner Logo
Sonntag, 26.03.2017
Hintergrund Farbverlauf Facebook-Leiste Facebook-Leiste Facebook-Leiste
Scinexx-Logo Facebook-Leiste

Navigation wird schneller

Neue Methode beschleunigt Navigationssysteme um das 100fache

Auch Navigationshilfen geraten manchmal in Hektik – beispielsweise dann, wenn der Fahrer einen angesagten Abzweig verpasst. Eine ganze Weile rechnet das Navigationsprogramm dann, ehe es einen neuen Weg verkündet. Jetzt haben Wissenschaftler eine Methode entwickelt, die Navigationshilfen um das 100fache beschleunigen könnte. Für Logistikunternehmen aber auch Routenplaner im Netz wäre dieses jetzt in „Science“ veröffentlichte Verfahren ein großer Fortschritt
Navigationssystem

Navigationssystem

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.

Weniger Knotenpunkte – schnelleres Ergebnis


„Wir reduzieren die Zahl der Knotenpunkte, die ein solches Programm berücksichtigen muss, drastisch", erklärt Stefan Funke vom Max-Planck-Institut für Informatik in Saarbrücken. Zusammen mit Forschern der Universität Karlsruhe entwickelten er und seine Kollegen die neue Methode. Von knapp 20 Millionen Knotenpunkten im Straßennetz Westeuropas bleiben dabei 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.


Knotennetz im Nahbereich feiner


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, beispielsweise 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.
(MPG, 30.04.2007 - NPO)
 
Printer IconShare Icon