Improved Genetic Algorithm for Train Platform Rescheduling Under Train Arrival Delays

Shuxin Ding; Tao Zhang; Rongsheng Wang; Yanhao Sun; Xiaozhao Zhou; Chen Chen; Zhiming Yuan

doi:10.20965/jaciii.2023.p0959

single-jc.php

« previous

JACIII Vol.27 No.5 pp. 959-966

doi: 10.20965/jaciii.2023.p0959

(2023)

Research Paper:

Views over last 60 days: 124

Improved Genetic Algorithm for Train Platform Rescheduling Under Train Arrival Delays

Shuxin Ding^1,2 , Tao Zhang^1,2, Rongsheng Wang^3,4, Yanhao Sun^1,2 , Xiaozhao Zhou^1,2, Chen Chen^5, and Zhiming Yuan^1,*2,†

^*1Signal and Communication Research Institute, China Academy of Railway Sciences Co., Ltd.
No.2 Daliushu Road, Haidian District, Beijing 100081, China

^*2Traffic Management Laboratory for High-Speed Railway, National Engineering Research Center of System Technology for High-Speed Railway and Urban Rail Transit, China Academy of Railway Sciences Co., Ltd.
No.2 Daliushu Road, Haidian District, Beijing 100081, China

^*3Scientific and Technological Information Research Institute, China Academy of Railway Sciences Co., Ltd.
No.2 Daliushu Road, Haidian District, Beijing 100081, China

^*4Office of Scientific and Technological Achievements and Intellectual Property, China State Railway Group Co., Ltd.
No.2 Daliushu Road, Haidian District, Beijing 100081, China

^*5National Key Laboratory of Autonomous Intelligent Unmanned Systems, School of Automation, Beijing Institute of Technology
No.5 Zhongguancun South Street, Haidian District, Beijing 100081, China

^†Corresponding author

Received:

March 17, 2023

Accepted:

June 16, 2023

Published:

September 20, 2023

Keywords:

high-speed railway, train platform rescheduling, conflict resolution, genetic algorithm, mixed encoding

Abstract

In this study, the train platform rescheduling problem (TPRP) at a high-speed railway station is analyzed. The adjustments of the train track assignment and train arrival/departure times under train arrival delays are addressed in the TPRP. The problem is formulated as a mixed-integer nonlinear programming model that minimizes the weighted sum of total train delays and rescheduling costs. An improved genetic algorithm (GA) is proposed, and the individual is represented as a platform track assignment and train departure priority, which is a mixed encoding scheme with integers and permutations. The individual is decoded into a feasible schedule comprising the platform track assignment and arrival/departure times of trains using a rule-based method for conflict resolution in the platform tracks and arrival/departure routes. The proposed GA is compared with state-of-the-art evolutionary algorithms. The experimental results confirm the superiority of the GA, which uses the mixed encoding and rule-based decoding, in terms of constraint handling and solution quality.

Cite this article as:

S. Ding, T. Zhang, R. Wang, Y. Sun, X. Zhou, C. Chen, and Z. Yuan, “Improved Genetic Algorithm for Train Platform Rescheduling Under Train Arrival Delays,” J. Adv. Comput. Intell. Intell. Inform., Vol.27 No.5, pp. 959-966, 2023.

Data files:

References

