Robust Timetabling and Stacking Problems

Last week I went to the “Mini-Workshop on Integrated Timetabling” in Göttingen, though I wonder if “mini” is the appropriate name for a three-day event? We enjoyed excellent talks on various combinations of timetabling with other problems in public transport. My own presentation was on “A New Robust Local Search Method and its Application to Uncertain Timetabling“, with the abstract below:

Railway timetabling problems are challenging to solve, even if all problem parameters are known exactly. If travel times are uncertain, as is the case in practice, finding good solutions is even harder.

I introduce a new local search technique to find robust solutions under implementation errors. In this setting, not the problem parameters are considered uncertain, but the actual implementation of a solution has an error margin. I first discuss an existing general approach to this problem by Bertsimas, Nohadani and Teo. I then introduce a new approach that is able to overcome local optima, and discuss its application to the train timetabling problem. While this is still work in progress, some first experimental results are presented.

I then went on to Osnabrück and gave a seminar talk on robust selection problems.