Algorithmen für Routenplanung
im Sommersemester 2015
Allgemeines
- Vorlesung: montags 14:00–15:30 Uhr, mittwochs 11:30–13:00 Uhr.
- Raum: Raum 301, Informatik-Hauptgebäude (Geb. 50.34)
- Studiengang: Master/Diplom Informatik/Informationswirtschaft. Weitere nach Rücksprache.
- Vertiefungsfächer: Theoretische Grundlagen, Algorithmentechnik
- Module: Algorithmen für Routenplanung [IN4INALGRP], Algorithm Engineering für Routenplanung [IN4INAERP], Algorithm Engineering und Anwendungen [IN4INAEA]
- Credits: 5 ECTS (3 SWS)
Prüfungstermine
Die Prüfungstermine in diesem Semester sind:
- 31. Juli
- 24. September
- 5. Oktober
Anmeldung: Die Anmeldung erfolgt per e-Mail an Lilian Beckert nach dem „first come, first served“-Prinzip.
Wichtig: Die Anmeldung muss bis spätestens 3 Wochen vor dem Prüfungstermin erfolgen.
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.
Termine und Material
Termine sind teilweise vorläufig.
| # | Datum | Dozent | Inhalt / Kommentar | Folien |
|---|---|---|---|---|
| 1 | Mo, 13.04. | Andreas | Einführung, Grundlagen, Modelle, Datenstrukturen, Dijkstras Algorithmus, Bidirektionale Suche | Einführung |
| – | Mi, 15.04. | – | keine Vorlesung | – |
| 2 | Mo, 20.04. | Andreas | Arc-Flags, SHARC | ArcFlags/SHARC |
| – | Mi, 22.04. | – | keine Vorlesung | – |
| 3 | Mo, 27.04. | Moritz | A*, Landmarks, ALT, CALT | ALT |
| – | Mi, 29.04. | – | keine Vorlesung | – |
| 4 | Mo, 04.05. | Moritz | Reach; Customizable Route Planning (Multi-Level Dijkstra) | Reach/CRP |
| 5 | Mi, 06.05. | Ben | Contraction Hierarchies (CH), Customizable Contraction Hierarchies (CCH) | CH & CCH |
| 6 | Mo, 11.05. | Ben | Hub labeling (HL); Transit Node Routing (TNR) | HL & TNR |
| 7 | Mi, 13.05. | Ben | Fortsetzung der letzten Vorlesung | |
| 8 | Mo, 18.05. | Ben | HLDB Grundlagen & PHAST | HLDB/PHAST |
| 9 | Mi, 20.05. | Moritz K. | Alternativrouten | Alternativrouten |
| – | Mo, 25.05. | – | keine Vorlesung (Pfingsten) | – |
| 10 | Mi, 27.05. | Julian | Erweiterte Szenarien (one2many, many2many, POIs, best via queries, multi-criteria) | Multicrit & Many/POI & Turns |
| 11 | Mo, 01.06. | Julian | Dynamische Szenarien; Zeitabhängige Routenplanung I | Stau & Zeitabh. (aktualisiert am 01.06. 15:30 |
| – | Mi, 03.06. | – | keine Vorlesung | – |
| 12 | Mo, 08.06. | Julian | Zeitabhängige Routenplanung II | Zeitabh. Vorberechnung |
| – | Mi, 10.06. | – | keine Vorlesung | – |
| 13 | Mo, 15.06. | Tobias | Elektromobilität | EV-Routing |
| – | Mi, 17.06. | – | keine Vorlesung | – |
| 14 | Mo, 22.06. | Tobias | Fahrplanauskunft, Modelle, Anfrageszenarien, Graph-Algorithmen | Fahrpläne |
| 15 | Mi, 24.06. | Tobias | Fahrplanauskunft: RAPTOR | RAPTOR |
| – | Fr, 26.06., 15:00 | Christian Sommer | Gastvortrag "On Balanced Separators in Road Networks" (Input für CCH/CRP) | Details |
| 16 | Mo, 29.06. | Ben | Fahrplanauskunft: Connection-Scan | CSA |
| – | Mi, 01.07. | – | keine Vorlesung | – |
| – | Mo, 06.07. | – | keine Vorlesung | – |
| 17 | Mi, 08.07. | Julian | Multimodal, LCSPP, ANR, UCCH, MMMC | Multimodal |
| 18 | Mo, 13.07. | Moritz | Highway Dimension, Shortest Path Cover und Laufzeitgarantien | HD/SPC |
| – | Mi, 15.07. | – | keine Vorlesung | – |
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 ] |
| [BDGMPSW14] | Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato Werneck: Route Planning in Transportation Networks. Preprint. [ web ] |
| Grundlagen | |
| [CLRS01] | Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms |
| [MS08] | Mehlhorn, Sanders: Algorithms and Data Structures |
| Arc-Flags, SHARC | |
| [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. |
| [BD09] | Reinhard Bauer and Daniel Delling: SHARC: Fast and Robust Unidirectional Routing In: ACM Journal of Experimental Algorithmics, 2009 [ pdf ] |
| [BBRW13] | Reinhard Bauer, Moritz Baum, Ignaz Rutter, and Dorothea Wagner: On the Complexity of Partitioning Graphs for Arc-Flags In: Journal of Graph Algorithms and Applications, 2013 [ html ] |
| A*, ALT, CALT, 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. some link |
| [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 ] |
| [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 ] |
| 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 ] |
| Multi-Level Overlays | |
| [SWZ02] | Frank Schulz, Dorothea Wagner, Christos Zaroliagis: Using Multi-Level Graphs for Timetable Information in Railway Systems In: Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02), 2002, pages 43-59. [ pdf ] |
| [SS07] | Dominik Schultes, Peter Sanders: Dynamic Highway-Node Routing In: Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07), 2007, pages 66-79. [ pdf ] |
| [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), 2011, pages 376-387. [ pdf ] |