[1] S. Ding, T. Zhang, Z. Liu, R. Wang, S. Lu, B. Xin, and Z. Yuan, “A memetic algorithm for high-speed railway train timetable rescheduling,” J. Adv. Comput. Intell. Intell. Inform., Vol.26, No.3, pp. 407-417, 2022. https://doi.org/10.20965/jaciii.2022.p0407
[2] G. Lu, J. Ning, X. Liu, and Y. M. Nie, “Train platforming and rescheduling with flexible interlocking mechanisms: An aggregate approach,” Transportation Research Part E: Logistics and Transportation Review, Vol.159, Article No.102622, 2022. https://doi.org/10.1016/j.tre.2022.102622
[3] P. Chakroborty and D. Vikram, “Optimum assignment of trains to platforms under partial schedule compliance,” Transportation Research Part B: Methodological, Vol.42, No.2, pp. 169-184, 2008. https://doi.org/10.1016/j.trb.2007.07.003
[4] R. Wang, Y. Bao, and W. Hao, “Reallocating siding tracks in a railway station under severe disruptions,” Proc. of 2018 Int. Conf. on Intelligent Rail Transportation (ICIRT), 2018. https://doi.org/10.1109/ICIRT.2018.8641521
[5] Y. Zhang, Q. Zhong, Y. Yin, X. Yan, and Q. Peng, “A fast approach for reoptimization of railway train platforming in case of train delays,” J. of Advanced Transportation, Article No.5609524, 2020. https://doi.org/10.1155/2020/5609524
[6] R. García-Ródenas, M. L. López-García, L. Cadarso, and E. Codina, “A mixed-integer linear program for real-time train platforming management,” Transportation Research Procedia, Vol.62, pp. 815-823, 2022. https://doi.org/10.1016/j.trpro.2022.02.101
[7] L. Zhang, W. Zheng, K. Huang, and H. Dong, “Research on optimization method of station track platform based on improved discrete teaching and learning optimization algorithm,” Proc. of 2021 IEEE Int. Intelligent Transportation Systems Conf. (ITSC), pp. 3432-3437, 2021. https://doi.org/10.1109/ITSC48978.2021.9565093
[8] S. Ding, T. Zhang, R. Wang, Y. Sun, X. Zhou, and C. Chen, “A mixed encoding genetic algorithm for train platforming rescheduling under train delays,” Proc. of the 10th Int. Symp. on Computational Intelligence and Industrial Applications (ISCIIA2022), Article No.B3-4, 2022.
[9] S. Ding, C. Chen, Q. Zhang, B. Xin, and P. Pardalos, “Metaheuristics for resource deployment under uncertainty in complex systems,” CRC Press, 2022.
[10] A. J. Umbarkar and P. D. Sheth, “Crossover operators in genetic algorithms: A review,” ICTACT J. on Soft Computing, Vol.6, No.1, pp. 1083-1092, 2015. https://doi.org/10.21917/ijsc.2015.0150
[11] J. Löfberg, “YALMIP: A toolbox for modeling and optimization in MATLAB,” Proc. of 2004 IEEE Int. Conf. on Robotics and Automation, pp. 284-289, 2004. https://doi.org/10.1109/CACSD.2004.1393890
[12] A. K. Qin, V. L. Huang, and P. N. Suganthan, “Differential evolution algorithm with strategy adaptation for global numerical optimization,” IEEE Trans. on Evolutionary Computation, Vol.13, No.2, pp. 398-417, 2008. https://doi.org/10.1109/TEVC.2008.927706
[13] J. J. Liang, A. K. Qin, P. N. Suganthan, and S. Baskar, “Comprehensive learning particle swarm optimizer for global optimization of multimodal functions,” IEEE Trans. on Evolutionary Computation, Vol.10, No.3, pp. 281-295, 2006. https://doi.org/10.1109/TEVC.2005.857610
[14] P. Kora and P. Yadlapalli, “Crossover operators in genetic algorithms: A review,” Int. J. of Computer Applications, Vol.162, No.10, pp. 34-36, 2017. http://doi.org/10.5120/ijca2017913370
[15] S. Mirjalili, “Genetic algorithm,” Evolutionary Algorithms and Neural Networks, pp. 43-55, 2019. https://doi.org/10.1007/978-3-319-93025-1_4
[16] S. Peng, X. Yang, S. Ding, J. Wu, and H. Sun, “A dynamic rescheduling and speed management approach for high-speed trains with uncertain time-delay,” Information Sciences, Vol.632, pp. 201-220, 2023. https://doi.org/10.1016/j.ins.2023.03.003
[17] X. Meng, Y. Wang, W. Xiang, and L. Jia, “An integrated model for train rescheduling and station track assignment,” IET Intelligent Transport Systems, Vol.15, No.1, pp. 17-30, 2021. https://doi.org/10.1049/itr2.12001

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] S. Ding, T. Zhang, Z. Liu, R. Wang, S. Lu, B. Xin, and Z. Yuan, “A memetic algorithm for high-speed railway train timetable rescheduling,” J. Adv. Comput. Intell. Intell. Inform., Vol.26, No.3, pp. 407-417, 2022. https://doi.org/10.20965/jaciii.2022.p0407

[2] [2] G. Lu, J. Ning, X. Liu, and Y. M. Nie, “Train platforming and rescheduling with flexible interlocking mechanisms: An aggregate approach,” Transportation Research Part E: Logistics and Transportation Review, Vol.159, Article No.102622, 2022. https://doi.org/10.1016/j.tre.2022.102622

[3] [3] P. Chakroborty and D. Vikram, “Optimum assignment of trains to platforms under partial schedule compliance,” Transportation Research Part B: Methodological, Vol.42, No.2, pp. 169-184, 2008. https://doi.org/10.1016/j.trb.2007.07.003

