| Modeling and Solving the (2007) | |||||||||||||||
Abstract | |||||||||||||||
| The Train Timetabling Problem aims at determining a periodic timetable for a set of trains which does not violate track capacities and satises 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 dierent 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 specied. 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 which 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 speedup 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 Ferroviario SpA. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||