Simultaneous Train Rescheduling through Cancelling, Delaying and Re-Ordering Policies: Three-Phase Solution Method with Guaranteed Optimality

Authors

1 Faculty of Transportation, Isfahan University of Technology, Isfahan, Iran

2 Department of Civil and Environment Engineering, Tarbiat Modares University, Tehran, Iran

3 Department of Industrial Engineering, University of Tehran, Tehran, Iran

Abstract

In this article, a new approach is presented to solve the double-track railway rescheduling problem, when an incident occurs into one of the block sections of the railway. The approach simultaneously considers three rescheduling policies: cancelling, delaying and reordering. To find the optimal conflict-free timetables compatible with the approach, a mathematical model and an exact three-phase solution method are proposed. The method is based on Branch-and-Bound (B&B) algorithm. The lower bound consists of two cost parts: the cost of deviation from the primary timetable and the cost of train cancellation. To generate an appropriate upper bound, the method exploits an innovative algorithm called "Local Left Shifting". A heuristic beam search technique is also developed for tackling the large-scale problems. An experimental analysis on two double-track railways of the Iranian network indicates that the proposed solution method provides the optimal solution in much shorter time, compared with the time taken to solve the mathematical model by CPLEX software. Based on the findings of this research, it is possible to optimally retrieve the primary timetable after incident occurrence during a pre-determined time horizon.

Keywords

References

