动车运用所调车作业计划优化

doi:10.3976/j.issn.1002-4026.2022.02.012

摘要/Abstract

摘要：

动车运用所的调车计划编制随着检修任务的增加而变得越来越复杂,调车计划编制的自动化对于增强动车运用所的检修能力具有重要意义。以最小化动车组检修任务完成时的时刻之和为目标,考虑动车运用所的股道占用冲突等约束构建优化模型,设计的贪婪算法结合邻域搜索的启发式算法可以对调车计划编制的自动化问题进行快速求解。最后,设计算例验证本文算法的有效性。研究发现,对于15组动车组规模的5个算例,平均Gap值为0.87%,且有3个算例直接求出了最优解;对于20组动车组规模的5个算例,邻域搜索改进的平均值为1.35%。

关键词: 动车运用所, 动车组检修, 调车作业计划, 贪婪算法, 邻域搜索

Abstract:

With increasing maintenance tasks in electric multiple unit (EMU) depots, shunting operation plans are becoming increasingly complex. The automation of shunting plan preparation is crucial for enhancing the maintenance ability of EMU depots. This study aims to minimize the total maintenance time of EMU trains and construct an optimization model that considers the occupancy conflict of the operation tracks in EMU depots. A heuristic algorithm comprising the greedy algorithm combined with neighborhood search is proposed to solve the automation of shunting plan quickly. Finally, a computational study is designed to verify the effectiveness of the proposed algorithm. Results show that for five cases with an EMU size of 15 each, the average Gap value is 0.87% and the optimal solution is directly obtained in three cases. In five cases with an EMU size of 20 each, the average value of the neighborhood search improvement is 1.35%.

Key words: electric multiple unit depots, electric multiple unit maintenance, shunting operation plan, greedy algorithm, neighborhood search

中图分类号:

U292.2

范贤,徐小明,钱程. 动车运用所调车作业计划优化[J]. 山东科学, 2022, 35(2): 96-105.

FAN Xian,XU Xiao-ming,QIAN Cheng. Optimization of shunting operation plan of electrical multiple unit depots[J]. Shandong Science, 2022, 35(2): 96-105.

图/表 8

图1

表1

参数符号及其定义"

符号	定义	符号	定义
K	入所检修的动车组集合	T_r	检修作业r需要的最小作业时间
R	待检动车组的所有检修作业集合	R_k	动车组k需要执行的检修作业集合
$t k a$	动车组k的入所时间	R_f	检修线f上的检修作业的集合
$t k d$	动车组k的出所时间	M	任意大的常数
$t r s$	到达作业线开始检修作业r的时间	$t k e$	动车组k完成所有检修作业的时刻
$t r e$	结束检修作业r离开作业线的时间	$y ij k$	动车组k的检修作业的执行顺序的0-1约束变量,如果动车组 k的检修作业j紧接着检修作业i,执行 $y ij k$ =1,否则 $y ij k$ =0
$x ij f$	动车组占用作业线的检修顺序的0-1约束变量,如果检修作业j 紧接检修作业i在作业线f上进行,则 $x ij f$ =1,否则 $x ij f$ =0

表1

图2

表2

表3

表4

表5

表6

参考文献 15

