This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Caprara, A. Articles by Toth, P. Search for Related Content

Modeling and Solving the Train Timetabling Problem

DEIS, University of Bologna, Italy
DEIS, University of Padova, Italy
DEIS, University of Bologna, Italy
ptoth{at}deis.unibo.it

The train timetabling problem aims 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 Ferroviario SpA.

Subject classifications: Programming algorithms: Lagrangian relaxation, heuristics; Transportation: train timetabling, railway.
History: Received August 2000; revision received May 2001; accepted May 2001.

This article has been cited by other articles:

				C. Liebchen The First Optimized Railway Timetable in Practice Transportation Science, November 1, 2008; 42(4): 420 - 435. [Abstract] [PDF]

				T. Larsson and M. Patriksson Global Optimality Conditions for Discrete and Nonconvex Optimization--With Applications to Lagrangian Heuristics and Column Generation Operations Research, May 1, 2006; 54(3): 436 - 453. [Abstract] [PDF]