Modeling and Solving the Train Timetabling Problem

Alberto Caprara, Matteo Fischetti and Paolo Toth ()
Additional contact information
Alberto Caprara: DEIS, University of Bologna, Italy
Matteo Fischetti: DEIS, University of Padova, Italy
Paolo Toth: DEIS, University of Bologna, Italy

Operations Research, 2002, vol. 50, issue 5, 851-861

Abstract: 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.

Keywords: Programming algorithms: Lagrangian relaxation; heuristics; Transportation: train timetabling; railway (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (111)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.50.5.851.362 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:50:y:2002:i:5:p:851-861

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().