Institut für Theoretische Informatik, Algorithmik

Algorithmen für Routenplanung

im Sommersemester 2010

Allgemeines

Inhalt

Optimale Route in einem Straßennetzwerk mit Suchraum einer Beschleunigungstechnik.

Optimale Routen in Verkehrsnetzen zu bestimmen ist ein alltägliches Problem. Wurden früher Reiserouten mit Hilfe von Karten am Küchentisch geplant, ist heute die computergestützte Routenplanung in weiten Teilen der Bevölkerung etabliert: Die beste Eisenbahnverbindung ermittelt man im Internet, für Routenplanung in Straßennetzen benutzt man häufig mobile Endgeräte.

Ein Ansatz, um die besten Verbindungen in solchen Netzen computergestützt zu finden, stammt aus der Graphentheorie. Man modelliert das Netzwerk als Graphen und berechnet darin einen kürzesten Weg, eine mögliche Route. Legt man Reisezeiten als Metrik zu Grunde, ist die so berechnete Route die beweisbar schnellste Verbindung. Dijkstra's Algorithmus aus dem Jahre 1959 löst dieses Problem zwar beweisbar optimal, allerdings sind Verkehrsnetze so groß (das Straßennetzwerk von West- und Mittel-Europa besteht aus ca. 45 Millionen Abschnitten), dass der klassische Ansatz von Dijsktra zu lange für eine Anfrage braucht. Aus diesem Grund ist die Entwicklung von Beschleunigungstechniken für Dijkstra's Algorithmus Gegenstand aktueller Forschung. Dabei handelt es sich um zweistufige Verfahren, die in einem Vorverarbeitungsschritt das Netzwerk mit Zusatzinformationen anreichern, um anschließend die Berechnung von kürzesten Wegen zu beschleunigen.

Diese Vorlesung gibt einen Überblick über aktuelle Algorithmen zur effizienten Routenplanung und vertieft einige von diesen. In den Übungen sollen Algorithmen aus der Vorlesung implementiert werden.

Termine und Material

Folgende Tabelle gibt eine Übersicht über die voraussichtlichen Termine, an denen die Vorlesung stattfinden wird. Die nächste Veranstaltung ist fett hervorgehoben.

Woche Tag Datum Inhalt / Kommentar Folien
1 Montag 12. April Einführung, Grundlagen, Modelle, Datenstrukturen, Dijkstra's Algorithmus Folien
2 fällt aus
3 Montag 26. April Stoppkriterium, Bidirektionale Suche, A*, ALT Folien
Freitag 30. April Bidirektionaler ALT, Geometrische Container, Arc-Flags Folien
4 Montag 3. Mai Multi-Level Arc-Flags, Bidirektionale Arc-Flags, A*-Reach Folien
5 Montag 10. Mai RE, REAL, Contraction Hierarchies Folien
6 Montag 17. Mai Many-to-Many Routing, Alternativrouten Folien
7 Freitag 28. Mai Transit-Node Routing Folien
8 Montag 31. Mai Kombinationen: CALT, SHARC, CHASE, TNR+AF Folien
9 Montag 7. Juni Highway-Dimension und theoretische Analyse von RE und CH Folien
10 Montag 14. Juni Theoretische Analyse von RE und CH (forts.),
Einführung zeitabhängige Routenplanung
Folien
11 Freitag 25. Juni Theoretische Modellierung, Vorberechnungskomplexität, Straßengraphgeneratoren Folien
12 Montag 28. Juni Zeitabhängige Routenplanung und Profil-Suchen Folien
13 Montag 5. Juli Zeitabhängige Beschleunigungstechniken: Ingredients, ALT, Core-ALT, SHARC, CH Folien
Freitag 9. Juli Approximative CHs, Fahrplanauskunft, Parallel Self-Pruning Algorithmus Folien
14 fällt aus

Übungsmaterial

Hier gibt es Übungsblätter für die Theorieaufgaben sowie für die Implementierungen.

Ausgabe Abgabe Theorieblatt Lösung
12. April Aufwärm-Übungsblatt 1 Lösungsvorschläge
26. April Übungsblatt 2 Lösungsvorschläge
03. Mai Übungsblatt 3 Lösungsvorschläge
31. Mai Übungsblatt 4

Vergangene Veranstaltungen

Hinweis: Die Inhalte vergangener Vorlesungen können von der Aktuellen abweichen.

Literatur

Achtung: Einige Aufsätze sind passwortgeschützt. Benutzername und Passwort gibt es zu gegebener Zeit in der Vorlesung.

