Nominal and robust train timetabling problems

In this paper we survey the main studies dealing with the train timetabling problem in its nominal and robust versions. Roughly speaking, the nominal version of the problem amounts of determining good timetables for a set of trains (on a railway network or on a single one-way line), satisfying the so-called track capacity constraints, with the aim of optimizing an objective function that can have different meanings according to the requests of the railway company (e.g. one can be asked to schedule the trains according to the timetables preferred by the train operators or to maximize the passenger satisfaction). Two are the main variants of the nominal problem: one is to consider a cyclic (or periodic) schedule of the trains that is repeated every given time period (for example every hour), and the other one is to consider a more congested network where only a non-cyclic schedule can be performed. In the recent years, many works have been dedicated to the robust version of the problem. In this case, the aim is to determine robust timetables for the trains, i.e. to find a schedule that avoids, in case of disruptions in the railway network, delay propagation as much as possible. We present an overview of the main works on train timetabling, underlining the differences between models and methods that have been developed to tackle the nominal and the robust versions of the problem. (C) 2011 Elsevier B.V. All rights reserved.