Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Sommersemester 2009
Algorithmen für Routenplanung

Algorithmen für Routenplanung

Sommersemester 2009

Allgemeines

Neueste Meldungen

  • 4. August: Folien und Artikel zu Vorlesung 12 online.
  • 23. Juli: Folien und Artikel zu Vorlesung 11 online.
  • 22. Juli: Lösungsvorschläge zu Blatt 5 online.
  • 10. Juli: Folien und Artikel zu Vorlesung 10 online.
  • 6. Juli: Lösungsvorschläge zu Blatt 4, sowie Materialien zur 5. Übung sind online.
  • 6. Juli: Folien und Artikel zu Vorlesung 9 online.
  • 26. Juni: Folien und Artikel zu Vorlesung 8 online.
  • 22. Juni: Lösungsvorschläge zu Blatt 3, sowie Materialien zur 4. Übung online. Außerdem ist eine kurze Zusammenfassung zu Contraction Hierarchies und Transit-Node Routing unter der 4. Übung verfügbar.
  • 22. Juni: Folien und Artikel zu Vorlesung 7 online.
  • 8. Juni: Das dritte Übungsblatt (Diesmal ein kombiniertes Theorie- und Praxisblatt) und die Lösungsvorschläge zum zweiten Theorieblatt sind nun online.
  • 5. Juni: Achtung, die Vorlesung am 12.6.2009 fällt aus!
  • 5. Juni: Folien zu Vorlesung 6 online.
  • 1. Juni: Folien zu Vorlesung 5 online, Literaturliste aktualisiert.
  • 26. Mai: Wir haben uns entschlossen Lösungsvorschläge zu den Theorieaufgaben zu veröffentlichen. Die Lösung zum ersten Theorieübungsblatt ist nun online.
  • 26. Mai: Zweites Übungsblatt online. Bitte beachten Sie auch die Hinweise zur Bearbeitung der Praxisaufgaben.
  • 26. Mai: Folien zu Vorlesung 4 online.
  • 15. Mai: Folien zu Vorlesung 3 online.
  • 8. Mai: Erstes Übungsblatt (Theorie- und Praxisteil) online. Außerdem ist das Rahmenwerk mit den Graphen herunterladbar.
  • 5. Mai: Folien zu Vorlesung 2 online.
  • 24. April: Achtung: nächste Vorlesung ist am 4.5. (Montag) 15:45 SR301
  • 24. April: Folien zu Vorlesung 1 online.

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. In den Übungen sollen Algorithmen aus der Vorlesung implementiert werden.

Termine

Mo Fr Thema der Vorlesung Material
24.04. Vorlesung Grundlagen, Modelle Folien_1,MS08,CLRS01
01.05. Feiertag
04.05. Vorlesung 08.05. Übung Bidirektionale Suche, A*, ALT Folien_2,GH05,GW05
15.05. Vorlesung Geometrische Container, Arc-Flags Folien_3,WWZ05,HKMS09
22.05. Vorlesung Reach, RE, REAL Folien_4,Gut04,GKW09
25.05. Übung 29.05. Vorlesung Highway Hierarchies, Highway-Node Routing, Contraction Hierarchies Folien_5, Sch08 (Kapitel 3,4), DGSSV09
05.06. Vorlesung Many-to-Many, Transit-Node Routing Folien_6, Sch08 (Kapitel 5,6)
08.06. Übung 12.06. fällt aus
19.06. Vorlesung Kombinationen Folien_7, BD09, BDS+09
22.06. Übung 26.06. Vorlesung Dynamische Szenarien Folien_8, Sch08 (Kapitel 5), DW07, BBD09, DGSSV09
03.07. Vorlesung Basics zeitabhängige Routenplanung Folien_9, Del09 (Kapitel 3)
06.07. Übung 10.07. Vorlesung Zeitabhängige Beschleunigungstechniken Folien_10, Del09 (Kapitel 5)
17.07. Vorlesung Multi-Kriterielle Wege Folien_11, Del09 (Kapitel 6)
20.07. Übung 24.07. Vorlesung Multi-Modale Routenplanung Folien_12, DPW09

Änderungen vorbehalten!

Übungen

An dieser Stelle werden jede Woche Übungsblätter (Theorie- und Praxisaufgaben) und Folien aus der Übung veröffentlicht.

Übung vom 8. Mai 2009

Übung vom 25. Mai 2009

Hinweise zur Bearbeitung:

  • Das Arc-Flag einer Kante e zur Region r wird gelesen indem man graph.edges[e].getArcFlag(r) ausliest.
  • Arc-Flags schreiben ist analog mit setArcFlag(r) (setzen) und unsetArcFlag(r) (entfernen) möglich.
  • Achtung: Bei der Implementierung der Arc-Flags-Vorberechnung sollten Sie im Vorfeld für alle Kanten einmal graph.edges[e].unsetAllArcFlags() aufrufen um die Arc-Flags korrekt zu initialisieren.
  • Benutzen Sie zum Testen und Debuggen der Vorberechnung den kleinen Graph USA_small.bgr, da die Vorberechnung auf den großen Graphen sehr lange (mehrere Stunden) dauern kann!

Übung vom 8. Juni 2009

Übung vom 22. Juni 2009

Übung vom 6. Juli 2009

Literatur

Achtung: Einige Aufsätze sind passwort-geschützt. Die username / password Kombination gibt es per Mail bei delling [at] iti [dot] uni [dash] karlsruhe [dot] de oder pajor [at] iti [dot] uni [dash] karlsruhe [dot] de.

Ü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. to appear. [ 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 to appear. [ 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 to appear. [ pdf ]
Highway Hiearchies, Highway-Node Routing, 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 ]
[DGSSV09] Daniel Delling, Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact Routing in Large Road Networks using Contraction Hierarchies Preliminary Version, 2009. [ pdf ]
Kombinationen
[BD09] Reinhard Bauer and Daniel Delling. SHARC: Fast and Robust Unidirectional Routing In: ACM Journal of Experimental Algorithmics, 2009 to appear [ 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. Preliminary version, 2009. [ pdf ]
Zeitabhängiges Routing
[Del09] Daniel Delling. Enginering and Augmenting Route Planning Algorithmus. Ph.D. Thesis, Universität Karlsruhe (TH), 2009. [ pdf ]
Multi-Modales Routing
[DPW09] Daniel Delling, Thomas Pajor, and Dorothea Wagner. Accelerating Multi-Modal Route Planning by Access-Nodes. In: Proceedings of the 17th Annual European Symposium on Algorithms (ESA'09), volume 5757 of Lecture Notes in Computer Science, pages 587-598. Springer, September 2009. [ pdf ]