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 Google Scholar Articles by Fischetti, M. Articles by Zanette, A.

Fast Approaches to Improve the Robustness of a Railway Timetable

Department of Information Engineering, University of Padova, 1 35131-Padova, Italy
Department of Pure and Applied Mathematics, University of Padova, 1 35121-Padova, Italy
Department of Pure and Applied Mathematics, University of Padova, 1 35121-Padova, Italy
matteo.fischetti{at}unipd.it
salvagni{at}math.unipd.it
zanettea{at}dei.unipd.it

The train timetabling problem (TTP) consists of finding a train schedule on a railway network that satisfies some operational constraints and maximizes some profit function that accounts for the efficiency of the infrastructure usage. In practical cases, however, the maximization of the objective function is not enough, and one calls for a robust solution that is capable of absorbing, as much as possible, delays/disturbances on the network. In this paper we propose and computationally analyze four different methods to improve the robustness of a given TTP solution for the aperiodic (noncyclic) case. The approaches combine linear programming (LP) and ad hoc stochastic programming/robust optimization techniques. We computationally compare the effectiveness and practical applicability of the four techniques under investigation on real-world test cases from the Italian railway company Trenitalia. The outcome is that two of the proposed techniques are very fast and provide robust solutions of comparable quality with respect to the standard (but very time consuming) stochastic programming approach.

Key Words: timetabling; integer programming; robustness; stochastic programming; robust optimization
History: Received: December 2007; revised: November 2008; accepted: January 2009.