Forum für Wissenschaft, Industrie und Wirtschaft

Hauptsponsoren:     3M 
Datenbankrecherche:

 

Informatiker entwickeln extrem schnellen Routenplaner

27.04.2007
Der Weg ist das Ziel

Viele Wege führen Autofahrer von Karlsruhe nach Berlin, Lyon oder Rom. Um zu wissen, welcher der schnellste ist, halten sie sich an Routenplaner – die sind aber oft noch ungenau oder zu langsam. Sie zu verbessern ist das Ziel, das Professor Dr. Peter Sanders und Dominik Schultes vom Institut für Theoretische Informatik an der Universität Karlsruhe durch praxisorientierte Algorithmenforschung verfolgen.

Das Thema ist brandaktuell und wissenschaftlich heiß umkämpft, auch wenn es sich bei der Berechnung von kürzesten Wegen um ein klassisches Problem aus der Graphentheorie handelt, zu dem bereits 1959 eine Lösungsmöglichkeit vorgestellt wurde. Die Karlsruher Algorithmen-Experten begannen im August vergangenen Jahres, an einer bis zu einer Million mal schnelleren Technik namens „Transit Node Routing“ zu arbeiten.

„Wir investieren etwas Zeit in einen einmaligen Vorberechnungsschritt, der dann alle nachfolgenden Suchanfragen deutlich beschleunigt“, sagt Schultes. Dabei spielt eine einfache Alltagsbeobachtung eine zentrale Rolle: Wenn man eine längere Reise unternimmt, verlässt man seinen Startpunkt immer über einen von wenigen in Frage kommenden wichtigen Verkehrsknotenpunkten - im Falle von Karlsruhe beispielsweise die Auffahrten der A5 und die Rheinbrücke. Von da aus schlägt man nur die jeweils relevanten Verkehrsknotenpunkte jeder beliebigen anderen weiter entfernt gelegenen Stadt oder alle Abstände zwischen diesen nach. Der neue Ansatz ermöglicht durchschnittliche Suchzeiten von etwa fünf Millionstelsekunden. Er bescherte den Karlsruher Wissenschaftlern, die in diesem Projekt mit Kollegen des Max-Planck-Institut für Informatik kooperierten, bereits den ersten Platz beim letzten Programmierwettbewerb „DIMACS Implementation Challenge“. Dabei konkurrierten die weltweit besten Routingverfahren miteinander. Internationale Beachtung findet das „Transit Node Routing“ derzeit auch durch eine Veröffentlichung in der aktuellen Ausgabe der amerikanischen „Science“, einem der weltweit angesehensten Wissenschaftsmagazine.

Ein zuvor von Sanders und Schultes entwickeltes Verfahren, in dem große Straßennetze in hierarchische Netzwerkstrukturen aufgeteilt wurden - von der kleinen, nur von lokalen Anwohnern benötigten Straße bis hin zur wichtigen Fernverkehrsverbindung - dient den Wissenschaftlern nun zur Bestimmung der relevanten Verkehrsknotenpunkte rund um einen vorgegebenen Startpunkt.

Der Vorverarbeitungsschritt für das neue Verfahren nimmt selbst nicht sehr viel Zeit in Anspruch. In mehreren Experimenten beschäftigten sich Sanders und Schultes mit der Berechnung von schnellsten Routen in Westeuropa und den USA. Beide Netze bestehen aus jeweils etwa 20 Millionen Knoten. „Um solche großen Netze zu berechnen, müssen einmalig wenige Stunden investiert werden“ so Schultes. „Doch da sich die Straßennetze schließlich nicht täglich ändern, ist diese Berechnungszeit hinnehmbar, wenn man anschließend von superschnellen Suchanfragen profitieren kann“.

Kommerzielle Systeme verwenden heute Beschleunigungstechniken, die nicht selten auf Kosten der Optimalität gehen. Das Ergebnis einer Suchanfrage wird zwar schneller präsentiert als noch vor Jahren, ist aber dafür oftmals ungenauer. Die Karlsruher Wissenschaftler wissen um die einzigartige Schnelligkeit ihres Verfahrens bei gleichbleibend hoher Genauigkeit, sehen aber noch Verbesserungsmöglichkeiten hinsichtlich der Flexibilität und der Erweiterung der Funktionalität. So arbeiten sie bereits an Methoden, die auch kurzfristige Gründe für die Änderung einer Strecke berücksichtigen, zum Beispiel einen Stau.

Nähere Informationen:
Institut für Theoretische Informatik
Universität Karlsruhe (TH)
Professor Dr. Peter Sanders
Tel. +49 721 608 7580
E-Mail sanders@ira.uka.de1
Dominik Schultes
Tel. +49 721 608-6603
E-Mail schultes@ira.uka.de

| Universität Karlsruhe (TH)
Weitere Informationen:
http://www.uni-karlsruhe.de

Weitere Berichte zu: Routenplaner Routing Startpunkt Suchanfragen

Weitere Nachrichten aus der Kategorie Informationstechnologie:

nachricht Der Krümmung einen Schritt voraus
27.06.2017 | Institute of Science and Technology Austria

