A simulation-based optimization approach to reschedule train traffic in uncertain conditions during disruptions

Authors

1 Department of Transportation Engineering and Planning, School of Civil Engineering, Iran University of Science & Technology, Narmak, Tehran, 1684613114. Iran

2 Department of Transportation Engineering and Planning, School of Civil Engineering, Iran University of Science & Technology, Tehran, Iran

3 Department of Maritime and Transport Technology, Delft University of Technology, Mekelweg 2, 2628 CD Delft, The Netherlands

Abstract

Delays and disruptions reduce the reliability and stability of the rail operations. Railway traffic rescheduling includes ways to manage the operations during and after the occurrences of such disturbances. In this study, we consider the simultaneous presence of large disruptions (temporary full or partial blockage of tracks) as well as stochastic variation of operations, as a source of disturbance. The occurrence time of blockage and its recovery time are given. We designed a simulation-based optimization model that incorporates dynamic dispatch priority rules with the objective of minimizing the total delay time of trains. We moreover design a variable neighborhood search meta-heuristic scheme for handling traffic under the limited capacity close to the blockage. The new plan includes a set of new departure times; dwell times, train running times. We evaluate the proposed model on a set of disruption scenarios covering a large part of the Iranian rail network. The result indicates that the developed simulation-based optimization approach has substantial advantages in producing practical solution quickly, when compared to commercial optimization software. In addition, the solutions have a lower average and smaller standard deviation than currently accepted solutions, determined by human dispatcher or by standard software packages.

Keywords

Main Subjects


References