[1]	王家喜. 动车所检修作业计划优化方法研究[D]. 北京: 北京交通大学, 2018.
[2]	CAPRARA A, KROON L, MONACI M, et al. Passenger railway optimization[J]. Handbooks in Operations Research and Management Science, 2007, 14(129-187). DOI: 10.1016/S0927-0507(06)14003-7. doi: 10.1016/S0927-0507(06)14003-7
[3]	FRELING R, LENTINK R M, KROON L G, et al. Shunting of passenger train units in a railway station[J]. Transportation Science, 2005, 39(2): 261-272. DOI: 10.1287/trsc.1030.0076. doi: 10.1287/trsc.1030.0076
[4]	KROON L G, LENTINK R M, SCHRIJVER A. Shunting of passenger train units: an integrated approach[J]. Transportation Science, 2008, 42(4): 436-449. DOI: 10.1287/trsc.1080.0243. doi: 10.1287/trsc.1080.0243
[5]	HAAHR J T, LUSBY R M, WAGENAAR J C. Optimization methods for the train unit shunting problem[J]. European Journal of Operational Research, 2017, 262(3): 981-995. DOI: 10.1016/j.ejor.2017.03.068. doi: 10.1016/j.ejor.2017.03.068
[6]	LENTINK R M, FIOOLE P J, KROON L G, et al. Applying operations research techniques to planning of train shunting[M]//Planning in Intelligent Systems. Hoboken, NJ, USA: John Wiley & Sons, Inc., 2006: 415-436. DOI: 10.1002/0471781266.ch15. doi: 10.1002/0471781266.ch15
[7]	JACOBSEN P M, PISINGER D. Train shunting at a workshop area[J]. Flexible Services and Manufacturing Journal, 2011, 23(2): 156-180. DOI: 10.1007/s10696-011-9096-1. doi: 10.1007/s10696-011-9096-1
[8]	TOMII N, ZHOU L J, FUKUMURA N. An algorithm for station shunting scheduling problems combining probabilistic local search and PERT[C]// International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems.Berlin, Heidelberg:Springer, 1999(1611): 788-797.DOI; 10.1007/978-3-540-48765-4_84. doi: 10.1007/978-3-540-48765-4_84
[9]	TOMII N, ZHOU L J. Depot shunting scheduling using combined genetic algorithm and PERT [C]// Seventh International Conference on Computers in Railways: Computers in Railways VII,Bologna, Italy: WIT Press, 2000: 437-446.
[10]	王忠凯, 史天运, 张惟皎, 等. 动车运用所调车作业计划优化编制模型与算法[J]. 铁道学报, 2013, 35(8): 1-9. DOI: 10.3969/j.issn.1001-8360.2013.08.001. doi: 10.3969/j.issn.1001-8360.2013.08.001
[11]	郭小乐, 宋瑞, 黎浩东, 等. 动车运用所调车作业计划编制优化[J]. 中国铁道科学, 2016, 37(1): 117-123. DOI: 10.3969/j.issn.1001-4632.2016.01.16. doi: 10.3969/j.issn.1001-4632.2016.01.16
[12]	童佳楠, 聂磊, 贺振欢. 基于遗传算法的动车运用所一级检修作业计划优化[J]. 铁道运输与经济, 2016, 38(8): 59-65. DOI: 10.16668/j.cnki.issn.1003-1421.2016.08.11. doi: 10.16668/j.cnki.issn.1003-1421.2016.08.11
[13]	王家喜, 林柏梁, 王忠凯, 等. 动车所调车作业计划优化模型及求解算法[J]. 交通运输系统工程与信息, 2016, 16(6): 122-127. DOI: 10.16097/j.cnki.1009-6744.2016.06.019. doi: 10.16097/j.cnki.1009-6744.2016.06.019
[14]	殷迪, 唐秋华, 张子凯, 等. 动车所调车作业计划优化模型与算法[J]. 武汉科技大学学报(自然科学版), 2020, 43(5): 370-376. DOI: 10.3969/j.issn.1674-3644.2020.05.008. doi: 10.3969/j.issn.1674-3644.2020.05.008
[15]	韩宝明, 赵鹏, 李得伟. 动车所一级修灵活作业顺序模型与算法[J]. 北京交通大学学报, 2021, 45(1): 8-15. DOI: 10.11860/j.issn.1673-0291.20200037. doi: 10.11860/j.issn.1673-0291.20200037

动车组编号	入所时刻	出所时刻	动车组编号	入所时刻	出所时刻
EMU1	0	150	EMU9	310	520
EMU2	10	245	EMU10	330	650
EMU3	30	330	EMU11	360	710
EMU4	70	270	EMU12	380	800
EMU5	110	290	EMU13	410	700
EMU6	180	450	EMU14	430	900
EMU7	220	460	EMU15	500	940
EMU8	270	480

