Modelling and Solving the Train Timetabling Problem

The Train Timetabling Problem (TTP) is a very complex problem, with both continuous and discrete aspects.
In the TTP, you have to choose schedules for trains, competing for the same scarce track capacities. At the same time, the rules for how close the trains may come are complex.
In a 98-paper (Brännlund et al) we introduced lagrangian relaxation for solving this problem, discretizing space and time, In the present talk we will present the approach and give improvements, some of which are under development. Some of the improvements are: parallelization of the heavy subproblem solution, disaggregate duals, and disaggregate primals.