Optimization Model and Algorithm for Train-Set Scheduling Based on Trip Sequence
ZHONG Qingwei1,2, ZHANG Yongxiang1,2, WANG Dian1,2, YIN Yong1,2, YAN Xu1,2, PENG Qiyuan1,2
1. School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 611756, China; 2. National United Engineering Laboratory of Integrated and Intelligent Transportation, Southwest Jiaotong University, Chengdu 611756, China
Abstract：Usually，the train-set schedule involves several practical aspects，such as operational safety，efficiency，and cost. The quality and efficiency of the schedule have a significant impact on the operation of high-speed railways. In order to quickly obtain a high-quality train-set schedule，a mixed-integer linear programming (MILP) model that takes composition changes on the basis of the trip sequences was established with the optimization goals of reducing operating costs and total deadhead mileages. Furthermore，an iterative gap reducing algorithm is developed to solve the MILP model，which divides the whole problem into the master problem and sub-problem. The master problem provides an effective lower bound for the whole problem，and its solutions that can pass the sub-problem provide an effective upper bound for the whole problem. As a result，the algorithm can continuously reduce the gap between bounds and generate a new feasible solution towards the lower bound. The real cases show that compared with the manual method，the proposed method can generate a high quality one-day train-set schedule in a short time，which reduces the total operating costs by 10.5% and the total deadhead mileage by 23%.
彭其渊,李建光,杨宇翔,等. 高速铁路建设对我国铁路运输的影响[J]. 西南交通大学学报,2016,51(3): 525-533PENG Qiyuan, LI Jianguang, YANG Yuxiang, et al. Influences of high-speed railway construction on railway transportation of China[J]. Journal of Southwest Jiaotong University, 2016, 51(3): 525-533
ABBINK E, BERG B V D, KROON L, et al. Allocation of railway rolling stock for passenger trains[J]. Transportation Science, 2004, 38(1): 33-41
[4]
ALFIERI A, GROOT R, KROON L, et al. Efficient circulation of railway rolling stock[J]. Transportation Science, 2006, 40(3): 378-391
[5]
FIOOLE P J, KROON L, MARÓTI G, et al. A rolling stock circulation model for combining and splitting of passenger trains[J]. European Journal of Operational Research, 2006, 174(2): 1281-1297
[6]
MARÓTI G, KROON L. Maintenance routing for train units:the transition model[J]. Transportation Science, 2005, 39(4): 518-525
[7]
GÁBOR M, LEO K. Maintenance routing for train units:the interchange model[J]. Computers & Operations Research, 2007, 34(4): 1121-1140
[8]
史峰,周文梁,郁宇卫,等. 客运专线动车组运用计划优化模型与算法[J]. 铁道学报,2011,33(1): 1-13SHI 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): 1-13
[9]
赵鹏,富井规雄. 基于路段交换的多基地动车组运用计划的编制算法[J]. 铁道学报,2004,26(1): 7-11ZHAO Peng, NORIO Tomii. An algorithm for multiple-bases train-set scheduling based on path-exchange[J]. Journal of the China Railway Society, 2004, 26(1): 7-11
[10]
王莹,刘军,苗建瑞. 基于列生成算法的动车组检修计划优化[J]. 中国铁道科学,2010,31(2): 115-120WANG Ying, LIU Jun, MIAO Jianrui. Column generation algorithms based optimization method for maintenance scheduling of multiple units[J]. China Railway Science, 2010, 31(2): 115-120
[11]
李建,林柏梁,耿令乾,等. 基于交路接续的动车组运用计划优化模型与算法[J]. 交通运输系统工程与信息,2015,15(5): 172-177,194LI Jian, LIN Boliang, GENG Lingqian, et al. Optimizaiton model and algorithm for motor trainset utilization scheduling based on routes connection[J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(5): 172-177,194
[12]
LI J, LIN B, WANG Z, et al. A pragmatic optimization method for motor trainset assignment and maintenance scheduling problem[J]. Discrete Dynamics in Nature & Society, 2016(3): 1-13
[13]
BORNDÖRFER R, REUTHER M, SCHLECHTE T, et al. Integrated optimization of rolling stock rotations for intercity railways[J]. Transportation Science, 2016, 50(3): 863-877
殷勇,陈锦渠,朱蔓,等. 城市轨道交通站点失效修复策略[J]. 西南交通大学学报,2020,55(4): 865-872YIN Yong, CHEN Jinqu, ZHU Man, et al. Repair strategies for failure of urban rail transit stations[J]. Journal of Southwest Jiaotong University, 2020, 55(4): 865-872
[16]
ZHONG Q, LUSBY R M, LARSEN J, et al. Rolling stock scheduling with maintenance requirements at the Chinese high-speed railway[J]. Transportation Research Part B: Methodological, 2019, 126: 24-44
