Optimizing existing railway timetables by means of stochastic programming

Abstract

We present some models to find the best allocation of a limited amount of so-called runningtime supplements (extra minutes added to a timetable to reduce delays) on a railway line. Bythe best allocation, we mean the solution under which the sum of expected delays is minimal.Instead of trying to invent a completely new timetable, our aim is to finely adjust an alreadyexisting and well-functioning one. We model this inherently stochastic optimization problemby using two-stage recourse models from stochastic programming, following Vromans [9]. Wepresent an improved formulation, allowing for an efficient solution using a standard algorithmfor recourse models. We include a case study that we managed to solve about 180 times fasterthan it was solved in [9]. By comparing our solution with other, seemingly intuitive solutions,we show that finding the best allocation is not obvious, and implementing it in practicepromises a significant improvement in the punctuality of trains. A technique to estimate themodel parameters from empirical data and an approximating deterministic problem are alsopresented, along with some practical ideas that are meant to enhance the applicability of ourmodels.