Dr. Valentina Cacchiani
DEIS, Universitšt Bologna, Italien

Nominal and Robust Train Timetabling Problems

Among railway optimization problems, the most relevant ones concern the main phases that are needed in the planning and operational processes related to railway systems. In this talk, we present our research on one of these phases, namely the Train Timetabling Problem (TTP). The nominal TTP, given the requests of suggested timetables from the Train Operators who share the same infrastructure, aims at determining an optimal timetable which satisfies a set of safeness operational constraints (i.e. a minimum headway is imposed between two consecutive departures from a station and between two consecutive arrivals at a station, and overtaking is allowed only within stations or by using alternative lines). The goal is to change the suggested timetables for the trains as little as possible. We study the problem, proposing an Integer Linear Programming (ILP) formulation, based on a graph representation of the problem. We present a Lagrangian heuristic based on the ILP formulation and report computational results on real-world instances of the Italian Railways. We also consider the robust version of TTP and propose a heuristic algorithm to obtain robust solutions. In this context, we define a solution to be robust if it allows avoiding delay propagation as much as possible. Thus, in the planning phase the aim is to build timetables characterized by buffer times that can be used for absorbing possible delays occurring at an operational level. The method takes into account both a nominal objective function aimed at maximizing effciency and a secondary objective function aimed at introducing buffer times. TTP is modelled using an arc-based ILP formulation, where the track capacity constraints are relaxed in a Lagrangian way. A Lagrangian-based heuristic approach is proposed and compared with previous existing methods on real-world instances of the Italian Railways.

joint work with: Alberto Caprara and Paolo Toth