Robustness in train timetabling

We propose a Lagrangian-based heuristic approach to obtain robust solutions to the Train Timetabling Problem (TTP) on a corridor (i.e. a single one-way line connecting two major stations). Roughly speaking, we define a solution to be robust if it allows to avoid delay propagation as much as possible. In particular, in the planning phase that we are considering the aim is to build timetables characterized by buffer times that can be used to absorb possible delays occurring at an operational level. In the TTP, we are given a set of stations S along the corridor, a set of trains T, and for each train an ideal timetable (i.e. the timetable suggested by the Train Operator). In the nominal TTP the aim is to change the ideal timetables for the trains as little as possible, while satisfying the track capacity constraints consisting of: - departure constraints (imposing a minimum headway between two consecutive departures from a station); - arrival constraints (imposing a minimum headway between two consecutive arrivals at a station); - overtaking constraints (avoiding overtaking between consecutive stations, since we are considering a single one-way line).