Übersicht über das Themengebiet
[DSSW09] Daniel Delling, Peter Sanders, Dominik Schultes, Dorothea Wagner:
Engineering Route Planning Algorithms.
In: Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science. Springer, 2009. [ pdf ]
Grundlagen
[CLRS01] Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms
[MS08] Mehlhorn, Sanders: Algorithms and Data Structures
A*, ALT, bidirektionale Suche
[GH05] Andrew V. Goldberg and Chris Harrelson:
Computing the Shortest Path: A Search Meets Graph Theory
In: Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA'05), 2005 pages 156–165. [ pdf ]
[GW05] Andrew V. Goldberg and Renato F. Werneck:
Computing Point-to-Point Shortest Paths from External Memory.
In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05), 2005 pages 26–40. [ pdf ]
[DW07] Daniel Delling and Dorothea Wagner:
Landmark-Based Routing in Dynamic Graphs
In: Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07), 2007 pages 52–65. [ pdf ]
Geometrische Container, Arc-Flags
[WWZ05] Dorothea Wagner and Thomas Willhalm and Christos Zaroliagis:
Geometric Containers for Efficient Shortest-Path Computation
In: ACM Journal of Experimental Algorithmics, 2005 article 1.3. [ pdf ]
[HKMS09] Moritz Hilger and Ekkehard Köhler and Rolf H. Möhring and Heiko Schilling:
Fast Point-to-Point Shortest Path Computations with Arc-Flags
In: Shortest Paths: Ninth DIMACS Implementation Challenge, 2009. [ pdf ]
[BDD09] Emanuele Berretini, Gianlorenzo D'Angelo, and Daniel Delling:
Arc-Flags in Dynamic Graphs
Unpublished, 2009. [ pdf ]
Reach
[Gut04] Ronald J. Gutman:
Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks
In: Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX'04), 2004 pages 100–111. [ pdf ]
[GKW09] Andrew V. Goldberg and Haim Kaplan and Renato F. Werneck:
Reach for A*: Shortest Path Algorithms with Preprocessing
In: Shortest Paths: Ninth DIMACS Implementation Challenge, 2009. [ pdf ]
Contraction Hiearchies, Many-to-Many Routing, Transit-Node Routing
[Sch08] Dominik Schultes:
Route Planning in Road Networks
Ph.D. Thesis, Universität Karlsruhe (TH), 2009. [ pdf ]
[DGSS08] Daniel Delling, Robert Geisberger, Peter Sanders, Dominik Schultes:
Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks.
In: Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 319-333. Springer, June 2008. [ pdf ]
[SS09] Peter Sanders, Dominik Schultes:
Robust, Almost Constant Time Shortest-Path Queries in Road Networks.
In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, 2009. [ pdf ]
Alternativrouten in Straßennetzen
[ADGW10] Ittai Abraham, Daniel Delling, Andrew Goldberg, and Renato Werneck:
Alternative Routes in Road Networks.
In: Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), volume 6049 of Lecture Notes in Computer Science, pages 23-34. Springer, May 2010. [ pdf ]
Kombinationen
[BD09] Reinhard Bauer and Daniel Delling:
SHARC: Fast and Robust Unidirectional Routing
In: ACM Journal of Experimental Algorithmics, 2009 [ pdf ]
[BDS+09] Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner:
Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm
In: ACM Journal of Experimental Algorithmics, 2010. [ pdf ]
Theorie zu Beschleunigungstechniken
[AFGW10] Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck:
Highway Dimension, Shortest Paths, and Provably Efficient Algorithms
In: Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA10), 2010 [ pdf ]
[BCKKW10] Reinhard Bauer, Tobias Columbus, Bastian Katz, Marcus Krug, and Dorothea Wagner:
Preprocessing Speed-Up Techniques is Hard
Technical Report 2010-04, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2010. [ pdf ]
[BKMW10] Reinhard Bauer, Marcus Krug, Sascha Meinert, and Dorothea Wagner:
Synthetic Road Networks.
In: Proceedings of the 6th International Conference on Algorithmic Aspects in Information and Management (AAIM'10), 2010.
Zeitabhängige Routenplanung
[Del09] Daniel Delling:
Enginering and Augmenting Route Planning Algorithms
Ph.D. Thesis, Universität Karlsruhe (TH), 2009. [ pdf ]
[BDSV09] Gernot Veit Batz, Daniel Delling, Peter Sanders, Christian Vetter:
Time-Dependent Contraction Hierarchies
In: Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09), April 2009. [ pdf ]
[BDGW10] Edith Brunel, Daniel Delling, Andreas Gemsa, Dorothea Wagner:
Space-Efficient SHARC-Routing
In: Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), May 2010. [ pdf ]
[BGNS10] Gernot Veit Batz, Robert Geisberger, Sabine Neubauer, Peter Sanders:
Time-Dependent Contraction Hierarchies and Approximation
In: Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), May 2010. [ pdf ]
Fahrplanauskunft
[PSWZ07] Evangelia Pyrga, Frank Schulz, Dorothea Wagner, Christos Zaroliagis:
Efficient Models for Timetable Information in Public Transportation Systems
In: ACM Journal of Experimental Algorithmics, 2007 [ pdf ]
[DKP10] Daniel Delling, Bastian Katz, Thomas Pajor:
Parallel Computation of Best Connections in Public Transportation Networks
In: 24th International Parallel and Distributed Processing Symposium (IPDPS'10). IEEE Computer Society, 2010 [ pdf ]