×

Mathematical solutions for solving periodic railway transportation. (English) Zbl 1181.90126

Summary: Train scheduling is a significant issue in the railway industry. Over the last few years, numerous approaches and tools have been developed to compute railway scheduling.
In this paper, we present a set of heuristics for a constraint-based train scheduling tool, which is a project in collaboration with the National Network of Spanish Railways (RENFE), Spain. We formulate train scheduling as a constraint optimization problem. Three heuristics are developed to speed up and direct the search toward suboptimal solutions in periodic train scheduling problems. The feasibility of our problem-oriented heuristics is confirmed with experimentation using real-life data. The results show that these techniques enable MIP solvers such as LINGO and ILOG Concert Technology (CPLEX) to terminate earlier with good solutions.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90B06 Transportation, logistics and supply chain management

Software:

CPLEX; PESPLib
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] M. A. Salido, F. Barber, and L. Ingolotti, “Robustness in railway transportation scheduling,” in Proceedings of the 7th World Congress on Intelligent Control and Automation (WCICA ’08), pp. 2833-2837, IEEE Press, Chongqing, China, June 2008. · doi:10.1109/WCICA.2008.4594481
[2] M. Abril, F. Barber, L. Ingolotti, M. A. Salido, P. Tormos, and A. Lova, “An assessment of railway capacity,” Transportation Research Part E, vol. 44, no. 5, pp. 774-806, 2008. · Zbl 1151.90594 · doi:10.1016/j.tre.2007.04.001
[3] M. A. Salido and F. Barber, “A constraint ordering heuristic for scheduling problem,” in Proceedings of the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA ’03), vol. 2, pp. 476-491, Nottingham, UK, August 2003.
[4] B. Szpigel, “Optimal train scheduling on a single track railway,” in Operational Research ’72, M. Ross, Ed., pp. 343-351, North-Holland, Amsterdam, The Netherlands, 1972.
[5] A. Higgins, E. Kozan, and L. Ferreira, “Heuristic techniques for single line train scheduling,” Journal of Heuristics, vol. 3, no. 1, pp. 43-62, 1997. · Zbl 1071.90535 · doi:10.1023/A:1009672832658
[6] X. Cai and C. J. Goh, “A fast heuristic for the train scheduling problem,” Computers and Operations Research, vol. 21, no. 5, pp. 499-510, 1994. · Zbl 0799.90068 · doi:10.1016/0305-0548(94)90099-X
[7] P. Serafini and W. Ukovich, “A mathematical model for periodic scheduling problems,” SIAM Journal on Discrete Mathematics, vol. 2, no. 4, pp. 550-581, 1989. · Zbl 0676.90030 · doi:10.1137/0402049
[8] K. Nachtigall and S. Voget, “A genetic algorithm approach to periodic railway synchronization,” Computers and Operations Research, vol. 23, no. 5, pp. 453-463, 1996. · Zbl 0847.90098 · doi:10.1016/0305-0548(95)00032-1
[9] M. A. Odijk, “Construction of periodic timetables, part 1: a cutting plane algorithm,” Tech. Rep. 94-61, TU Delft, Delft, The Netherlands, 1994.
[10] L. Kroon and L. Peeters, “A variable trip time model for cyclic railway timetabling,” Transportation Science, vol. 37, no. 2, pp. 198-212, 2003. · doi:10.1287/trsc.37.2.198.15247
[11] C. Liebchen, Periodic timetable optimization in public transport, Ph.D. dissertation, Institut fur Mathematik, Berlin, Germany, 2006. · Zbl 1209.90095
[12] C. K. Chiu, C. M. Chou, J. H. M. Lee, H. F. Leung, and Y. W. Leung, “A constraint-based interactive train rescheduling tool,” Constraints, vol. 7, no. 2, pp. 167-198, 2002. · Zbl 0994.68532 · doi:10.1023/A:1015109732002
[13] A. H. Kaas, Methods to calculate capacity of railways, Ph.D. dissertation, Technical University of Denmark, Lyngby, Denmark, 1998.
[14] I. Amit and D. Goldfarb, “The timetable problem for railways,” Developments in Operations Research, vol. 2, pp. 379-387, 1971.
[15] J.-F. Cordeau, P. Toth, and D. Vigo, “A survey of optimization models for train routing and scheduling,” Transportation Science, vol. 32, no. 4, pp. 380-404, 1998. · Zbl 0987.90507 · doi:10.1287/trsc.32.4.380
[16] I. \cSahin, “Railway traffic control and train scheduling based on inter-train conflict management,” Transportation Research Part B, vol. 33, no. 7, pp. 511-534, 1999. · doi:10.1016/S0191-2615(99)00004-1
[17] K. Ghoseiri, F. Szidarovszky, and M. J. Asgharpour, “A multi-objective train scheduling model and solution,” Transportation Research Part B, vol. 38, no. 10, pp. 927-952, 2004. · doi:10.1016/j.trb.2004.02.004
[18] A. Higgins, E. Kozan, and L. Ferreira, “Optimal scheduling of trains on a single line track,” Transportation Research Part B, vol. 30, no. 2, pp. 147-161, 1996. · doi:10.1016/0191-2615(95)00022-4
[19] A. Higgins, E. Kozan, and L. Ferreira, “Modelling the number and location of sidings on a single line railway,” Computers and Operations Research, vol. 24, no. 3, pp. 209-220, 1997. · Zbl 0889.90062 · doi:10.1016/S0305-0548(96)00042-1
[20] M. Carey, “A model and strategy for train pathing with choice of lines, platforms, and routes,” Transportation Research Part B, vol. 28, no. 5, pp. 333-353, 1994. · doi:10.1016/0191-2615(94)90033-7
[21] A. A. Assad, “Models for rail transportation,” Transportation Research Part A, vol. 14, no. 3, pp. 205-220, 1980. · doi:10.1016/0191-2607(80)90017-5
[22] A. E. Haghani, “Rail freight transportation: a review of recent optimization models for train routing and empty car distribution,” Journal of Advanced Transportation, vol. 21, no. 2, pp. 147-172, 1987.
[23] M. Wardman, “The value of travel time a review of british evidence,” Journal of Transport Economics and Policy, vol. 32, no. 3, pp. 285-316, 1998.
[24] H. Krueger, Parametric Modelling in Rail Capacity Planning, Canadian National Railway, Montreal, Canada, 1998.
[25] E. Weits, “Railway capacity and timetable complexity,” in Proceedings of the 7th International Workshop on Project Management and Scheduling (PMS ’00), Osnabrück, Germany, April 2000.
[26] F. Barber, M. A. Salido, L. P. Ingolotti, M. Abril, A. L. Lova, and M. P. Tormos, “An interactive train scheduling tool for solving and plotting running maps,” in Proceedings of the 10th Conference of the Spanish Association for Artificial Intelligence and 5th Conference on Technology Transfer (TTIA ’03), vol. 3040 of Lecture Notes in Artificial Intelligence, pp. 646-655, San Sebastian, Spain, November 2004. · Zbl 1151.90594
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.