动车组编号	检修流程及股道占用情况
EMU1	W1(0~30);R1(35~125);S1(130~150)
EMU2	W2(10~40);R2(45~135);S2(140~245)
EMU3	R3(30~120);W1(125~155);S3(160~330)
EMU4	W1(70~100);R4(105~195);S4(200~270)
EMU5	W2(110~140);R3(145~235);S5(240~290)
EMU6	W1(180~210);R1(215~305);S1(310~450)
EMU7	W1(220~250);R2(255~345);S2(350~460)
EMU8	W1(270~300);R3(305~395);S3(400~480)
EMU9	W1(310~340);R1(345~435);S4(440~520)
EMU10	W2(330~360);R2(365~455);S1(460~650)
EMU11	W1(360~390);R4(395~485);S2(490~710)
EMU12	W2(380~410);R3(415~505);S3(510~800)
EMU13	W1(410~440);R1(445~535);S4(540~700)
EMU14	W2(430~460);R2(465~555);S5(560~900)
EMU15	W1(500~530);R3(535~625);S6(630~940)

动车组编号	入所时刻	出所时刻	动车组编号	入所时刻	出所时刻
EMU1	110	290	EMU9	375	870
EMU2	165	420	EMU10	395	900
EMU3	180	450	EMU11	415	780
EMU4	220	460	EMU12	435	920
EMU5	270	480	EMU13	450	850
EMU6	305	520	EMU14	475	890
EMU7	330	650	EMU15	500	750
EMU8	350	670

动车组编号	初始解	邻域搜索优化
EMU1	W1(110~140);R1(145~235);S1(240~290)	W1(110~140);R1(145~235);S1(240~290)
EMU2	W1(165~195);R2(200~290);S1(295~420)	W1(165~195);R2(200~290);S1(295~420)
EMU3	W2(180~210);R3(215~305);S2(310~450)	W2(180~210);R3(215~305);S1(310~450)
EMU4	W1(220~250);R1(255~345);S3(350~460)	W1(220~250);R1(255~345);S2(350~460)
EMU5	W1(270~300);R2(305~395);S4(400~480)	W1(270~300);R2(305~395);S3(400~480)
EMU6	W1(305~335);R3(340~430);S1(435~520)	R3(305~395);W2(400~430);S4(435~520)
EMU7	W2(330~360);R1(365~455);S2(460~650)	W1(330~360);R1(365~455);S1(460~650)
EMU8	W1(350~380);R4(385~475);S3(480~670)	W2(350~380);R4(385~475);S2(480~670)
EMU9	W2(375~405);R2(410~500);S4(505~870)	W1(375~405);R3(410~500);S3(505~870)
EMU10	W1(395~425);S5(430~440) ;R3(445~535);S1(540~900)	S4(395~410);R2(415~505);W1(510~540);S4(545~900)
EMU11	W2(415~445);S5(450~460); R1(465~555);S5(560~780)	W1(415~445);S5(450~460);R1(465~555);S5(560~780)
EMU12	W1(435~465);S5(470~480); R4(485~575);S6(580~920)	W2(435~465);S5(470~485);R4(490~580);S6(585~920)
EMU13	S6(450~470);W1(475~505);R2(510~600); S7(605~850)	W1(450~480); S6(485~510);R2 (515~605);S7(610~850)
EMU14	W2(475~510);S5(515~540);R3(545~635);S8(640~890)	W2(475~515);R3(520~610);S8(615~890)
EMU15	S6(500~515);W1(520~550);S6(555~560); R1(565~655);S2(660~750)	S5(500~525);W2(530~560);R3(565~655); S1(660~750)

算例	解的下界(L_B)	贪婪算法的初始解(S)	邻域搜索后的解(N_S)	Gap值/%	IMP值/%
M1	6 730	6 730	6 730	0.00	0.00
M2	6 401	6 474	6 474	1.13	0.00
M3	6 660	6 660	6 660	0.00	0.00
M4	5 661	5 661	5 661	0.00	0.00
M5	5 999	6 197	6 146	3.20	0.82
平均				0.87	0.16
L1	8 310	8 944	8 806	5.97	1.54
L2	8 597	8 923	8 885	3.35	0.43
L3	8 893	9 287	9 287	4.43	0.00
L4	7 886	8 387	8 347	5.85	0.48
L5	7 078	8 175	7 822	10.51	4.32
平均				6.02	1.35