idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
idw - Informationsdienst
Wissenschaft
Wer eine Ansage seiner Navigationshilfe verpasst, bringt nicht nur sich
selbst in Hektik, sondern auch den Routenplaner: Manchmal minutenlang
sucht ein gängiges Navigationsprogramm einen neuen Weg, der die
Reisenden auf schnellstem Weg zum Ziel bringt. 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
http://www.mpg.de/bilderBerichteDokumente/multimedial/ideen/index.html - Ideen, das Kapital von morgen (Serie)
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
Merkmale dieser Pressemitteilung:
Informationstechnik, Verkehr / Transport
überregional
Forschungsergebnisse, Forschungsprojekte
Deutsch
Sie können Suchbegriffe mit und, oder und / oder nicht verknüpfen, z. B. Philo nicht logie.
Verknüpfungen können Sie mit Klammern voneinander trennen, z. B. (Philo nicht logie) oder (Psycho und logie).
Zusammenhängende Worte werden als Wortgruppe gesucht, wenn Sie sie in Anführungsstriche setzen, z. B. „Bundesrepublik Deutschland“.
Die Erweiterte Suche können Sie auch nutzen, ohne Suchbegriffe einzugeben. Sie orientiert sich dann an den Kriterien, die Sie ausgewählt haben (z. B. nach dem Land oder dem Sachgebiet).
Haben Sie in einer Kategorie kein Kriterium ausgewählt, wird die gesamte Kategorie durchsucht (z.B. alle Sachgebiete oder alle Länder).
