Auf schnellstem Weg durchs Straßennetz – Max-Planck-Forscher beschleunigen Navigationshilfen um das 100fache
Doch es geht auch deutlich schneller – mit einer Idee von Wissenschaftlern des Max-Planck-Instituts für Informatik, die Navigationshilfen um das 100fache beschleunigt.
Die Max-Planck-Forscher haben dazu gemeinsam mit Kollegen der Universität Karlsruhe relativ wenige Transitknoten ermittelt – 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 gibt es 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.
Liegen Start und Ziel dicht beieinander – etwa in Berlin Tiergarten und Berlin Mitte -, reicht das weitmaschige Netz der Knoten 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”, sagt Hannah Bast, die das neue Navigationssystem am Max-Planck-Institut für Informatik zusammen mit Stefan Funke entwickelt hat.
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 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.
“Manche kommerziellen Navigationshilfen rechnen zwar schnell, ermitteln aber nicht immer die schnellste Route”, sagt Hannah Bast. Die neue Methode liefert dagegen immer die beste Strecke, was sich besonders für Logistikunternehmen bezahlt macht. Kürzeste Wege schnell und zuverlässig zu ermitteln, senkt nämlich deren Kosten 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. (MI 0601-3878-BC-JK)
Kontakt:
Hannah Bast
Max-Planck-Institut für Informatik, Saarbrücken
Tel.: +49 681 9325-120
E-mail: bast@mpi-inf.mpg.de
Media Contact
Weitere Informationen:
http://www.mpg.de http://www.mpg.de/bilderBerichteDokumente/multimedial/ideen/index.htmlAlle Nachrichten aus der Kategorie: Informationstechnologie
Neuerungen und Entwicklungen auf den Gebieten der Informations- und Datenverarbeitung sowie der dafür benötigten Hardware finden Sie hier zusammengefasst.
Unter anderem erhalten Sie Informationen aus den Teilbereichen: IT-Dienstleistungen, IT-Architektur, IT-Management und Telekommunikation.
Neueste Beiträge
![](https://www.innovations-report.de/wp-content/uploads/2024/09/Recycling-360x240.jpg)
Das Potenzial alter Elektroautos nutzen
Bundesministerium für Bildung und Forschung fördert neues Graduiertenkolleg Circular E-Cars. Recycling als Chance für das Rheinische Revier. Weil in Elektroautos (E-Cars) im Vergleich zu herkömmlichen Automobilen deutlich mehr wertvolle Nichteisenmetalle…
![](https://www.innovations-report.de/wp-content/uploads/2024/09/Vewinger_Umesh-360x240.jpg)
Forscher erzeugen eindimensionales Gas aus Licht
Physiker der Universität Bonn und der Rheinland-Pfälzisch Technischen Universität Kaiserslautern-Landau (RPTU) haben ein eindimensionales Gas aus Licht erzeugt. Damit konnten sie erstmals theoretische Vorhersagen überprüfen, die für den Übergang in…
![](https://www.innovations-report.de/wp-content/uploads/2024/09/yBM-360x240.jpg)
Zwergplanet Ceres: Ursprung im Asteroidengürtel?
Hellgelbe Ablagerungen im Consus Krater zeugen von Ceres‘ kryovulkanischer Vergangenheit – und beleben die Diskussion um ihren Entstehungsort neu. Der Zwergplanet Ceres könnte seinen Ursprung im Asteroidengürtel haben – und…