nachricht KogniHome feiert die Wohnung der Zukunft
26.06.2017 | Universität Bielefeld

Alle Nachrichten aus der Kategorie: Informationstechnologie >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Vorbild Delfinhaut: Elastisches Material vermindert Reibungswiderstand bei Schiffen

Für eine elegante und ökonomische Fortbewegung im Wasser geben Delfine den Wissenschaftlern ein exzellentes Vorbild. Die flinken Säuger erzielen erstaunliche Schwimmleistungen, deren Ursachen einerseits in der Körperform und andererseits in den elastischen Eigenschaften ihrer Haut zu finden sind. Letzteres Phänomen ist bereits seit Mitte des vorigen Jahrhunderts bekannt, konnte aber bislang nicht erfolgreich auf technische Anwendungen übertragen werden. Experten des Fraunhofer IFAM und der HSVA GmbH haben nun gemeinsam mit zwei weiteren Forschungspartnern eine Oberflächenbeschichtung entwickelt, die ähnlich wie die Delfinhaut den Strömungswiderstand im Wasser messbar verringert.

Delfine haben eine glatte Haut mit einer darunter liegenden dicken, nachgiebigen Speckschicht. Diese speziellen Hauteigenschaften führen zu einer signifikanten...

Im Focus: Kaltes Wasser: Und es bewegt sich doch!

Bei minus 150 Grad Celsius flüssiges Wasser beobachten, das beherrschen Chemiker der Universität Innsbruck. Nun haben sie gemeinsam mit Forschern in Schweden und Deutschland experimentell nachgewiesen, dass zwei unterschiedliche Formen von Wasser existieren, die sich in Struktur und Dichte stark unterscheiden.

Die Wissenschaft sucht seit langem nach dem Grund, warum ausgerechnet Wasser das Molekül des Lebens ist. Mit ausgefeilten Techniken gelingt es Forschern am...

Im Focus: Hyperspektrale Bildgebung zur 100%-Inspektion von Oberflächen und Schichten

„Mehr sehen, als das Auge erlaubt“, das ist ein Anspruch, dem die Hyperspektrale Bildgebung (HSI) gerecht wird. Die neue Kameratechnologie ermöglicht, Licht nicht nur ortsaufgelöst, sondern simultan auch spektral aufgelöst aufzuzeichnen. Das bedeutet, dass zur Informationsgewinnung nicht nur herkömmlich drei spektrale Bänder (RGB), sondern bis zu eintausend genutzt werden.

Das Fraunhofer IWS Dresden entwickelt eine integrierte HSI-Lösung, die das Potenzial der HSI-Technologie in zuverlässige Hard- und Software überführt und für...

Im Focus: Can we see monkeys from space? Emerging technologies to map biodiversity

An international team of scientists has proposed a new multi-disciplinary approach in which an array of new technologies will allow us to map biodiversity and the risks that wildlife is facing at the scale of whole landscapes. The findings are published in Nature Ecology and Evolution. This international research is led by the Kunming Institute of Zoology from China, University of East Anglia, University of Leicester and the Leibniz Institute for Zoo and Wildlife Research.

Using a combination of satellite and ground data, the team proposes that it is now possible to map biodiversity with an accuracy that has not been previously...

Im Focus: Klima-Satellit: Mit robuster Lasertechnik Methan auf der Spur

Hitzewellen in der Arktis, längere Vegetationsperioden in Europa, schwere Überschwemmungen in Westafrika – mit Hilfe des deutsch-französischen Satelliten MERLIN wollen Wissenschaftler ab 2021 die Emissionen des Treibhausgases Methan auf der Erde erforschen. Möglich macht das ein neues robustes Lasersystem des Fraunhofer-Instituts für Lasertechnologie ILT in Aachen, das eine bisher unerreichte Messgenauigkeit erzielt.

Methan entsteht unter anderem bei Fäulnisprozessen. Es ist 25-mal wirksamer als das klimaschädliche Kohlendioxid, kommt in der Erdatmosphäre aber lange nicht...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

IHR
JOB & KARRIERE
SERVICE
im innovations-report
in Kooperation mit academics
Veranstaltungen

Internationale Konferenz zu aktuellen Fragen der Stammzellforschung

27.06.2017 | Veranstaltungen

Fraunhofer FKIE ist Gastgeber für internationale Experten Digitaler Mensch-Modelle

27.06.2017 | Veranstaltungen

Future Security Conference 2017 in Nürnberg - Call for Papers bis 31. Juli

26.06.2017 | Veranstaltungen

 
VideoLinks
B2B-VideoLinks
Weitere VideoLinks >>>
Aktuelle Beiträge

Vorbild Delfinhaut: Elastisches Material vermindert Reibungswiderstand bei Schiffen

27.06.2017 | Materialwissenschaften

Kaltes Wasser: Und es bewegt sich doch!

27.06.2017 | Biowissenschaften Chemie

Weniger Schadstoffe im Heizkessel: Smartes Verbrennungskonzept vermindert Schadstoffemissionen

27.06.2017 | Energie und Elektrotechnik