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 Weltrekord: Jülicher Forscher simulieren Quantencomputer mit 46 Qubits
15.12.2017 | Forschungszentrum Jülich GmbH

nachricht Neues Epidemie-Management-System bekämpft Affenpocken-Ausbruch in Nigeria
15.12.2017 | Helmholtz-Zentrum für Infektionsforschung

Alle Nachrichten aus der Kategorie: Informationstechnologie >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

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

Im Focus: Immunsystem - Blutplättchen können mehr als bislang bekannt

LMU-Mediziner zeigen eine wichtige Funktion von Blutplättchen auf: Sie bewegen sich aktiv und interagieren mit Erregern.

Die aktive Rolle von Blutplättchen bei der Immunabwehr wurde bislang unterschätzt: Sie übernehmen mehr Funktionen als bekannt war. Das zeigt eine Studie von...

Im Focus: First-of-its-kind chemical oscillator offers new level of molecular control

DNA molecules that follow specific instructions could offer more precise molecular control of synthetic chemical systems, a discovery that opens the door for engineers to create molecular machines with new and complex behaviors.

Researchers have created chemical amplifiers and a chemical oscillator using a systematic method that has the potential to embed sophisticated circuit...

Im Focus: Nanostrukturen steuern Wärmetransport: Bayreuther Forscher entdecken Verfahren zur Wärmeregulierung

Der Forschergruppe von Prof. Dr. Markus Retsch an der Universität Bayreuth ist es erstmals gelungen, die von der Temperatur abhängige Wärmeleitfähigkeit mit Hilfe von polymeren Materialien präzise zu steuern. In der Zeitschrift Science Advances werden diese fortschrittlichen, zunächst für Laboruntersuchungen hergestellten Funktionsmaterialien beschrieben. Die hiermit gewonnenen Erkenntnisse sind von großer Relevanz für die Entwicklung neuer Konzepte zur Wärmedämmung.

Von Schmetterlingsflügeln zu neuen Funktionsmaterialien

Im Focus: Lange Speicherung photonischer Quantenbits für globale Teleportation

Wissenschaftler am Max-Planck-Institut für Quantenoptik erreichen mit neuer Speichertechnik für photonische Quantenbits Kohärenzzeiten, welche die weltweite...

Im Focus: Long-lived storage of a photonic qubit for worldwide teleportation

MPQ scientists achieve long storage times for photonic quantum bits which break the lower bound for direct teleportation in a global quantum network.

Concerning the development of quantum memories for the realization of global quantum networks, scientists of the Quantum Dynamics Division led by Professor...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

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

Call for Contributions: Tagung „Lehren und Lernen mit digitalen Medien“

15.12.2017 | Veranstaltungen

Die Stadt der Zukunft nachhaltig(er) gestalten: inter 3 stellt Projekte auf Konferenz vor

15.12.2017 | Veranstaltungen

Mit allen Sinnen! - Sensoren im Automobil

14.12.2017 | Veranstaltungen

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

Weltrekord: Jülicher Forscher simulieren Quantencomputer mit 46 Qubits

15.12.2017 | Informationstechnologie

Wackelpudding mit Gedächtnis – Verlaufsvorhersage für handelsübliche Lacke

15.12.2017 | Verfahrenstechnologie

Forscher vereinfachen Installation und Programmierung von Robotersystemen

15.12.2017 | Energie und Elektrotechnik