WiSe 19/20: Verkehrsoptimierung: Optimale Touren in Graphen
Niels Lindner
Kommentar
Das Finden optimaler Touren in einem Graphen ist Teil zahlreicher diskreter Optimierungsprobleme. Die Bandbreite dieser Probleme reicht dabei von einfach (z. B. Route Inspection) über berühmt (Traveling Salesman) zu praktisch hochrelevant (Fahrzeugumlauf- und Dienstplanung) und unterhaltsam (S-Bahn-Challenge). Obwohl einfach zu formulieren und zu verstehen sind, ist das Berechnen exakter Lösungen oft überraschend schwierig.
Wir werden diese Probleme und einige naheliegende Verallgemeinerungen im Detail besprechen, die zugrundeliegende Mathematik analysieren, (gemischt-)ganzzahlige Programme formulieren und exakte sowie heuristische Lösungsverfahren vorstellen.
Mathematische Grundlagen:
- Rekapitulation Graphentheorie (kürzeste Wege, Matchings, Spannbäume, Euler- und Hamiltonpfade)
- fortgeschrittene Graphentheorie (T-Joins, Baum-/Branchzerlegungen)
- kurze Einführung in Komplexitätstheorie (Komplexitätsklassen, Polynomialzeitreduktionen, P vs. NP, Approximationsalgorithmen)
- Modellieren von öffentlichen Verkehrsnetzen
- (gemischt-)ganzzahlige lineare Programmierung
Behandelte Optimierungsprobleme:
- Route Inspection/Chinese Postman
- Traveling Salesman (TSP)
- Vehicle Routing
- Vehicle Scheduling
- Crew Scheduling
- S-Bahn-Challenge
Am Ende des Semesters werden Studenten die folgenden Fragen (und mehr) beantworten können:
- Warum ist es im Vergleich zu einer Eulertour so viel schwerer, einen Rundweg in einem Graphen zu finden, der alle Knoten besucht?
- Was sind die Stärken und Schwächen verschiedener Ansätze für dasselbe Optimierungsproblem?
- Wie können Methoden der diskreten Optimierung den öffentlichen Verkehr verbessern?
- Wie viel Zeit ist nötig, um das gesamte Berliner S-Bahn-Netz abzufahren?
Voraussetzungen: Grundlagen der Graphentheorie, etwa im Umfang von Diskrete Mathematik I
Ergänzend zu dieser Vorlesung empfiehlt sich fakultativ auch der Besuch von Optimierung I (Ralf Borndörfer) oder des Seminars Graphzerlegungen (Niels Lindner).
16 Termine
Regelmäßige Termine der Lehrveranstaltung