The 2005 timetable for this network was computed by Matheon, at the Institute of Mathematics at TU Berlin. The key were state-of-the-art combinatorial optimization techniques. The public transport of Berlin is modeled as a graph with vertices at the stations, edges between them, and constraints of different types. The optimal solution for its functioning (minimizing the waiting time at stations and the number of trains required) is hidden somewhere in the set of all possible solutions respecting the constraints. But this set is much too large to be explored as a whole, even with the most powerful computers. Clever mathematical techniques produce powerful algorithms allowing to eliminate large portions of this set and, to concentrate the search in smaller subregions where the optimum lies.

The film is available in German and English, to download it please click on the «download link» button on the right.