WiSe 19/20: Traffic Optimization: Optimal Tours in Graphs
Niels Lindner
Comments
Finding optimal tours in graphs is part of many discrete optimization problems. The scope of these problems ranges from simple (e.g., Route inspection) to famous (Traveling Salesman), practically highly relevant (Vehicle and Crew Scheduling), and funny (S-Bahn Challenge). Although simple to formulate and easy to understand, computing exact solutions is often surprisingly hard.
We will describe these problems and some natural generalizations in detail, analyze the mathematics behind, develop (mixed) integer programming formulations, and present exact and heuristic solution methods.
Mathematical foundations:
- Graph theory recap (shortest paths, matchings, spanning trees, Euler tours, Hamiltonian paths)
- advanced graph theory (T-joins, tree and branch decompositions)
- short introdcution to complexity theory (complexity classes, polynomial-time reductions, P vs. NP, approximation algorithms)
- Modelling of public transport networks
- (mixed) integer linear programming
Optimization problems:
- Route Inspection/Chinese Postman
- Traveling Salesman (TSP)
- Vehicle Routing
- Vehicle Scheduling
- Crew Scheduling
- S-Bahn Challenge
Afterwards, students will be able to answer the following (and many more) questions:
- Why is it so much more difficult to find a tour visiting all vertices exactly once in a graph compared to an Euler tour?
- What are the strengths and weaknesses of different approaches to the same optimization problem?
- How can discrete optimization methods improve public transport?
- How long does it take to travel the entire Berlin S-Bahn network?
Prerequisites: Basics of graph theory, e.g., Diskrete Mathematik I
As a complement, you may optionally visit the lecture Optimierung I (Ralf Borndörfer) or the seminar on graph decompositions (Niels Lindner).
16 Class schedule
Regular appointments