A Lagrangian heuristic algorithm for a real-world train timetabling problem. (English) Zbl 1120.90324
Summary: The train timetabling problem (TTP) aims at determining an optimal timetable for a set of trains which does not violate track capacities and satisfies some operational constraints.
In this paper, we describe the design of a train timetabling system that takes into account several additional constraints that arise in real-world applications. In particular, we address the following issues:
\(\bullet\) Manual block signaling for managing a train on a track segment between two consecutive stations.
\(\bullet\) Station capacities, i.e., maximum number of trains that can be present in a station at the same time.
\(\bullet\) Prescribed timetable for a subset of the trains, which is imposed when some of the trains are already scheduled on the railway line and additional trains are to be inserted.
\(\bullet\) Maintenance operations that keep a track segment occupied for a given period.
We show how to incorporate these additional constraints into a mathematical model for a basic version of the problem, and into the resulting Lagrangian heuristic. Computational results on real-world instances from Rete Ferroviaria Italiana (RFI), the Italian railway infrastructure management company, are presented.
In this paper, we describe the design of a train timetabling system that takes into account several additional constraints that arise in real-world applications. In particular, we address the following issues:
\(\bullet\) Manual block signaling for managing a train on a track segment between two consecutive stations.
\(\bullet\) Station capacities, i.e., maximum number of trains that can be present in a station at the same time.
\(\bullet\) Prescribed timetable for a subset of the trains, which is imposed when some of the trains are already scheduled on the railway line and additional trains are to be inserted.
\(\bullet\) Maintenance operations that keep a track segment occupied for a given period.
We show how to incorporate these additional constraints into a mathematical model for a basic version of the problem, and into the resulting Lagrangian heuristic. Computational results on real-world instances from Rete Ferroviaria Italiana (RFI), the Italian railway infrastructure management company, are presented.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
Train scheduling; Path allocation; Lagrangian relaxation; Lagrangian heuristic; Computational resultsReferences:
| [1] | Brännlund, U.; Lindberg, P. O.; Nöu, A.; Nilsson, J. E., Allocation of scarce track capacity using Lagrangian relaxation, Transportation Sci., 32, 358-369 (1998) · Zbl 1004.90035 |
| [2] | Cai, X.; Goh, C. J., A fast heuristic for the train scheduling problem, Comput. Oper. Res., 21, 499-510 (1994) · Zbl 0799.90068 |
| [3] | Caprara, A.; Fischetti, M.; Toth, P., Modeling and solving the train timetabling problem, Oper. Res., 50, 851-861 (2002) · Zbl 1163.90482 |
| [4] | Carey, M.; Lockwood, D., A model, algorithms and strategy for train pathing, J. Oper. Res. Soc., 46, 988-1005 (1995) · Zbl 0832.90068 |
| [5] | Escudero, L. F.; Guignard, M.; Malik, K., A Lagrangian relax and cut approach for the sequential ordering with precedence constraints, Ann. Oper. Res., 50, 219-237 (1994) · Zbl 0833.90068 |
| [6] | Fisher, M., Optimal solution of vehicle routing problems using minimum \(k\)-trees, Oper. Res., 42, 626-642 (1994) · Zbl 0815.90066 |
| [7] | Higgings, A.; Kozan, E.; Ferreira, L., Heuristic techniques for single line train scheduling, J. Heuristics, 3, 43-62 (1997) · Zbl 1071.90535 |
| [8] | Jovanovic, D.; Harker, P. T., Tactical scheduling of rail operationsthe SCAN I system, Transportation Sci., 25, 46-64 (1991) |
| [9] | Lindner, T.; Zimmermann, U. T., Cost-oriented train scheduling, (Eighth International Conference on Computer Aided Scheduling of Public Transport (CASPT 2000). Eighth International Conference on Computer Aided Scheduling of Public Transport (CASPT 2000), Berlin (June 2000)) · Zbl 1109.90042 |
| [10] | E. Oliveira, B.M. Smith, A job-shop scheduling model for the single-track railway scheduling problem, Technical Report 2000.21, School of Computing Research Report, University of Leeds, 2000.; E. Oliveira, B.M. Smith, A job-shop scheduling model for the single-track railway scheduling problem, Technical Report 2000.21, School of Computing Research Report, University of Leeds, 2000. |
| [11] | L.W.P. Peeters, Cyclic railway timetable optimization, Ph.D. Thesis, Erasmus Research Institute of Management, Erasmus University Rotterdam, 2003.; L.W.P. Peeters, Cyclic railway timetable optimization, Ph.D. Thesis, Erasmus Research Institute of Management, Erasmus University Rotterdam, 2003. |
| [12] | L.W.P. Peeters, L.G. Kroon, A cycle based optimization model for the cyclic railway timetabling problem, in: J. Daduna, S. Voss (Eds.), Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, vol. 505, Springer, Berlin, 2001, pp. 275-296.; L.W.P. Peeters, L.G. Kroon, A cycle based optimization model for the cyclic railway timetabling problem, in: J. Daduna, S. Voss (Eds.), Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, vol. 505, Springer, Berlin, 2001, pp. 275-296. · Zbl 0989.90521 |
| [13] | A. Schrijver, A. Steenbeek, Timetable construction for railned, Technical Report, CWI, Amsterdam, 1994 (in Dutch).; A. Schrijver, A. Steenbeek, Timetable construction for railned, Technical Report, CWI, Amsterdam, 1994 (in Dutch). |
| [14] | Szpigel, B., Optimal train scheduling on a single track railway, (Ross, M., OR’72 (1973), North-Holland: North-Holland Amsterdam), 343-351 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
