Planning and operating public transport networks in an optimized way is an ubiquitous task, both from the passengers’ and operators’ perspective. Mathematical methods play a key role in numerous problems in traffic optimization. Many problems can be approached by techniques from discrete optimization.

The lecture deals with the mathematical modeling and algorithmic investigation of the following applications:

* Shortest routes in public transportation networks

* Line planning

* Timetabling

* Railway track allocation

* Vehicle scheduling

This includes the following mathematical problems and techniques:

* Modeling public transportation networks

* Shortest paths in graphs, time-dependent and resource-constrained

* Single- and multi-commodity network flows

* Cycle spaces and cycle bases in graphs

* Basic complexity theory (polynomial-time reductions, NP-completeness)

* Mixed integer linear programming, cutting planes and column generation

* Periodic Event Scheduling

Prerequisites: Basics of graph theory, e.g., Discrete Mathematics I. As a complement, you may optionally visit the lecture Discrete Mathematics II (= Optimization I) or the seminar on Optimization in Public Transport.

Literature: will be announced in the lecture

• The course language will be either English or German, depending on the audience.

• Lectures will be held weekly (2h/week), either hybrid or online, depending on the COVID situation.    

• Tutorials will be held weekly, starting from the second week of lectures. The tutorials are a good opportunity to ask questions concerning the lectures and problem sets. We expect regular participation in the 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. We encourage to communicate with other students, e.g., by using the forum on the Whiteboard site. The problem sets can be submitted in groups of two people. 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 upon appointment at the end of the semester.

• Whiteboard: We ask students to sign up for the Whiteboard site. This enables better communication and access to course material. TU/HU students are able to get access to the Whiteboard system as well.