Optimized decomposition algorithm for train-set scheduling of high-speed railway network

doi:10.16265/j.cnki.issn1003-3033.2019.S2.002

Abstract

Abstract: The train-set scheduling optimization problem with multiple train-sets and multiple depots considering maintenance requirementswas investigated, and a novel two-stage decomposition algorithm was proposed. Firstly, a multi-commodity flow-based MILP optimization model for train-set schedulingwithout consideringmaintenance requirementswas established to obtain multiple candidates train-set schedules. Thenbased on the multiple candidate train-set schedules generated in the first stage, the second stage of the algorithm generated a set of feasible paths for each single train-set unit, where a path allocation sub-problem with maintenance constraints was developed to check the maintenance feasibility. The results show that the proposed optimization approach can save foureight-car size train sets, reduce the total deadhead mileage by 38.4% and save 3% operating cost compared to the manual schedule, and that the operation efficiency of train-setcan be further improvedthrough a more flexible way of composition.

Key words: high-speed railway, train-set circulation plan, decomposition algorithm, maintenance requirements, mixed integer linear programming (MILP)

CLC Number:

X951

ZHONG Qingwei, ZHANG Yongxiang, WEN Chao, PENG Qiyuan, WANG Mengmeng. Optimized decomposition algorithm for train-set scheduling of high-speed railway network[J]. China Safety Science Journal, 2019, 29(S2): 10-17.

References 18

[1]	黄平, 文超, 李忠灿,等. 高速铁路列车晚点时间实时预测的神经网络模型[J]. 中国安全科学学报, 2019,29(增1):20-26.HUANG Ping, WEN Chao, LI Zhongcan, et al.A neural network model for real-time prediction of high-speed railway delays[J].China Safety Science Journal,2019, 29(S1):20-26.
[2]	彭其渊, 张永祥, 鲁工圆, 等. 基于时空资源的铁路客运站到发线运用调整[J]. 同济大学学报:自然科学版, 2018, 47(7):1 011-1 021.PENG Qiyuan, ZHANG Yongxiang, LU Gongyuan, et al. Arrival and departure tracks utilization adjustment method in railway passenger stations based on time-space resources[J]. Journal of Tongji University:Natural Science, 2019,47(7):1 011-1 021.
[3]	钟庆伟, 赵军, 文超, 等. 城轨线路运营时段前车底空驶出场路径优化[J]. 铁道学报, 2018, 40(3):29-38.ZHONG Qingwei, ZHAO Jun, WEN Chao, et al. Optimizing rolling stock deadhead routing problem before operation period of urban rail transit line[J]. Journal of the China Railway Society, 2018, 40(3):29-38.
[4]	ABBINK E, BIANCA V D B, KROON L, et al. Allocation of railway rolling stock for passenger trains[J]. Transportation Science, 2004, 38(1):33-41.
[5]	ALFIERI A, GROOT R, KROON L, et al. Efficient circulation of railway rolling stock[J]. Transportation Science, 2006, 40(3):378-391.
[6]	FIOOLE P J, KROON L, GÁBOR M, et al. A rolling stock circulation model for combining and splitting of passenger trains[J]. European Journal of Operational Research, 2006, 174(2):1 281-1 297.
[7]	GÁBOR M, KROON L. Maintenance routing for train units: the transition model[J]. Computers & Operations Research, 2005, 39(4):518-525.
[8]	GÁBOR M, KROON L. Maintenance routing for train units: the interchange model[J]. Computers & Operations Research, 2007, 34(4):1 121-1 140.
[9]	BORNDRFER R, REUTHER M, SCHLECHTE T, et al. Integrated optimization of rolling stock rotations for intercity railways[J]. Transportation Science, 2015, 50(3):863-877.
[10]	HAAHR J, LUSBY R M. Integrating rolling stock scheduling with train unit shunting[J]. European Journal of Operational Research, 2017, 259(2):452-468.
[11]	聂磊, 赵鹏, 杨浩, 等. 高速铁路动车组运用的研究[J].铁道学报, 2001, 23(3):1-7.NIE Lei, ZHAO Peng, YANG Hao,et al. Study on motor trainset operation in high speed railway [J]. Journal of the China Railway Society, 2001, 23(3):1-7.
[12]	赵鹏, 富井规雄. 动车组运用计划及其编制算法[J]. 铁道学报, 2003, 25(3):1-7.ZHAO Peng, NORIO T. Train-set scheduling and an algorithm [J]. Journal of the China Railway Society, 2003, 25(3):1-7.
[13]	赵鹏, 富井规雄. 基于路段交换的多基地动车组运用计划的编制算法[J]. 铁道学报, 2004, 26(1):7-11.ZHAO Peng, NORIO T. An algorithm for multiple-bases train-set scheduling based on path-exchange[J]. Journal of the China Railway Society, 2004, 26(1):7-11.
[14]	史峰, 周文梁, 郁宇卫, 等. 客运专线动车组运用计划优化模型与算法[J]. 铁道学报, 2011, 33(1):8-13.SHI Feng, ZHOU Wenliang, YU Yuwei,et al. Optimized model and algorithm of motor trains-sets scheduling for dedicated passenger lines [J]. Journal of the China Railway Society, 2011, 33(1):8-13.
[15]	张才春, 陈建华, 花伟. 基于不同检修能力的动车组运用计划研究[J].中国铁道科学, 2010, 31(5):130-133.ZHANG Caichun, CHEN Jianhua, HUA Wei. Research on the EMU operation plan based on different maintenance capacity [J].China Railway Science, 2010, 31(5):130-133.
[16]	李华, 韩宝明, 张琦,等. 动车组交路计划优化模型与算法研究[J]. 铁道学报, 2013, 35(3):1-8.LI Hua, HAN Baoming, ZHANG Qi,et al. Research on optimization model and algorithm of EMU circulation plan [J]. Journal of the China Railway Society, 2013, 35(3):1-8.
[17]	陈旭, 李海鹰, 王莹, 等. 放射状路网条件下动车组运用优化研究[J]. 铁道学报, 2017, 39(11):28-34.CHEN Xu, LI Haiying, WANG Ying, et at. Research on Optimization of EMU scheduling for Radial HSR Network [J]. Journal of the China Railway Society, 2017, 39(11):28-34.
[18]	我国首列可变编组动车组已具备出厂条件 [EB/OL]. (2019-02-25).http://www.gd.xinhuanet.com/newscenter/2019-02/25/c_1124157073.htm.