Institut für Theoretische Informatik, Algorithmik

Algorithmen für Routenplanung

im Sommersemester 2013

Allgemeines

  • Vorlesung: Montags 14:00–15:30 Uhr, Mittwochs 11:30–13:00 Uhr.
  • Erstmalig: Montag 15. April, 14: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)

Neuigkeiten

  • Mittwoch, 10. Juli: Die Prüfungstermine für die Vorlesung Routenplanung finden an folgenden Tagen statt: Freitag, 16. August 2013 zwischen 8:40 und 12:20 Uhr, und Dienstag, 8. Oktober 2013 zwischen 13 und 17 Uhr. Anmeldung über das Sekretariat.
  • Freitag, 5. April: Vorläufige Vorlesungstermine aktualisiert.
  • Dienstag, 2. April: Vorlesungsseite angelegt.

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.

Vorläufige Termine und Material

# Datum Dozent Inhalt / Kommentar Folien
1 Mo, 15.04. Thomas Einführung, Grundlagen, Modelle, Datenstrukturen Folien
Mi, 17.04. keine Vorlesung
2 Mo, 22.04. Thomas Dijkstra's Algorithmus, Bidirektionale Suche Folien
3 Mi, 24.04. Thomas Potentiale, A*, ALT Folien
4 Mo, 29.04. Thomas Bidirektionaler ALT, Arc-Flags Folien
Mi, 01.05. Feiertag (1. Mai)
5 Mo, 06.05. Julian Arc-Flags, PUNCH, Overlays Folien
6 Mi, 08.05. Julian Reach, Multi-Level Overlays, Contraction Hierarchies Folien
7 Mo, 13.05. Julian Contraction Hierarchies, Hub Labels Folien
Mi, 15.05. keine Vorlesung
Mo, 20.05. Feiertag (Pfingstmontag)
8 Mi, 22.05. Julian Transit Node Routing Folien
9 Mo, 27.05. Julian Kombinationen, PHAST, GPHAST Folien
10 Mi, 29.05. Julian GPHAST, Many-to-many, POI, HLDB Folien
Mo, 03.06. keine Vorlesung
Mi, 05.06. keine Vorlesung
11 Mo, 10.06. Julian Alternativ-Routen Folien
Mi, 12.06. keine Vorlesung
12 Mo, 17.06. Julian Dynamik, Zeitabhängige Routenplanung (basics) Folien
13 Mi, 19.06. Julian Zeitabhängige Routenplanung II Folien
14 Mo, 24.06. Thomas Einführung in Fahrplanauskunft in öffentlichen Verkehrsnetzen Folien
15 Mi, 26.06. Thomas Fahrplanauskunft: Parallele Profilsuchen (PSPCS) Folien
16 Mo, 01.07. Thomas Multikriterielle Fahrplanauskunft: MLC, LD, RAPTOR Folien
Mi, 03.07. keine Vorlesung
17 Mo, 08.07. Julian Multimodale Routenplanung Folien
18 Mi, 10.07. Thomas Multikriterielle multimodale Routenplanung Folien
19 Mo, 15.07. Thomas Highway Dimension, Shortest Path Cover und Laufzeitgarantien Folien
Mi, 17.07. keine Vorlesung

