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 Starke IT-Sicherheit für das Auto der Zukunft – Forschungsverbund entwickelt neue Ansätze
25.05.2018 | Universität Ulm

nachricht Diagnose per Computer: Gefährliche Krankheitserreger mithilfe maschinellen Lernens erkennen
23.05.2018 | 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: Starke IT-Sicherheit für das Auto der Zukunft – Forschungsverbund entwickelt neue Ansätze

Je mehr die Elektronik Autos lenkt, beschleunigt und bremst, desto wichtiger wird der Schutz vor Cyber-Angriffen. Deshalb erarbeiten 15 Partner aus Industrie und Wissenschaft in den kommenden drei Jahren neue Ansätze für die IT-Sicherheit im selbstfahrenden Auto. Das Verbundvorhaben unter dem Namen „Security For Connected, Autonomous Cars (SecForCARs) wird durch das Bundesministerium für Bildung und Forschung mit 7,2 Millionen Euro gefördert. Infineon leitet das Projekt.

Bereits heute bieten Fahrzeuge vielfältige Kommunikationsschnittstellen und immer mehr automatisierte Fahrfunktionen, wie beispielsweise Abstands- und...

Im Focus: Powerful IT security for the car of the future – research alliance develops new approaches

The more electronics steer, accelerate and brake cars, the more important it is to protect them against cyber-attacks. That is why 15 partners from industry and academia will work together over the next three years on new approaches to IT security in self-driving cars. The joint project goes by the name Security For Connected, Autonomous Cars (SecForCARs) and has funding of €7.2 million from the German Federal Ministry of Education and Research. Infineon is leading the project.

Vehicles already offer diverse communication interfaces and more and more automated functions, such as distance and lane-keeping assist systems. At the same...

Im Focus: Mit Hilfe molekularer Schalter lassen sich künftig neuartige Bauelemente entwickeln

Einem Forscherteam unter Führung von Physikern der Technischen Universität München (TUM) ist es gelungen, spezielle Moleküle mit einer angelegten Spannung zwischen zwei strukturell unterschiedlichen Zuständen hin und her zu schalten. Derartige Nano-Schalter könnten Basis für neuartige Bauelemente sein, die auf Silizium basierende Komponenten durch organische Moleküle ersetzen.

Die Entwicklung neuer elektronischer Technologien fordert eine ständige Verkleinerung funktioneller Komponenten. Physikern der TU München ist es im Rahmen...

Im Focus: Molecular switch will facilitate the development of pioneering electro-optical devices

A research team led by physicists at the Technical University of Munich (TUM) has developed molecular nanoswitches that can be toggled between two structurally different states using an applied voltage. They can serve as the basis for a pioneering class of devices that could replace silicon-based components with organic molecules.

The development of new electronic technologies drives the incessant reduction of functional component sizes. In the context of an international collaborative...

Im Focus: GRACE Follow-On erfolgreich gestartet: Das Satelliten-Tandem dokumentiert den globalen Wandel

Die Satellitenmission GRACE-FO ist gestartet. Am 22. Mai um 21.47 Uhr (MESZ) hoben die beiden Satelliten des GFZ und der NASA an Bord einer Falcon-9-Rakete von der Vandenberg Air Force Base (Kalifornien) ab und wurden in eine polare Umlaufbahn gebracht. Dort nehmen sie in den kommenden Monaten ihre endgültige Position ein. Die NASA meldete 30 Minuten später, dass der Kontakt zu den Satelliten in ihrem Zielorbit erfolgreich hergestellt wurde. GRACE Follow-On wird das Erdschwerefeld und dessen räumliche und zeitliche Variationen sehr genau vermessen. Sie ermöglicht damit präzise Aussagen zum globalen Wandel, insbesondere zu Änderungen im Wasserhaushalt, etwa dem Verlust von Eismassen.

Potsdam, 22. Mai 2018: Die deutsch-amerikanische Satellitenmission GRACE-FO (Gravity Recovery And Climate Experiment Follow On) ist erfolgreich gestartet. Am...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

VideoLinks
Industrie & Wirtschaft
Veranstaltungen

Im Fokus: Klimaangepasste Pflanzen

25.05.2018 | Veranstaltungen

Größter Astronomie-Kongress kommt nach Wien

24.05.2018 | Veranstaltungen

22. Business Forum Qualität: Vom Smart Device bis zum Digital Twin

22.05.2018 | Veranstaltungen

VideoLinks
Wissenschaft & Forschung
Weitere VideoLinks im Überblick >>>
 
Aktuelle Beiträge

Berufsausbildung mit Zukunft

25.05.2018 | Unternehmensmeldung

Untersuchung der Zellmembran: Forscher entwickeln Stoff, der wichtigen Membranbestandteil nachahmt

25.05.2018 | Interdisziplinäre Forschung

Starke IT-Sicherheit für das Auto der Zukunft – Forschungsverbund entwickelt neue Ansätze

25.05.2018 | Informationstechnologie

Weitere B2B-VideoLinks
IHR
JOB & KARRIERE
SERVICE
im innovations-report
in Kooperation mit academics