1. Tornquist, J. and Persson, J.A. \N-tracked railway trac re-scheduling during disturbances", Transportation  Research Part B: Methodological, 41(3), pp. 342- 362 (2007).
2. Hassannayebi, E., Zegordi, S.H., Amin-Naseri, M.R., and Yaghini, M. \Train timetabling at rapid rail transit lines: a robust multi-objective stochastic programming
approach", Operational Research, pp. 1-43 (2016).
3. Narayanaswami, S. and Rangaraj, N. \A MAS architecture
for dynamic, realtime rescheduling and learning
applied to railway transportation", Expert Systems
with Applications, 42(5), pp. 2638-2656 (2015).
4. Hansen, I.A. and Pachl, J., Railway Timetabling &
Operations: Analysis, Modelling, Optimisation, Simulation,
Performance Evaluation (2014).
5. Quaglietta, E., Corman, F., and Goverde, R.M.
\Stability analysis of railway dispatching plans in a
stochastic and dynamic environment", Journal of Rail
Transport Planning & Management, 3(4), pp. 137-149
(2013).
6. Suhl, L., Mellouli, T., Biederbick, C., and Goecke,
J. \Managing and preventing delays in railway trac
by simulation and optimization", In Mathematical
Methods on Optimization in Transportation Systems,
Springer, pp. 3-16 (2001).
7. Takeuchi, Y., Tomii, N., and Hirai, C. \Evaluation
method of robustness for train schedules", Quarterly
Report of RTRI, 48(4), pp. 197-201 (2007).
8. Sajedinejad, A., Mardani, S., Hasannayebi, E., and
Kabirian, A. \SIMARAIL: simulation based optimization
software for scheduling railway network", In Simulation
Conference (WSC), Proceedings of the 2011
Winter, IEEE (2011).
9. Motraghi, A. and Marinov, M.V. \Analysis of urban
freight by rail using event based simulation", Simulation
Modelling Practice and Theory, 25, pp. 73-89
(2012).
10. Hasannayebi, E., Sajedinejad, A., Mardani, S., and
Mohammadi, K.A.R.M. \An integrated simulation
model and evolutionary algorithm for train timetabling
problem with considering train stops for praying", In
Simulation Conference (WSC), Proceedings of the 2012
Winter. IEEE (2012).
11. Buker, T. and Seybold, B. \Stochastic modelling of
delay propagation in large networks", Journal of Rail
Transport Planning & Management, 2(1), pp. 34-50
(2012).
M. Shakibayifar et al./Scientia Iranica, Transactions A: Civil Engineering 25 (2018) 646{662 661
12. Eskandari, H., Rahaee, M.A., Memarpour, M., Nayebi,
E.H., and Malek, S.A. \Evaluation of di erent
berthing scenarios in Shahid Rajaee container terminal
using discrete-event simulation", In Proceedings of
the 2013 Winter Simulation Conference: Simulation:
Making Decisions in a Complex World. 2013, IEEE
Press (2013).
13. Hassannayebi, E., Sajedinejad, A., and Mardani,
S. \Urban rail transit planning using a two-stage
simulation-based optimization approach", Simulation
Modelling Practice and Theory, 49, pp. 151-166 (2014).
14. Abbott, D. and Marinov, M.V. \An event based
simulation model to evaluate the design of a rail interchange
yard, which provides service to high speed and
conventional railways", Simulation Modelling Practice
and Theory, 52, pp. 15-39 (2015).
15. Acuna-Agost, R., Michelon, P., Feillet, D., and Gueye,
S. \A MIP-based local search method for the railway
rescheduling problem", Networks, 57(1), pp. 69-86
(2011).
16. Hassannayebi, E., Zegordi, S.H., and Yaghini, M.
\Train timetabling in urban rail transit line using a
Lagrangian relaxation approach", Applied Mathematical
Modelling, 40(23-24), pp. 9892-9913 (2016).
17. Corman, F., D'Ariano, A., Pacciarelli, D., and Pranzo,
M. \Dispatching and coordination in multi-area railway
trac management", Computers & Operations
Research, 44, pp. 146-160 (2014).
18. Qu, W., Corman, F., and Lodewijks, G. \A review
of real time railway trac management during disturbances",
in Computational Logistics, Springer, pp. 658-
672 (2015).
19. Cacchiani, V., Huisman, D., Kidd, M., Kroon, L.,
Toth, P., Veelenturf, L., and Wagenaar, J. \An
overview of recovery models and algorithms for realtime
railway rescheduling", Transportation Research
Part B: Methodological, 63, pp. 15-37 (2014).
20. Corman, F. and Meng, L. \A review of online dynamic
models and algorithms for railway trac management",
Intelligent Transportation Systems, IEEE
Transactions on, 16(3), pp. 1274-1284 (2015).
21. Fang, W., Yang, S., and Yao, X. \A survey on problem
models and solution approaches to rescheduling in
railway networks", IEEE Transactions on Intelligent
Transportation Systems, 16(6), pp. 2997-3016 (2015).
22. Cheng, Y. \Optimal train trac rescheduling simulation
by a knowledge-based system combined with critical
path method", Simulation Practice and Theory,
4(6), pp. 399-413 (1996).
23. Higgins, A., Kozan, E., and Ferreira, L. \Heuristic
techniques for single line train scheduling", Journal of
Heuristics, 3(1), pp. 43-62 (1997).
24. D'Ariano, A. \Innovative decision support system for
railway trac control", IEEE Intelligent Transportation
Systems Magazine, 1(4), pp. 8-16 (2009).
25. Corman, F., D'Ariano, A., Pacciarelli, D., and Pranzo,
M. \Centralized versus distributed systems to reschedule
trains in two dispatching areas", Public Transport,
2(3), pp. 219-247 (2010).
26. Corman, F., D'Ariano, A., Hansen, I.A., and Pacciarelli,
D. \Optimal multi-class rescheduling of railway
trac", Journal of Rail Transport Planning & Management,
1(1), pp. 14-24 (2011).
27. Dundar, S. and Sahin, _I \Train re-scheduling with
genetic algorithms and arti cial neural networks for
single-track railways", Transportation Research Part
C: Emerging Technologies, 27, pp. 1-15 (2013).
28. Hassannayebi, E. and Kiaynfar, F. \A greedy randomized
adaptive search procedure to solve the train sequencing
and stop scheduling problem in double track
railway lines", Journal of Transportation Research,
9(3), pp. 235-257 (2012).
29. Dollevoet, T., Corman, F., D'Ariano, A., and Huisman,
D. \An iterative optimization framework for
delay management and train scheduling", Flexible
Services and Manufacturing Journal, 26(4), pp. 490-
515 (2014).
30. Hassannayebi, E. and Zegordi, S.H. \Variable and
adaptive neighbourhood search algorithms for rail
rapid transit timetabling problem", Computers & Operations
Research, 78, pp. 439-453 (2017).
31. Hassannayebi, E. and Zegordi, S.H. \Variable and
adaptive neighbourhood search algorithms for rail
rapid transit timetabling problem", Computers & Operations
Research (2016).
32. Grinstead, C.M. and Snell, J.L., Introduction to Probability,
American Mathematical Soc. (2012).
33. Nie, L. and Hansen, I.A. \System analysis of train
operations and track occupancy at railway stations",
European Journal of Transport and Infrastructure Research,
5(1), pp. 31-54 (2005).
34. Borndorfer, R., Schlechte, T., and Swarat, E. \Railway
track allocation-simulation, aggregation, and
optimization", In Proceedings of the 1st International
Workshop on High-Speed and Intercity Railways,
Springer (2012).
35. Paolucci, M. and Pesenti, R. \An object-oriented
approach to discrete-event simulation applied to underground
railway systems", Simulation, 72(6), pp.
372-383 (1999).
36. Venkatesan, K., Gowri, A., and Sivanandan, R. \Development
of microscopic simulation model for heterogeneous
trac using object oriented approach",
Transportmetrica, 4(3), pp. 227-247 (2008).
37. Hullinger, D.R. \Taylor enterprise dynamics", In Simulation
Conference Proceedings, Winter, IEEE (1999).
38. Hassannayebi, E., Sajedinejad, A., and Mardani, S.
\Disruption management in urban rail transit system:
A simulation based optimization approach", In
662 M. Shakibayifar et al./Scientia Iranica, Transactions A: Civil Engineering 25 (2018) 646{662
Handbook of Research on Emerging Innovations in Rail
Transportation Engineering, IgI-Global. pp. 420-450
(2016).
39. Mladenovic, N. and Hansen, P. \Variable neighborhood
search", Computers & Operations Research,
24(11), pp. 1097-1100 (1997).
40. Hansen, P., Mladenovic, N., and Perez, J.A.M. \Variable
neighbourhood search: methods and applications",
Annals of Operations Research, 175(1), pp.
367-407 (2010).
41. Xiao, Y., Zhao, Q., Kaku, I., and Mladenovic, N.
\Variable neighbourhood simulated annealing algorithm
for capacitated vehicle routing problems", Engineering
Optimization, 46(4), pp. 562-579 (2014).
42. Kleijnen, J.P. and Wan, J. \Optimization of simulated
systems: OptQuest and alternatives", Simulation
Modelling Practice and Theory, 15(3), pp. 354-362
(2007).
43. Kelton, W.D., Sadowski, R.P., and Sadowski, D.A.,
Simulation with ARENA, McGraw-Hill, Inc (2002).