Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Algorithm Engineering für Routenplanung

Antragstellerinnen / Antragsteller Professor Dr. Peter Sanders; Professorin Dr. Dorothea Wagner
Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2008 bis 2020
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 67847980
 
Erstellungsjahr 2018

Zusammenfassung der Projektergebnisse

Routenplanungssysteme wie Google, Apple oder Bing Maps, TomTom oder Garmin Navigationsgeräte beziehungsweise Fahrplanauskunftssysteme wie der DB Navigator gehören heute zu den meist benutzen Informationssystemen überhaupt. Nutzerinnen dieser Systeme erwarten heutzutage aber weit mehr als nur die Berechnung der schnellsten Route. Der Routenplaner der Zukunft berechnet im Bruchteil einer Sekunde eine Route, welche die individuellen Präferenzen und Optimalitätskriterien der Nutzerinnen berücksichtigt, aktualisiert die Route auf Basis der aktuellen Verkehrslage und kann unterschiedliche Verkehrsmittel in die Routenberechnung einbeziehen. Um diese Erwartungen zu erfüllen werden hochentwickelte, extrem schnelle, optimale Algorithmen für das Kernproblem der Routenplanung, die Berechnung eines kürzesten Weges, benötigt. Mit den Ergebnissen dieses Projektes haben wir entscheidend zur Erfüllung dieser Vision des „zukünftigen Routenplaners“ beigetragen. Die von uns vorgeschlagenen Algorithmen Contraction Hierarchies und Multi-Level Dijkstra für Routenplanung im Straßenverkehr, RAPTOR und Connection Scan Algorithm für Fahrplanauskunft, deren Verbesserungen und Weiterentwicklungen haben die Forschung und inzwischen auch die industrielle Praxis zum Thema Routenplanung geprägt. Routenplanungsalgorithmen werden heute als Aushängeschild für die Methodik des Algorithm Engineering gesehen. Einen entscheidenden Beitrag zu dieser Entwicklung haben ehemalige Doktoranden aus diesem Projekt bei Microsoft Research, Apple, Google, Daimler und anderen auf diesem Gebiet tätigen Firmen geleistet. Während zu Beginn des Projekts vor allem der Entwurf, die theoretische Analyse, die Implementierung und experimentelle Bewertung von Algorithmen zur Berechnung kürzester Wege, insbesondere von Beschleunigungstechniken für den Algorithmus von Dijkstra im Mittelpunkt standen, hat sich der Fokus während der Projektlaufzeit um zeitabhängige und dynamische Aspekte, die schnelle Anpassbarkeit auf neue Verkehrssituationen, und die Berücksichtigung von Nebenbedingungen und von mehreren Optimierungskriterien erweitert. Die Bedeutung von Routenplanungsalgorithmen für wichtige Szenarien im Mobilitätsbereich ist ungebrochen. Für Echtzeitroutenplanung, Elektromobilität, Verkehrsplanung und -kontrolle, Verkehrssimulation und für die Mobilität im Zeitalter autonomer Fahrzeuge müssen im Extremfall wiederholt viele Millionen, ggf. zeitabhängige Punkt-zu-Punkt-Routenplanungen durchgeführt werden. Das Potential unserer Algorithmen ist für diese Aufgabenstellungen bei weitem noch nicht ausgeschöpft.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2024 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung