An Algorithm for Rescheduling of Trains under Planned Track Closures
Source abstract
Abstract
This work considered a joint problem of train rescheduling and closure planning. The derivation of a new train run schedule and the determination of a closure plan not only must guarantee the satisfaction of all the given constraints but also must optimize the number of accepted closures, the number of approved train runs, and the total time shift between the resultant and the original schedule. Presented is a novel nonlinear mixed integer optimization problem which is valid for a broad class of railway networks. A multi-level hierarchical heuristic algorithm is introduced due to the NP-hardness of the considered optimization problem. The algorithm is able, on an iterative basis, to jointly select closures and train runs, along with the derivation of a train schedule. Results obtained by the algorithm, launched for the conducted experiments, confirm its ability to provide acceptable and feasible solutions in a reasonable amount of time.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Railway Systems and Energy Efficiency · Railway Engineering and Dynamics · Transport and Economic Policies
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Science and Systems Engineering, Faculty of Computer Science and Management, Wroclaw University of Science and Technology, 27 Wyb. Wyspianskiego St., 50-370 Wroclaw, Poland
Funding
European Union within the European Regional Development Fund program
References (65)
Show source-provided references
1. Arenas, D., Chevrier, R., Rodriguez, J., Dhaenens, C., and Hanafi, S. (2013, January 28–30). Application of a co-evolutionary genetic algorithm to solve the periodic railway timetabling problem. Proceedings of the 2013 IEEE International Conference on Industrial Engineering and Systems Management (IESM), Agdal, Morocco.
2. Goverde, R.M., Besinovic, N., Binder, A., Cacchiani, V., Quaglietta, E., Roberti, R., and Toth, P. (2015, January 23–26). A three-level framework for performance-based railway timetabling. Proceedings of the 6th International conference on Railway Operations Modelling and Analysis, RailTokyo 2015, Narashimo, Japan.
3. Optimizing urban rail timetable under time-dependent demand and oversaturated conditions10.1016/j.trc.2013.08.016 ↗
4. Exact formulations and algorithm for the train timetabling problem with dynamic demand10.1016/j.cor.2013.11.003 ↗
5. Filcek, G., Gąsior, D., Hojda, M., and Józefczyk, J. (2016). Joint Train Rescheduling and Track Closures Planning: Model and Solution Algorithm. Information Systems Architecture and Technology: Proceedings of 36th International Conference on Information Systems Architecture and Technology—ISAT 2015–Part I, Springer International Publishing.10.1007/978-3-319-28555-9_19 ↗
6. Hojda, M., and Filcek, G. (2017). A Joint Problem of Track Closure Planning and Train Run Rescheduling with Detours. Advances in Intelligent Systems and Computing—Advances in Systems Science 539, Springer International Publishing.10.1007/978-3-319-48944-5_26 ↗
7. Integrating timetabling and crew scheduling at a freight railway operator10.1287/trsc.2015.0648 ↗
8. Microscopic optimization model and algorithm for integrating train timetabling and track maintenance task scheduling10.1016/j.trb.2019.07.010 ↗
9. Joint optimization of train scheduling and maintenance planning in a railway network: A heuristic algorithm using Lagrangian relaxation10.1016/j.trb.2020.02.008 ↗
10. A Review of Online Dynamic Models and Algorithms for Railway Traffic Management10.1109/TITS.2014.2358392 ↗
11. A model for the delay management problem based on Mixed Integer Programming10.1016/S1571-0661(04)00160-4 ↗
12. Capacity constraints in delay management10.1007/s12469-009-0010-0 ↗
13. Railway timetabling using Lagrangian relaxation10.1287/trsc.32.4.358 ↗
14. Line block prevention in rail line dispatch and simulation models
15. Ping, L., Axin, N., Limin, J., and Fuzhang, W. (2001, January 25–29). Study on intelligent train dispatching. Proceedings of the IEEE Intelligent Transportation Systems Conference Proceedings, Oakland, CA, USA.
16. Zhang, Z., Zhu, C., and Ma, W. (2020). Discrete Optimization on Train Rescheduling on Single-Track Railway: Clustering Hierarchy and Heuristic Search. J. Adv. Transp., 2020.10.1155/2020/8892372 ↗
17. N-tracked railway traffic rescheduling during disturbances10.1016/j.trb.2006.06.001 ↗
18. An exact solution procedure to determine the optimal dispatching times for complex rail networks10.1080/074081791008988 ↗
19. Constraint Programming and Mixed Integer Linear Programming for Rescheduling Trains under Disrupted Operations A Comparative Analysis of Models, Solution Methods, and Their Integration
20. An overview of recovery models and algorithms for real-time railway rescheduling10.1016/j.trb.2014.01.009 ↗
21. Job shop scheduling with blocking and no-wait constraints10.1016/S0377-2217(01)00338-1 ↗
22. Sama, M., Pellegrini, P., D’Ariano, A., Rodriguez, J., and Pacciarelli, D. (2017, January 4–7). The potential of the routing selection problem in real-time railway traffic management. Proceedings of the 7th International Conference on Railway Operations Modelling and Analysis, Lille, France.
23. Modeling network transition constraints with hypergraphs10.1287/trsc.1100.0337 ↗
24. High-Speed Rail Train Timetabling Problem: A Time-Space Network Based Method with an Improved Branch-and-Price Algorithm
25. Acuna-Agost, R. (2010). Mathematical Modeling and Methods for Rescheduling Trains under Disrupted Operations, Universitéd’Avignon et des Pays de Vaucluse.
26. Tornquist, J., and Persson, J.A. (2005, January 3–6). Train traffic deviation handling using Tabu Search and Simulated Annealing. Proceedings of the 38th Hawaii International Conference on System Sciences (HICSS38), Big Island, HI, USA.
27. A railway timetable rescheduling approach for handling large-scale disruptions10.1287/trsc.2015.0618 ↗
28. Andersson, E., Peterson, A., and Törnquist Krasemann, J. (2015, January 23–26). Improved Railway Timetable Robustness for Reduced Traffic Delays–a MILP approach. Proceedings of the 6th International conference on Railway Operations Modelling and Analysis, RailTokyo 2015, Narashimo, Japan.
29. Mixed integer programming for minimizing the period of a cyclic railway timetable for a single track with two train types10.1016/j.cie.2013.06.003 ↗
30. Adjusting a railway timetable in case of partial or complete blockades10.1016/j.ejor.2013.12.020 ↗
31. Scheduling overnight trains for improving both last and first train services in an urban subway network
32. A multi-objective optimization-simulation approach for real time rescheduling in dense railway systems10.1016/j.ejor.2020.03.034 ↗
33. Zhong, Q., Zhang, Y., Wang, D., Zhong, Q., Wen, C., and Peng, Q. (2020). A Mixed Integer Linear Programming Model for Rolling Stock Deadhead Routing before the Operation Period in an Urban Rail Transit Line. J. Adv. Transp., 1–18.10.1155/2020/3809734 ↗
34. Applications of maintenance optimization models: A review and analysis10.1016/0951-8320(95)00076-3 ↗
35. Higgins, A., Ferreira, L., and Lake, M. (1999, January 20–23). Scheduling rail track maintenance to minimise overall delays. Proceedings of the 14th International Symposium on Transportation and Traffic Theory, Jerusalem, Israel.
36. Scheduling preventive railway main- tenance activities10.1057/palgrave.jors.2602085 ↗
37. Scheduling of railway track maintenance activities and crews10.1057/palgrave.jors.2600612 ↗
38. Khalouli, S., Benmansour, R., and Hanafi, S. (2016, January 6–8). An ant colony algorithm based on opportunities for scheduling the preventive railway maintenance. Proceedings of the Control, Decision and Information Technologies (CoDIT), Saint Julian’s, Malta.10.1109/CoDIT.2016.7593629 ↗
39. Dimensioning windows for railway infrastructure maintenance: Cost efficiency versus traffic impact
40. Railway infrastructure maintenance-a survey of planning problems and conducted research10.1016/j.trpro.2015.09.011 ↗
41. Lidén, T. (2014). Survey of Railway Maintenance Activities from a Planning Perspective and Literature Review Concerning the Use of Mathematical Algorithms for Solving Such Planning and Scheduling Problems, Department of Science and Technology, Linköping University. Technical Report.
42. Scheduling of maintenance work of a large-scale tramway network10.1016/j.ejor.2018.04.027 ↗
43. Tactical scheduling of rail operations: The SCAN I system10.1287/trsc.25.1.46 ↗
44. Real-time scheduling of freight railroads10.1016/0191-2615(94)00034-W ↗
45. The Netherlands schedules track maintenance to improve track workers’ safety10.1287/inte.1060.0246 ↗
46. Rescheduling rail networks with maintenance disruptions using problem space search10.1016/j.cor.2010.09.001 ↗
47. Albrecht, A. (2009). Integrating Railway Track Maintenance and Train Timetables. [Ph.D. Thesis, University of South Australia].
48. Maintaining tracks and traffic flow at the same time
49. An optimization model for integrated planning of railway traffic and network maintenance10.1016/j.trc.2016.11.016 ↗
50. Borndörfer, R., and Storandt, S. (2018, January 23–24). Reformulations for Integrated Planning of Railway Traffic and Network Maintenance. Proceedings of the 18th Workshop on Algorithmic Approaches for Transp. Modelling, Optimization, and Systems, Helsinki, Finland.
51. Resource considerations for integrated planning of railway traffic and maintenance windows
52. Integrated optimization on train scheduling and preventive maintenance time slots planning10.1016/j.trc.2017.04.010 ↗
53. Designing alternative railway timetables under infrastructure maintenance possessions10.1016/j.trb.2016.12.019 ↗
54. Timetable rearrangement to cope with railway maintenance activities10.1016/j.cor.2018.02.018 ↗
55. Integrated optimization of train scheduling and maintenance planning on high-speed railway corridors10.1016/j.omega.2018.08.005 ↗
56. Cavone, G., Blenkers, T., van den Boom, T., Dotoli, M., Seatzu, C., and De Schutter, B. (2019, January 23–26). Railway disruption: A bi-level rescheduling algorithm. Proceedings of the 6th International Conference on Control, Decision and Information Technologies (CoDIT’19), Paris, France.10.1109/CoDIT.2019.8820380 ↗
57. Cavone, G., van den Boom, T., Blenkers, L., Dotoli, M., Seatzu, C., and De Schutter, B. (IEEE Trans. Autom. Sci. Eng., 2020). An MPC-Based Rescheduling Algorithm for Disruptions and Disturbances in Large-Scale Railway Networks, IEEE Trans. Autom. Sci. Eng., in print.
58. Integration of real-time traffic management and train control for rail networks—Part 1: Optimization problems and solution approaches10.1016/j.trb.2018.06.006 ↗
59. Research and development of automatic train operation for railway transportation systems: A survey10.1016/j.trc.2017.09.009 ↗
60. (2016, August 30). Zasady Organizacji i Udzielania Zamknięć Torowych Ir-19. Available online: http://www.plk-sa.pl/files/public/user_upload/pdf/Akty_prawne_i_przepisy/Instrukcje/Wydruk/Ir-19.pdf.
61. (2020, September 07). Zasady Organizacji i Udzielania Zamknięć Torowych Ir-19. Available online: https://www.plk-sa.pl/files/public/user_upload/pdf/Akty_prawne_i_przepisy/Instrukcje/Wydruk/Instrukcja_Ir-19.pdf.
62. Scheduling around a small common due date10.1016/0377-2217(91)90228-N ↗
63. (2016, October 30). lp_solve Reference Guide. Available online: http://lpsolve.sourceforge.net/5.5/.
64. Filcek, G., Gasior, D., Hojda, M., and Jozefczyk, J. (2017). An Algorithm for Rescheduling of Trains under Planned Track Closures—Auxiliary Problem Formulations, ResearchGate.
65. On the Complexity of Linear Programming