Verkehrsoptimierung: Optimale Touren in Graphen / Traffic Optimization: Optimal Tours in Graphs

News

The lectures (Mon 10-12) take place in A3/SR 024, Arnimallee 3.

Tutorials (Mon 12-14) are in A6/SR 025/026, Arnimallee 6.

Exception: The lecture on November 18 takes place in A6/SR 009, Arnimallee 6.

No lecture (but a tutorial) on February 10.

Exams: The oral exams can be taken on February 11, February 17 or April 6, 2020. Make an appointment by e-mailing to Niels Lindner.

Übungsaufgaben / Problem Sets

 Problem Set 1 (due October 21)

Problem Set 2 (due October 28)

Problem Set 3 (due November 4)

Problem Set 4 (due November 11)

Problem Set 5 (due November 18)

Problem Set 6 (due November 25)

Problem Set 7 (due December 2 - update on November 26, 11:50)

Problem Set 8 (due December 9 - update on December 5, 10:30)

Problem Set 9 (due December 16)

Problem Set 10 (due January 6)

Problem Set 11 (due January 13)

Problem Set 12 (due January 20)

Problem Set 13 (due January 27)

Problem Set 14 (due February 4)

Vorlesungsfolien / Lecture Notes

Lecture 1: S-Bahn-Challenge

Lecture 1: Mathematical Optimization in Public Transport

Lecture 2: Euler tours, Chinese Postman, shortest paths, min-plus matrix multiplication algorithm

Lecture 3: T-joins, Edmonds-Johnson algorithm, Hamiltonian circuits

Lecture 4: Hamiltonian circuits (line graph, Dirac's lemma), computational complexity (encoding graphs as binary strings, languages, decision problems, P, NP, polynomial-time reductions)

Lecture 5: NP-completeness, Traveling Salesman (NP-hardness, decision vs. optimization), polynomial equivalence of TSP, ATSP, Metric (A)TSP

Lecture 6: TSP Heuristics (Nearest Neighbor, Minimum Spanning Tree, Christofides, k-opt), Inapproximability of TSP, Approximation algorithms for Metric TSP

Lecture 7: Halfspaces, polyhedra, linear programming, Farkas' lemma, LP duality, integer programming

 Lecture 8: LP & IP recall, simplex algorithm, cutting planes, TSP IP formulation, subtour elimination, branch-and-bound, branch-and-cut

Lecture 9: Dimension of the TSP polytope, Miller-Tucker-Zemlin ATSP formulation

Lecture 10: Rural Postman, GDRPP, GATSP, Noon-Bean transformation

Lecture 11: Public transportation networks, periodic timetables, S-Bahn Challenge as GATSP/GDRPP

Lecture 12: Periodic Vehicle Scheduling (modelling, cycle periodicity, periodic offsets, circulation vs. perfect matching)

Lecture 13: Single-depot aperiodic vehicle scheduling (modelling by acyclic relations, minimum value flow formulation, matching interpretation, comparison periodic vs. aperiodic)

Lecture 14: Comparison of aperiodic and periodic vehicle schedules, multi-depot vehicle scheduling, multi-commodity flow

Lecture 15: Path-based multi-commodity flow formulation for multi-depot vehicle scheduling, column generation, extensions of vehicle scheduling, capacitated vehicle routing, dial-a-ride/ride pooling

Literature

• E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys (editors): The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons.
• B. Korte, J. Vygen: Combinatorial Optimization - Theory and Applications. Springer.
• A. Schrijver: Combinatorial Optimization - Polyhedra and Efficiency, Part A. Springer.
• W. Cook: In Pursuit of the Traveling Salesman - Mathematics at the Limits of Computation. Princeton University Press.

Contact

Beschreibung

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