Vergangene Veranstaltungen

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.
[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 ]
Arc-Flags
[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.
Graph Partitionierung (METIS, PUNCH, KaFFPaE)
[KK99] George Karypis and Gautam Kumar:
A Fast and Highly Quality Multilevel Scheme for Partitioning Irregular Graphs
In: SIAM Journal on Scientific Computing, 1999, pages 359–392. [ pdf ]
[DGRW11] Daniel Delling and Andrew V. Goldberg and Ilya Razenshteyn and Renato F. Werneck:
Graph Partitioning with Natural Cuts
In: 25th International Parallel and Distributed Processing Symposium (IPDPS'11), 2011, pages 1135–1146. [ link ]
[SS12] Peter Sanders and Christian Schulz:
Distributed Evolutionary Graph Partitioning
In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12), 2012, pages 16–29. [ 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 ]
Contraction Hiearchies, HubLabels, HLDB
[GSSV12] Robert Geisberger, Peter Sanders, Dominik Schultes, Christian Vetter:
Exact Routing in Large Road Networks Using Contraction Hierarchies
In: Transportation Science, 2012. [ link ]
[ADGW11] Ittai Abaraham, Daniel Delling, Andrew V. Goldberg, 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, pages 230-241. [ link ]
[ADGW12] Ittai Abaraham, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck:
Hierarchical Hub Labelings for Shortest Paths
MSR-TR-2012-46, 2012. [ link ]
[ADFGW12] Ittai Abaraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, Renato F. Werneck:
HLDB: Location-Based Services in Databases
MSR-TR-2012-59, 2012. [ link ]
Transit Node Routing
[SS09] Peter Sanders and Dominik Schultes:
Robust, Almost Constant Time Shortest-Path Queries in Road Networks
In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, 2009. [ pdf ]
[ALS13] Julian Arz, Dennis Luxen and Peter Sanders:
Transit Node Routing Reconsidered
In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), 2013. [ Springer, arxiv ]
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 ]
Batched Shortest Paths (One-to-all, one-to-many, POI)
[DGNW11] Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyck, Renato F. Werneck:
PHAST: Hardware-Accelerated Shortest Path Trees
In: Journal of Parallel and Distributed Computing, 2012. [ link ]
[KSSSW07] Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, Dorothea Wagner:
Computing Many-to-Many Shortest Paths Using Highway Hierarchies
In: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07), pages 36-45, 2007. [ pdf ]
[DGW11] Daniel Delling, Andrew V. Goldberg, Renato F. Werneck:
Faster Batched Shortest Paths in Road Networks
In: Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11), pages 52-63, 2011. [ pdf ]
[ADFGW12] Ittai Abaraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, Renato F. Werneck:
HLDB: Location-Based Services in Databases
MSR-TR-2012-59, 2012. [ link ]
Alternativrouten
[ADGW10] Ittai Abaraham, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck:
Alternative Routes in Road Networks
In: Proceedings of the 9th International Symposium on Experimental Algorithms (SEA '10), 2010. [ pdf ]
[LS12] Dennis Luxen, Dennis Schieferdecker:
Candidate Sets for Alternative Routes in Road Networks
In: Proceedings of the 11th International Symposium on Experimental Algorithms (SEA '12), 2012. [ pdf ]
[BDGS11] Roland Bader, Jonathan Dees, Robert Geisberger, Peter Sanders:
Alternative Route Graphs in Road Networks
In: Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in Computer Systems (TAPAS'11), 2011. [ pdf ]
Abbiegekosten
[GS11] Robert Geisberger, Christian Vetter:
Efficient Routing in Road Networks with Turn Costs.
In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), 2011, pages 100-111. [ 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 ]
Zeitabhängige Routenplanung
[Del09] Daniel Delling:
Engineering 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 ]
[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. [ link ]
Fahrplanauskunft
[PSWZ08] Evangelia Pyrga, Frank Schulz, Dorothea Wagner, Christos Zaroliagis:
Efficient Models for Timetable Information in Public Transportation Systems
In: ACM Journal of Experimental Algorithmics, 2008 [ pdf ]
[DPW09] Daniel Delling, Thomas Pajor, Dorothea Wagner:
Engineering Time-Expanded Graphs for Faster Timetable Information
In: Robust and Online Large-Scale Optimization, 2009 [ pdf ]
[BDW11] Reinhard Bauer, Daniel Delling, Dorothea Wagner:
Experimental Study on Speed-Up Techniques for Timetable Information Systems
In: Networks, 2011 [ pdf ]
[Gei10] Robert Geisberger:
Contraction of Timetable Networks with Realistic Transfers
In: Proceedings of the 9th International Symposium on Experimental Algorithms (SEA’10), 2010 [ 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), 2010 [ pdf ]
[DMS08] Yann Disser, Matthias Müller-Hannemann, Mathias Schnee:
Multi-Criteria Shortest Paths in Time-Dependent Train Networks
In: Proceedings of the 7th Workshop on Experimental Algorithms (WEA’08), 2008 [ pdf ]
[DPW12] Daniel Delling, Thomas Pajor, Renato Werneck:
Round-Based Public Transit Routing
In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12), 2012 [ pdf ]
Multimodale Routenplanung
[DPW09] Daniel Delling, Thomas Pajor, Dorothea Wagner:
Accelerating Multi-Modal Route Planning by Access-Nodes.
In: Proceedings of the 17th Annual European Symposium on Algorithms (ESA'09). [ pdf ]
[DPW12] Julian Dibbelt, Thomas Pajor, Dorothea Wagner:
User-Constrained Multi-Modal Route Planning
In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12). [ pdf ]
[DDP+13] Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, Renato F. Werneck:
Computing Multimodal Journeys in Practice
In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13). [ pdf ]
Highway-Dimension
[AFGW10] Ittai Abraham, Amos Fiat, Andrew V. Goldberg, Renato F. Werneck:
Highway Dimension, Shortest Paths, and Provably Efficient Algorithms
In: Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA10), 2010 [ download ]