Routing Structures and Periodic Timetabling

Creating an optimal timetable and choosing optimal passenger routes are usually viewed as two separate tasks in traffic optimization: Timetables are built assuming fixed passenger routes, and public transport route planners are based upon a fixed timetable. This project aims for an efficient integration of passenger routing and timetabling. Examples show that this approach is able to produce timetables with much smaller total traveling time for all passengers.

However, there are some difficulties: First, optimizing a timetable is already hard in the case of fixed passenger routes. This project hence attacks these problems in several ways, e.g., by improving the mixed integer program formulations, separating cutting planes and transforming to SAT instances. A second bottleneck is the large amount of routing computations required in the integrated timetabling problem. To this end, we investigate various routing methods beyond Dijkstra's algorithm, in particular time-dependent approaches and exploiting routing structures. Thirdly, integrated passenger routing and timetabling results in a large-scale bilinear integer optimization problem. This can be efficiently linearized, but the computational challenge is still demanding. To this end, we develop heuristics based on modulo network simplex techniques. In the long run, the goal of this project is to lead to a better understanding of the structure of public transportation networks and the characteristics of passenger paths.

This research is carried out in the framework of MATHEON supported by Einstein Foundation Berlin.

The video shows an optimized bus timetable. Overcrowded stations are colored dark.