Praktikum Algorithmentechnik (Algorithm Engineering - Routenplanung)

• Betreuung: Dr. Moritz Baum, Dr. Julian Dibbelt, Dr. Thomas Pajor, Dr. Ben Strasser, Prof. Dr. Dorothea Wagner
• Vorbesprechung: am Mittwoch, den 17.10.12 um 11:30 Uhr im Seminaraum 301 (Informatikgebäude 50.34)
• Teilnahme: Die Teilnehmerzahl ist auf 12 Personen begrenzt. Interessensbekundungen, Fragen und/oder Anmeldungen bitte per E-Mail an Julian Dibbelt. Keine weiteren Anmeldungen möglich.
• Studiengang: Master Informatik/Informationswirtschaft. Weitere nach Rücksprache.
• Module: Praktikum Algorithmentechnik [IN4INALGOP], Algorithm Engineering für Routenplanung [IN4INAERP]
• Credits: 6 ECTS (4 SWS)

• 07. November 2012: Nächstes Treffen: Mittwoch, 21.11., 11:30 in SR 301, Kurzvorträge
• 06. November 2012: Nächstes Treffen: Mittwoch, 07.11., 11:30 im Poolraum
• 24. Oktober 2012: Das zweite Übungsblatt ist online. Entgegen dessen, was wir heute in der Besprechung möglicherweise gesagt haben, braucht ihr doch keine neuen Graphen für das zweite Blatt herunterzuladen. Die Rückwärtskanten werden nun direkt beim Einlesen der Graphen erzeugt.
• 22. Oktober 2012: Nächstes Treffen: Mittwoch, 24.10., 11:30 im Poolraum
• 22. Oktober 2012: Literaturliste aktualisiert, Folien der Vorlesung Routenplanung verlinkt.
• 18. Oktober 2012: Graphen für das erste Übungsblatt sind online.
• 17. Oktober 2012: Die Vorbesprechung war sehr gut besucht, wir haben die maximale Teilnehmerzahl erreicht.
• Nähere Informationen folgen in der Vorbesprechung.

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 gängiger Ansatz das Problem zu lösen ist das Transportnetzwerk auf geeignete Weise als einen Graphen zu modellieren. Eine optimale Verbindung entspricht dann einem kürzesten Weg in diesem Graphen. Zwar löst Dijkstra's Algorithmus dieses Problem beweisbar optimal, jedoch ist aufgrund der hohen Datenmenge (Straßennetzwerke von kontinentaler Größe haben mehrere Millionen Knoten und Kanten) dieser Ansatz selbst auf moderner Server-Hardware zu langsam und daher nicht praktikabel.

Aus diesem Grund ist die Routenplanung ein sehr aktiver und vielfältiger Forschungsbereich in der experimentellen Algorithmik. Neben der grundlegenden Fragestellung nach schnelleren Methoden Routen auf Straßennetwerken zu berechnen, sind insbesondere auch Aspekte wie All-Pairs Shortest-Path, Alternativrouten, Fahrplanauskunft oder dynamische Techniken, die in Echtzeit mit Staus oder Verspätungen umgehen können, von Interesse.

Dieses Praktikum soll interessierten Studenten die Möglichkeit geben brandaktuelle Techniken aus dem Bereich Routenplanung zu implementieren und experimentell zu evaluieren. Neben der Korrektheit der implementierten Algorithmen liegt dabei ein Schwerpunkt auf der Performance (Zeit und Speicherverbrauch). Das Praktikum ist eine Ergänzung zur Vorlesung Algorithmen für Routenplanung, die jeweils im Sommersemester stattfindet. Eine kurze Einführung der wichtigen Grundlagen zu Beginn gibt aber auch Studenten ohne spezielle Vorkenntnisse die Möglichkeit zur Teilnahme.

In einem ersten Präsenztermin wird zunächst eine theoretische Fundierung des Stoffes vermittelt werden; daneben wird Gelegenheit zur praktischen Einarbeitung in die Thematik und die verwendeten Bibliotheken an Hand einiger Aufwärmaufgaben gegeben sein. Im Anschluss daran werden in Teams von zwei bis drei Personen und individueller Betreuung durch Lehrstuhlmitarbeiter eine oder mehrere größere Aufgaben bearbeitet werden. Jeweils etwa zu Semesterhalbzeit und -ende wird jede Gruppe in einer Präsentation ihre bisherige Arbeit vorstellen. Abschließend ist eine schriftliche Ausarbeitung der Ergebnisse in LaTeX zu erstellen.

Für die Teilnahme am Praktikum sind Grundkenntnisse aus den Bereichen Algorithmentechnik und Graphentheorie sowie Grundkenntnisse in C++ (oder verwandten Sprachen) empfehlenswert (fehlende Kenntnisse werden durch die Aufwärmübungen aufgearbeitet, dadurch eventuell erhöhter Zeitaufwand wird jedoch nicht in den ECTS berücksichtigt). Ein Besuch der Vorlesung Routenplanung ist nicht erforderlich.

Folgenden Themen sollen einen Vorgeschmack auf den Inhalt des Praktikums geben. Die konkrete im Team zu bearbeitende Aufgabe wird in der Vorbesprechung festgelegt:

• Berechnung guter Alternativ-Routen
• Metrik-unabhängige Routenplanung
• Sehr schnelle Punkt-zu-Punkt-Anfragen, Location-based Services
• Cache-effiziente Berechnung von kürzeste-Wege-Bäumen
• Routenplanungsalgorithmen für Fahrplan-Netzwerke

Dies ist die Zuteilung der Gruppen zu den Betreuern.

Hier findet ihr nützliche Materialien zum Praktikum

• Praktikum Algorithm Engineering - Routenplanung 2011
• Folien der Vorbesprechung
• Merkblatt Rechnerexperimente

• Einführungsblatt
• Graphen für das erste Blatt

• Zweites Blatt (Dijkstra und bidirektionale Suche)
• Die Graphen von Blatt 1 können weiterverwendet werden.

Generell lohnt sich der Blick in die Folien der Routenplanungsvorlesung

• Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Alternative Routes in Road Networks, in Proc. 9th International Symposium on Experimental Algorithms (SEA), Springer Verlag, 2010. html
• Dennis Luxen and Dennis Schieferdecker, Candidate Sets for Alternative Routes in Road Networks. In Proceedings of the 11th International Symposium on Experimental Algorithms (SEA'12). PDF
• Folien Vorlesung #12
• Folien Vorlesung #7 (Contraction Hierarchies)

• Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and 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
• Folien Vorlesung #6 (Multi-Level Overlays)

• 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), Springer Verlag, May 2011. html
• Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Hierarchical Hub Labelings for Shortest Paths, in Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12), Springer, 2012. html
• Folien Vorlesung #7 (Contraction Hierarchies, Hub Labels)
• Folien Vorlesung #11 (POIs, HLDB)

• Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck, PHAST: Hardware-Accelerated Shortest Path Trees, in 25th International Parallel and Distributed Processing Symposium (IPDPS'11), IEEE, 2011. html
• Folien Vorlesung #10
• Folien Vorlesung #7 (Contraction Hierarchies)

• Daniel Delling, Thomas Pajor, and Renato F. Werneck: Round-Based Public Transit Routing. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12), pages 130-140. SIAM, 2012. PDF
• Folien Vorlesung #18