Modeling and solving the train timetabling problem

The train timetabling problem alms at determining a periodic timetable for a set of trains that does not violate track capacities and satisfies some operational constraints In particular, we concentrate on the problem of a single one-way track linking two major stations with a number of intermediate stations in between Each train connects two given stations along the track (possibly different from the two major stations) and may have to stop for a minimum time in some of the intermediate stations Trains can overtake each other only in correspondence of an intermediate station, and a minimum time interval between two consecutive departures and arrivals of trains in each station is specified In this paper we propose a graph theoretic formulation for the problem using a directed multigraph in which nodes correspond to departures/arrivals at a certain station at a given time instant This formulation is used to derive an integer linear programming model that is relaxed in a Lagrangian way A novel feature of our model is that the variables in the relaxed constraints are associated only with nodes (as opposed to arcs) of the aforementioned graph This allows a considerable speed-up in the solution of the relaxation The relaxation .is embedded within a heuristic algorithm which makes extensive use of the dual information associated with the Lagrangian multipliers We report extensive computational results on real world instances provided from Ferrovie dello Stato SpA, the Italian railway company, and from Ansaldo Segnalamento Ferroviano SpA.