Algorithm Engineering für Routenplanung
Final Report Abstract
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.
Publications
- Intriguingly simple and fast transit routing. Proceedings of 12th International Symposium on Experimental Algorithms (SEA), volume 7933 of LNCS, pages 43–54. Springer, 2013
Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner
(See online at https://doi.org/10.1007/978-3-642-38527-8_6) - Minimum time-dependent travel times with contraction hierarchies. ACM Journal of Experimental Algorithmics (JEA) 18, 2013
Gernot Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter
(See online at https://doi.org/10.1145/2444016.2444020) - Transit node routing reconsidered. Proceedings of 12th International Symposium on Experimental Algorithms (SEA), volume 7933 of LNCS, pages 55–66. Springer, 2013
Julian Arz, Dennis Luxen, and Peter Sanders
(See online at https://doi.org/10.1007/978-3-642-38527-8_7) - Candidate sets for alternative routes in road networks. Journal of Experimental Algorithmics (JEA) 19, 2014
Dennis Luxen and Dennis Schieferdecker
(See online at https://doi.org/10.1145/2674395) - Parallel bi-objective shortest paths using weightbalanced B-trees with bulk updates. Proceedings of 13th Symposium on Experimental Algorithms (SEA), volume 8504 of LNCS, pages 111–122. Springer, 2014
Stephan Erb, Moritz Kobitzsch, and Peter Sanders
(See online at https://doi.org/10.1007/978-3-319-07959-2_10) - User-Constrained Multimodal Route Planning. ACM Journal of Experimental Algorithmics (JEA) 19, 2014
Julian Dibbelt, Thomas Pajor, and Dorothea Wagner
(See online at https://doi.org/10.1145/2699886) - Customizable Contraction Hierarchies. ACM Journal of Experimental Algorithmics (JEA) 21, 2016
Julian Dibbelt, Ben Strasser, and Dorothea Wagner
(See online at https://doi.org/10.1145/2886843) - Route Planning in Transportation Networks. Algorithm Engineering - Selected Results and Surveys, volume 9220 of LNCS, pages 19–80. Springer, 2016
Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck
(See online at https://doi.org/10.1007/978-3-319-49487-6_2) - Search-space size in contraction hierarchies. Theoretical Computer Science 645: 112–127, 2016
Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner
(See online at https://doi.org/10.1016/j.tcs.2016.07.003)
