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 »Lernlabor Cybersicherheit« startet in Weiden i. d. Oberpfalz
12.01.2017 | Fraunhofer-Gesellschaft

nachricht Klick-Tagebuch: App-Projekt der HdM erlaubt neuen Ansatz in Entwicklungsforschung
11.01.2017 | Hochschule der Medien Stuttgart

Alle Nachrichten aus der Kategorie: Informationstechnologie >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

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

Im Focus: Mit solaren Gebäudehüllen Architektur gestalten

Solarthermie ist in der breiten Öffentlichkeit derzeit durch dunkelblaue, rechteckige Kollektoren auf Hausdächern besetzt. Für ästhetisch hochwertige Architektur werden Technologien benötigt, die dem Architekten mehr Gestaltungsspielraum für Niedrigst- und Plusenergiegebäude geben. Im Projekt »ArKol« entwickeln Forscher des Fraunhofer ISE gemeinsam mit Partnern aktuell zwei Fassadenkollektoren für solare Wärmeerzeugung, die ein hohes Maß an Designflexibilität erlauben: einen Streifenkollektor für opake sowie eine solarthermische Jalousie für transparente Fassadenanteile. Der aktuelle Stand der beiden Entwicklungen wird auf der BAU 2017 vorgestellt.

Im Projekt »ArKol – Entwicklung von architektonisch hoch integrierten Fassadekollektoren mit Heat Pipes« entwickelt das Fraunhofer ISE gemeinsam mit Partnern...

Im Focus: Designing Architecture with Solar Building Envelopes

Among the general public, solar thermal energy is currently associated with dark blue, rectangular collectors on building roofs. Technologies are needed for aesthetically high quality architecture which offer the architect more room for manoeuvre when it comes to low- and plus-energy buildings. With the “ArKol” project, researchers at Fraunhofer ISE together with partners are currently developing two façade collectors for solar thermal energy generation, which permit a high degree of design flexibility: a strip collector for opaque façade sections and a solar thermal blind for transparent sections. The current state of the two developments will be presented at the BAU 2017 trade fair.

As part of the “ArKol – development of architecturally highly integrated façade collectors with heat pipes” project, Fraunhofer ISE together with its partners...

Im Focus: Mit Bindfaden und Schere - die Chromosomenverteilung in der Meiose

Was einmal fest verbunden war sollte nicht getrennt werden? Nicht so in der Meiose, der Zellteilung in der Gameten, Spermien und Eizellen entstehen. Am Anfang der Meiose hält der ringförmige Proteinkomplex Kohäsin die Chromosomenstränge, auf denen die Bauanleitung des Körpers gespeichert ist, zusammen wie ein Bindfaden. Damit am Ende jede Eizelle und jedes Spermium nur einen Chromosomensatz erhält, müssen die Bindfäden aufgeschnitten werden. Forscher vom Max-Planck-Institut für Biochemie zeigen in der Bäckerhefe wie ein auch im Menschen vorkommendes Kinase-Enzym das Aufschneiden der Kohäsinringe kontrolliert und mit dem Austritt aus der Meiose und der Gametenbildung koordiniert.

Warum sehen Kinder eigentlich ihren Eltern ähnlich? Die meisten Zellen unseres Körpers sind diploid, d.h. sie besitzen zwei Kopien von jedem Chromosom – eine...

Im Focus: Der Klang des Ozeans

Umfassende Langzeitstudie zur Geräuschkulisse im Südpolarmeer veröffentlicht

Fast drei Jahre lang haben AWI-Wissenschaftler mit Unterwasser-Mikrofonen in das Südpolarmeer hineingehorcht und einen „Chor“ aus Walen und Robben vernommen....

Im Focus: Wie man eine 80t schwere Betonschale aufbläst

An der TU Wien wurde eine Alternative zu teuren und aufwendigen Schalungen für Kuppelbauten entwickelt, die nun in einem Testbauwerk für die ÖBB-Infrastruktur umgesetzt wird.

Die Schalung für Kuppelbauten aus Beton ist normalerweise aufwändig und teuer. Eine mögliche kostengünstige und ressourcenschonende Alternative bietet die an...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

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

Aquakulturen und Fangquoten – was hilft gegen Überfischung?

16.01.2017 | Veranstaltungen

14. BF21-Jahrestagung „Mobilität & Kfz-Versicherung im Fokus“

12.01.2017 | Veranstaltungen

Leipziger Biogas-Fachgespräch lädt zum "Branchengespräch Biogas2020+" nach Nossen

11.01.2017 | Veranstaltungen

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

Weltweit erste Solarstraße in Frankreich eingeweiht

16.01.2017 | Energie und Elektrotechnik

Proteinforschung: Der Computer als Mikroskop

16.01.2017 | Biowissenschaften Chemie

Vermeintlich junger Stern entpuppt sich als galaktischer Greis

16.01.2017 | Physik Astronomie