Veranstaltung

Weiterführende Literatur

Mehlhorn/Sanders: Algorithms and Data Structures, The Basic Toolbox. Springer, 2008

Dieses Modul gibt einen Überblick über aktuelle Algorithmen zur effizienten Routenplanung und vertieft einige von den Algorithmen.

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.

Lernziele:
Die Teilnehmer beherrschen die Methodik des Algorithm Engineering und insbesondere ihre Anwendung im Bereich Routenplanung. Sie kennen algorithmische Problemstellungen, die sich in verschiedenen praktischen Anwendungen der Routenplanung in Transportnetzwerken ergeben. Sie sind in der Lage, diese Probleme zu identifizieren und verstehen es, die auftretenden Fragestellungen auf ihren algorithmischen Kern zu reduzieren und anschließend effizient zu lösen. Sie sind in der Lage, dabei Wissen aus den Bereichen der Graphentheorie und der Algorithmik praktisch umzusetzen. Zudem kennen die Teilnehmer verschiedene Techniken, die in der Praxis genutzt werden, um effiziente Verfahren zur Routenplanung zu implementieren. Sie kennen Verfahren zur Routenberechnung in Straßennetzen, öffentlichen Verkehrsnetzwerken sowie multimodalen Netzwerken. Studierende sind in der Lage, auch für komplexere Szenarien, wie etwa der zeitabhängigen Routenplanung, in der Praxis effizient umsetzbare Verfahren zu identifizieren und analysieren. Sie können theoretische und experimentelle Ergebnisse interpretieren und untereinander vergleichen.

Studierende sind außerdem in der Lage, neue Problemstellungen im Bereich der Routenplanung mit Methoden des Algorithm Engineering zu analysieren und Algorithmen unter Berücksichtigung moderner Rechnerarchitektur zu entwerfen, sowie aussagekräftige experimentelle Evaluationen zu planen und auszuwerten. Auf der Ebene der Modellierung sind sie in der Lage, verschiedene Modellierungsansätze zu entwickeln und deren Interpretationen zu beurteilen und zu vergleichen. Die Teilnehmer können zudem die vorgestellten Methoden und Techniken autonom auf verwandte Fragestellungen anwenden.

Empfehlungen:
Kenntnisse zu Grundlagen der Graphentheorie und Algorithmentechnik sind hilfreich.

Arbeitsaufwand: Vorlesung mit 3 SWS, 5 LP
5 LP entspricht ca. 150 Arbeitsstunden, davon
ca. 45 Std. Vorlesungsbesuch,
ca. 60 Std. Nachbereitung und Bearbeitung der Übungsaufgaben,
ca. 45 Std. Prüfungsvorbereitung.

Die Erfolgskontrolle wird in der Modulbeschreibung erläutert.