Institut für Theoretische Informatik, Algorithmik

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 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.

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

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 ]