References:
1. Hansen, I.A. "Railway network timetabling and dynamic traffic management", International Journal of Civil Engineering, 8(1), pp. 19-32 (2010).
2. Yaghini, M., Nikoo, N. and Ahadi, H.R. "An integer  rogramming model for analysing impacts of different train types on railway line capacity", Transport, 29(1), pp. 28-35 (2014).
3. Xu, J., Zhang, Z. and Mookerjee, V. "Applying bi-random MODM model to navigation coordinated scheduling: a case study of three Gorges project", Transport, 28(2), pp. 140-157 (2013).
4. Chen, C., Zeng, Q. and Zhang, Z. "An integrating scheduling model for mixed cross-operation in container terminals", Transport, 27(4), pp. 405-413 (2012).
5. Spliet, R., Gabor, A.F. and Dekker, R. "The vehicle rescheduling problem", Computers and Operations Research, 43, pp. 129-136 (2014).
6. Veelenturf, L.P. "Railway crew rescheduling with retiming", Transportation Research. C, 20(1), pp. 95-110 (2012).
7. Alwadood, Z., Shuib, A. and Abd Hamid, N. "Mathematical rescheduling models for railway services", International Journal of Mathematical, Computational, Physical and Quantum Engineering., 7(8), pp. 798-803 (2013).
8. Cacchiani, V., Huisman, D., Kidd, M., Kroon, L., Toth, P., Veelenturf, L. and Wagenaar, L. "An overview of recovery models and algorithms for realtime railway rescheduling", Transportation Research Part B, 63, pp. 15-37 (2014).
9. Alwadood, Z., Shuib, A. and Abd. Hamid, N. "A review on quantitative models in railway rescheduling", International Journal of Scientific & Engineering Research, 3(6), pp. 1-7 (2012).
10. Yaghini, M., Momeni, M. and Sarmadi, M. "Solving train formation problem using simulated annealing algorithm in a simplex framework", Journal of Advanced Transportation, 48(5), pp. 402-416 (2014).
11. D'Ariano, A. "Innovative decision support system for railway traffic control", IEEE Intelligent Transportation System Magazine, 1(4), pp. 8-16 (2009).
12. D'Ariano, A., D'Urgolo, P., Pacciarelli, D. and Pranzo, M. "Optimal sequencing of aircrafts take-off and landing at a busy airport", in Proceeding of 13th International IEEE Conference on Intelligent Transportation System, Madeira Island, Portugal, pp. 1569- 1574 (2010).
13. Corman, F., D'Ariano, A., Hansen, I., Pacciarelli, D. and Pranzo, M. "Dispatching trains during seriously disrupted traffic situations", in Proceeding of 8th IEEE International Conference on Network, Sensing and Control, Delft, The Netherlands, pp. 323-328 (2011).
14. D'Ariano, A., Pranzo, M. and Hansen, I. "Conflict resolution and train speed coordination solving realtime timetable perturbations", IEEE Transaction on Intelligent Transportation System., 8(2), pp. 208-222 (2007).
15. Tornquist, J. and Persson, J. "N-tracked railway traffic rescheduling during disturbances", Transportation Research Part B, 41(3), pp. 342-362 (2007).
16. Burdett, R.L. and Kozan, E. "Techniques for inserting additional trains into existing timetables", Transportation Research Part B, 43, pp. 821-836 (2009).
17. Sato, K. and Fukumura, N. "An algorithm for freight train driver rescheduling in disruption situations", QR of RTRI, 51(2), pp. 72-76 (2010).
18. Cacchiani, V. and Caprara, A. "Scheduling extra freight trains on railway networks", Transportation Research Part B, 44(2), pp. 215-231 (2010).
19. D'Ariano, A. "Improving real-time train dispatching performance: Optimization models and algorithms for re-timing, re-ordering and local re-routing", 4OR: A Quarterly Journal of Operations Research, 8(4), pp. 429-432 (2010).
20. Mu, S. and Dessouky, M. "Scheduling freight trains traveling on complex networks", Transportation Research part B, 45(7), pp. 1103-1123 (2011).
21. Caimi, G., Fuchsberger, M., Laumanns, M. and Luthi, M. "A model predictive control approach for discretetime rescheduling in complex central railway station areas", Computers and Operations Research, 39(11), pp. 2578-2593 (2011).
22. Corman, F., D'Ariano, A. and Pacciarelli, D. "Biobjective conflict detection and resolution in railway traffic management", Transportation Research part C, 20(1), pp. 79-94 (2012).
23. Sato, K. and Fukumura, N. "Real-time freight locomotive rescheduling and uncovered train detection during disruption", European Journal of Operational Research, 221(3), pp. 636-648 (2012).
24. Albrecht, A.R., Panton, D.M. and Lee, D.H. "Rescheduling rail networks with maintenance disruptions using problem space search", Computers and Operations Research, 40(3), pp. 703-712 (2013).
25. Dundar, S. and Sahin, _I. "Train re-scheduling with genetic algorithms and artificial neural networks for single-track railways", Transportation Research Part C: Emerging Technologies, 27, pp. 1-15 (2013).
26. Louwerse, I. and Huisman, D. "Adjusting a railway timetable in case of partial or complete blockades", European Journal of Operational Research, 235(3), pp. 583-593 (2014).
27. Pellegrini, P., Marliere, G. and Rodriguez, J. "Optimal train routing and scheduling for managing traffic perturbations in complex junctions", Transportation Research Part B, 59, pp. 58-80 (2014).
28. Wang, Y., Schutter, B.D., Boom, T. and Ning, B. "Optimal trajectory planning for trains under fixed and moving signalling systems using mixed integer linear programming", Control Engineering Practice, 22, pp. 44-56 (2014).
29. Veelenturf, L., Kidd, M., Cacchiani, V., Kroon, L.G. and Toth, P. "A Railway timetable rescheduling approach for handling large scale disruptions", ERIM Report Series Reference No. ERS-2014-010-LIS. Available at SSRN: http://ssrn.com/abstract=2472934.
30. Kang, L., Wu, J., Sun, H., Zhu, X. and Wang, Bo. "A practical model for last train rescheduling with train delay in urban railway transit networks", Omega, 50, pp. 29-42 (2015).
31. Zhan, S., Kroon, L.G., Veelenturf, L.P. and Wagenaar, J. "Real-time high-speed train rescheduling in case of a complete blockade", Transportation Research Part B: Methodological, 78, pp. 182-201 (2015).
32. D'Ariano, A., Pacciarelli, D. and Pranzo, M. "A branch and bound algorithm for scheduling trains in a railway network", European Journal of Operational Research, 183(2), pp. 643-657 (2007).
33. Tamannaei, M., Saffarzadeh, M., Jamili, A. and Seyedabrishami, S.E. "A novel train rescheduling approach in double-track railways: optimization model and solution method based on simulated annealing algorithm", International Journal of Civil Engineering, 14(3), pp. 139-150 (2016).
34. Tamannaei, M., Saffarzadeh, M., Jamili, A., Seyedabrishami, S.E. and Bagheri, S.R., Proposing a New Train Rescheduling Approach with Simultaneous Consideration of Cancelling, Delaying and Re-ordering Policies, in Transportation Research Board (TRB), Washington, United States (2015).
35. AitZai, A. and Boudhar, M. "Parallel branch-andbound and parallel PSO algorithms for job shop scheduling problem with blocking", International Journal of Operational Research, 16(1), pp. 14-37 (2013).
36. Shafia, M.A., Pourseyed Aghaee, M., Sadjadi, S.J. and Jamili, A. "Robust train timetabling problem: mathematical model and branch and bound algorithm", IEEE Transaction on Intelligent Transportation System, 13(1), pp. 307-317 (2012).
37. Caprara, A., Fischetti, M. and Toth, P. "Modelling and solving the train timetabling problem", Operations Research, 50(5), pp. 851-861 (2002).
38. D'Ariano, A. "Improving real-time train dispatching: models, algorithms and applications", PhD Thesis, Series no. T2008/6, the Netherlands TRAIL Research School (2008).
39. Jafari, N. and Zegordi, S.H. "Simultaneous recovery model for aircraft and passengers", Journal of Franklin Institute, 348(7), pp. 1638-1655 (2011).
Scientia Iranica
Volume 24, Issue 1 - Serial Number 1
Transactions on Civil Engineering (A)
January and February 2017
Pages 121-135

Files

History

  • Receive Date: 03 May 2015
  • Revise Date: 23 August 2022
  • Accept Date: 09 July 2017

Share

How to cite

Statistics