[4] [4] R. Wang, Y. Bao, and W. Hao, “Reallocating siding tracks in a railway station under severe disruptions,” Proc. of 2018 Int. Conf. on Intelligent Rail Transportation (ICIRT), 2018. https://doi.org/10.1109/ICIRT.2018.8641521

[5] [5] Y. Zhang, Q. Zhong, Y. Yin, X. Yan, and Q. Peng, “A fast approach for reoptimization of railway train platforming in case of train delays,” J. of Advanced Transportation, Article No.5609524, 2020. https://doi.org/10.1155/2020/5609524

[6] [6] R. García-Ródenas, M. L. López-García, L. Cadarso, and E. Codina, “A mixed-integer linear program for real-time train platforming management,” Transportation Research Procedia, Vol.62, pp. 815-823, 2022. https://doi.org/10.1016/j.trpro.2022.02.101

[7] [7] L. Zhang, W. Zheng, K. Huang, and H. Dong, “Research on optimization method of station track platform based on improved discrete teaching and learning optimization algorithm,” Proc. of 2021 IEEE Int. Intelligent Transportation Systems Conf. (ITSC), pp. 3432-3437, 2021. https://doi.org/10.1109/ITSC48978.2021.9565093

[8] [8] S. Ding, T. Zhang, R. Wang, Y. Sun, X. Zhou, and C. Chen, “A mixed encoding genetic algorithm for train platforming rescheduling under train delays,” Proc. of the 10th Int. Symp. on Computational Intelligence and Industrial Applications (ISCIIA2022), Article No.B3-4, 2022.

[9] [9] S. Ding, C. Chen, Q. Zhang, B. Xin, and P. Pardalos, “Metaheuristics for resource deployment under uncertainty in complex systems,” CRC Press, 2022.

[10] [10] A. J. Umbarkar and P. D. Sheth, “Crossover operators in genetic algorithms: A review,” ICTACT J. on Soft Computing, Vol.6, No.1, pp. 1083-1092, 2015. https://doi.org/10.21917/ijsc.2015.0150

[11] [11] J. Löfberg, “YALMIP: A toolbox for modeling and optimization in MATLAB,” Proc. of 2004 IEEE Int. Conf. on Robotics and Automation, pp. 284-289, 2004. https://doi.org/10.1109/CACSD.2004.1393890

[12] [12] A. K. Qin, V. L. Huang, and P. N. Suganthan, “Differential evolution algorithm with strategy adaptation for global numerical optimization,” IEEE Trans. on Evolutionary Computation, Vol.13, No.2, pp. 398-417, 2008. https://doi.org/10.1109/TEVC.2008.927706

[13] [13] J. J. Liang, A. K. Qin, P. N. Suganthan, and S. Baskar, “Comprehensive learning particle swarm optimizer for global optimization of multimodal functions,” IEEE Trans. on Evolutionary Computation, Vol.10, No.3, pp. 281-295, 2006. https://doi.org/10.1109/TEVC.2005.857610

[14] [14] P. Kora and P. Yadlapalli, “Crossover operators in genetic algorithms: A review,” Int. J. of Computer Applications, Vol.162, No.10, pp. 34-36, 2017. http://doi.org/10.5120/ijca2017913370

[15] [15] S. Mirjalili, “Genetic algorithm,” Evolutionary Algorithms and Neural Networks, pp. 43-55, 2019. https://doi.org/10.1007/978-3-319-93025-1_4

[16] [16] S. Peng, X. Yang, S. Ding, J. Wu, and H. Sun, “A dynamic rescheduling and speed management approach for high-speed trains with uncertain time-delay,” Information Sciences, Vol.632, pp. 201-220, 2023. https://doi.org/10.1016/j.ins.2023.03.003

[17] [17] X. Meng, Y. Wang, W. Xiang, and L. Jia, “An integrated model for train rescheduling and station track assignment,” IET Intelligent Transport Systems, Vol.15, No.1, pp. 17-30, 2021. https://doi.org/10.1049/itr2.12001

Improved Genetic Algorithm for Train Platform Rescheduling Under Train Arrival Delays

Shuxin Ding*1,*2 , Tao Zhang*1,*2, Rongsheng Wang*3,*4, Yanhao Sun*1,*2 , Xiaozhao Zhou*1,*2, Chen Chen*5, and Zhiming Yuan*1,*2,†

Shuxin Ding^1,2 , Tao Zhang^1,2, Rongsheng Wang^3,4, Yanhao Sun^1,2 , Xiaozhao Zhou^1,2, Chen Chen^5, and Zhiming Yuan^1,*2,†