Fast Approaches to Improve the Robustness of a Railway Timetable
- 1 August 2009
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 43 (3) , 321-335
Abstract
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.Keywords
This publication has 9 references indexed in Scilit:
- Cyclic Railway Timetabling: A Stochastic Optimization Approach2007
- A Lagrangian heuristic algorithm for a real-world train timetabling problemDiscrete Applied Mathematics, 2006
- The empirical behavior of sampling methods for stochastic programmingAnnals of Operations Research, 2006
- Monte Carlo sampling approach to stochastic programmingESAIM: Proceedings, 2003
- The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational StudyComputational Optimization and Applications, 2003
- Modeling and Solving the Train Timetabling ProblemOperations Research, 2002
- On Latin hypercube samplingThe Annals of Statistics, 1996
- A Mathematical Model for Periodic Scheduling ProblemsSIAM Journal on Discrete Mathematics, 1989
- Importance Sampling in Monte Carlo AnalysesOperations Research, 1961