Traffic Optimization: Public Transportation Networks

Verkehrsoptimierung: Öffentliche Verkehrsnetze

Course Format

• Lectures will be uploaded regularly here (Lessons section), as PDF presentation + MP3 audio.
• Tutorials will be held interactively every Thursday 12-14 c.t. The first meeting is on April 23, 2020. The tutorials are also a good opportunity to ask questions concerning the lectures and problem sets. We expect regular participation in the interactive tutorial, please contact us if this is not possible for you.
• Problem Sets will be distributed every week and are supposed to be solved at home. You don't have to do this alone, we encourage you to communicate with other students, e.g., by using the forum on this site. The problem sets can be submitted in groups of two people (join at Site Info). Submit your solution as a scan or better as a LaTeX PDF via the Whiteboard Assignments section. Summed over all problem sets, reaching 50% of the total points is required for active participation.
• Exams will be oral via WebEx on July 29. Please sign up for an appointment by sending an e-mail to Niels Lindner <lindner@zib.de>, and specify the requirements of the exam (length, graded or not). This will typically be 15 minutes and ungraded (Ergänzungsmodul, MSc Mathematics, 2018 regulations).  It is also possible to take the exam in September. The last problem set is #11, the final lesson is #22, and the last tutorial session is on July 16.
• Whiteboard: We ask students to sign up for this site. This enables better communication and access to course material. TU/HU students can get access to the Whiteboard system and specifically this site as described here.

Contact

English Description

Mathematical methods play a key role in numerous problems in traffic optimization. For planning and operating public transportation networks, often discrete optimization techniques are employed.

The lecture deals with the mathematical modeling and algorithmic investigation of the following applications:
* Shortest routes in public transportation networks
* Network and infrastructure planning
* Line planning
* Timetabling
* Railway track allocation

This includes the following mathematical problems and techniques:
* Shortest paths in graphs, time-dependent and resource-constrained
* Multi-commodity network flows
* Cycle bases in graphs
* Mixed integer linear programming, cutting planes and column generation
* Steiner trees
* Facility Location
* Periodic Event Scheduling

Prerequisites: Basics of graph theory, e.g., Discrete Mathematics I. A background in optimization (e.g., Optimization I) is desirable, but not obligatory.

Literature: will be announced in the lecture

As a complement, you may optionally visit the lecture Integer Programming or the seminar on Optimization in Public Transport.

Deutsche Beschreibung

Mathematische Verfahren spielen eine Schlüsselrolle in zahlreichen Problemen in der Verkehrsoptimierung. Bei der Planung und Angebotsgestaltung im öffentlichen Verkehr kommen häufig Techniken aus der diskreten Optimierung zum Einsatz.

Die Vorlesung beschäftigt sich mit der mathematischen Modellierung und der algorithmischen Betrachtung folgender Anwendungsprobleme:
* Kürzeste Routen in öffentlichen Verkehrsnetzen
* Netz- und Infrastrukturplanung
* Linienplanung
* Fahrplanoptimierung
* Trassenplanung im Eisenbahnverkehr

Dabei werden folgende mathematische Probleme und Techniken beleuchtet:
* kürzeste Wege in Graphen mit Zeitabhängigkeit und beschränkten Ressourcen
* Mehrgüterflüsse in Netzwerken
* Kreisbasen in Graphen
* gemischt-ganzzahlige lineare Programmierung, Schnittebenen und Spaltenerzeugung
* Steinerbäume
* Facility Location
* Periodic Event Scheduling

Voraussetzungen: Grundlagen der Graphentheorie, etwa im Umfang von Diskrete Mathematik I. Kenntnisse in diskreter Optimierung (z. B. Optimierung I) sind wünschenswert, werden aber nicht vorausgesetzt.

Literatur: wird in der Vorlesung bekannt gegeben

Ergänzend zu dieser Vorlesung empfiehlt sich fakultativ auch der Besuch von Optimierung II oder des Seminars Optimierung im öffentlichen Verkehr.