Algorithmen für Routenplanung
im Sommersemester 2011
Allgemeines
- Vorlesung: Montags 14:00–15:30 Uhr (wöchentlich), Donnerstags 11:30–13:00 Uhr (zweiwöchentlich)
- Erstmalig: Donnerstag 14. April, 11:30 Uhr.
- Raum: Raum 301, Informatik-Hauptgebäude (Geb. 50.34)
Lernzielkontrolle
- Die Lernzielkontrolle ist im Begriff zu entstehen, und zwar genau hier.
Rechnerübung am Montag, den 23. Mai 2011
- Am Montag, den 23. Mai 2011 findet von 14:00-15:30 in Poolraum 305 Rechnerübung statt
- Der dort behandelte Stoff ist nicht prüfungsrelevant
- Ziele der Rechnerübung sind wie folgt:
- Verständnis für eine bestehende, sehr effiziente Implementation von Dijkstra's Algorithmus sowie den zugehörigen Datenstrukturen
- Implementation von Bidirektionaler Suche
- Bei Interesse wird eine zweite Rechnerübung angeboten, in der Reach-Based-Pruning oder Arc-Flags implementiert werden.
- Der Quellcode ist in C++, die Rechnerübung bringt aber auch ohne C++ Kentnisse Nutzen
Termine (vorläufig)
- Am 19.05. findet keine Vorlesung statt!
- Am 27.6. und 30.6. finden keine Vorlesungen statt!
| Montag | Donnerstag |
|---|---|
| - | 14.04. |
| 18.04 | 21.04 |
| - | - |
| 02.05 | 05.05 |
| 09.05 | 12.05 |
| 16.05 | – |
| 23.05 | 26.05 |
| 30.05 | – |
| 06.06 | 09.06 |
| – | 16.06 |
| 20.06 | - |
| | |
| 04.07 | 07.07 |
Inhalt
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.
Folien
Vergangene Veranstaltungen
Hinweis: Die Inhalte vergangener Vorlesungen können von der Aktuellen abweichen.
Literatur
| Ü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. |
| 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. |
| 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. [ download ] |
| [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. [ download ] |
| 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. |
| Customizable Route Planning | |
|---|---|
| [DGP11] | Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato F. Werneck: Customizable Route Planning In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 376-387. Springer, 2011. [ pdf ] |
| Kombinationen | |
|---|---|
| [BD09] | Reinhard Bauer and Daniel Delling: SHARC: Fast and Robust Unidirectional Routing In: ACM Journal of Experimental Algorithmics, 2009 [ download ] |
| [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. [ download ] |
| Zeitabhängige Routenplanung | |
|---|---|
| [Del09] | Daniel Delling: Enginering and Augmenting Route Planning Algorithms Ph.D. Thesis, Universität Karlsruhe (TH), 2009. [ pdf ] |
| [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 [ download ] |
| [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 ] |
| Theorie und Labeling Algorithmus | |
|---|---|
| [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 [ download ] |
| [ADGW11] | Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck: A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), 2011 [ download ] |