0 引言
近年来，动车的快速发展带来了动车生产交付的新问题。动车生产中，列车车厢生产受制造工艺影响，产出顺序与交车顺序并不相同。此时需要把列车车厢暂存到交车线，当一列车的车厢全部完成时，调出全部车厢组成列车交付。由于交车线数量有限，而积压的订单和列车车厢越来越多，调出目标车厢时需对大量车厢进行连锁调整，造成了额外成本并严重影响组车和联调效率。如何优化调度，缩短调车过程中的车厢调运距离和交车时间，是本问题的研究目标。
组车优化调度问题与火车车厢运行编组调度、车辆调度等问题相似。王典等[1]以车辆在编组站的总停留时间和总额外中转时间最小为目标，构建了多目标混合整数线性规划模型；肖杰等[2]采用遗传算法建立了单组列车编组优化模型；郭瑞等[3]设计了优先规则和推理算法；毕明凯等[4]以运输费用最小为目标函数，构建了编组去向和调车线数量协调优化模型；赵军等[5]针对双向编组站配流问题，构建了大规模混合整数线性规划模型；张其亮等[6]针对复线列车调度问题，提出了一种混合粒子群优化算法进行求解。上述研究都取得了很好效果，但研究问题与目标函数都与本文不同。
车辆调度问题包括车辆使用成本最小的调度问题[7]、堆场中的车辆调度问题[8]和AGV的调度问题[9]，这些车辆调度属于小规模的车辆调度，可以通过智能算法找到一个比较优秀的结果。对于大规模车辆调度问题，徐奇等[10]在港口的拖轮调度问题中，利用启发式规则和模拟退火算法相结合的算法进行优化。对于集装箱码头调度问题，梁亮等[11]建立了整数规划模型，并利用二阶段启发式算法进行调度优化；曾庆成等[12]提出了神经网络和模拟退火算法的混合优化算法；李斌等[13]集成服务系统的理念，建立了一个新的调度体系。针对散货码头中的车辆调度问题，VAN VIANEN 等[14]用调度规则代替调度算法，缩短了调度所需的时间；鹿特丹港的调度仿真模型[15]中，使用启发式的算法结果与最优解偏差为10%，但运算时间仅为求得最优解的0.01%。然而，上述车辆调度的研究都没有考虑车辆的编组和编组导致的联动调车问题，因此也不同于本文研究问题。
上述研究成果无法直接用到动车组车调度中。对于不追求最优解的工程问题，启发式方法往往可以获得很好的实用效果。为了探索适合该问题的启发式调度方法，本文基于离散事件仿真技术建立组车调度仿真模型，并采用仿真调度的方法进行研究。
1 问题描述
我国的动车生产中，由于工艺等条件的限制，生产顺序并非是列车的出厂顺序，所以车厢顺序需要在调车线进行调整。该调整过程可描述如下：假设轨道中的车厢服从先入先出原则，第t个存车轨道为Qt，第i辆列车的第j节车厢表示为Ci,j，则图1所示的存车轨道Q1、Q2的车厢储存状态可表示为(C1,7,C2,2,C1,6,C1,3)和(C1,1,C2,5,C2,8,C2,4)。
图1 交车线示意图
Fig.1 Delivery line diagram
当有新车厢进入存车轨道时，选择有存储空间的轨道，并将其存储在第一个位置。在上述存储状态的基础上，通过中间轨道调换存车轨道和存储位置，但每条轨道需满足先入先出的原则。例如图1中的C1,3离开Q1之后，C1,6才能离开。离开的车厢再进入队列时和新车厢进入存车轨道方式相同，只能排在C1,7或C1,1之前。最终通过上述方式在某一存车轨道按顺序组合目标列车的全部车厢，即实现组车。假定QD为出口轨道，对应的列车i有n节车厢，其最终组车状态的车厢顺序为(Ci,1, Ci,2, …, Ci,n)。
以调出车厢Ci,j为例来说明，组车过程需要确定QD中按顺序缺失的车厢Ci,j，并将车厢Ci,j从对应的Qt调入QD。调出车厢Ci,j需要进行以下操作：
(1)将存车轨道Qt中阻挡车厢Ci,j到达QD的多个车厢顺序移出轨道Qt。
(2)移出的车厢可进入用于调车的预留轨道Qbuffer。
(3)移出目标车厢Ci,j，j←j+1。
(4)从预留轨道Qbuffer中移出暂存车厢，重新选择进入新的存车轨道。
重复上述过程，直到Ci,n均按照顺序移入QD。上述过程中，只有步骤(4)把暂存车厢重新移入存车轨道时存在优化空间。重新进入轨道会造成新的存车顺序，对后续的调车带来不同程度的影响。在调车过程中，每次移动车厢都会耗费一定能源，耗费能源与车厢行程成正比，记为wi,j，则该问题的目标函数为min∑wi,j。
此外，由于生产存在一定的不确定性，因此可认为新车厢到达顺序随机，新车厢到达时通过分配车厢存储轨道，实现未来调车过程的优化。调车时可通过步骤(4)重新分配车厢存储轨道，来优化后续调车的行驶距离。为了节约存储空间，调车线中只要任意列车的全部车厢到齐，即可实施上述组车过程。上述问题具有高动态性和随机性，难以通过建立数学模型的方法求解，所以本文利用启发式的方法寻求存储轨道分配规则，并针对企业实例建立仿真模型。
2 仿真模型构建
2.1 模型逻辑
某动车企业列调车间共6条轨道，如图2所示。车厢由入口轨道进入交车线，组车成功后整列列车由出口轨道驶出存车线。仿真模型中轨道的长度按企业具体情形建立，结合车厢长度每条轨道的最大容量为8节车厢。
图2 轨道布置
Fig.2 Track layout
车厢进入存车轨道时，根据相应的规则，通过中间轨道进入相应的存车轨道，考虑到车厢调车的问题，预留1个轨道进行调车，这里将轨道6作为暂存轨道Qbuffer。
仿真过程首先随机产生车厢，车厢根据相应的规则进入存车轨道，当某列列车对应的全部车厢都进入存车轨道时，触发组车事件。组车时，根据列车车厢原始顺序对车厢进行调整并按次序组车；调车时，将目标车厢前方的车厢依次移入轨道6，再将目标车厢移出。图3、图4分别为仿真逻辑流程图和组车流程图。
图3 仿真逻辑流程图
Fig.3 Simulation flow chart
图4 调车流程
Fig.4 Marshalling flow chart
2.2 实验设计
根据订单的批量设计3组(小批量订单、中批量订单、大批量订单)实验。模型利用3种运算的方案：穷举算法、遗传算法(genetic algorithm, GA)和启发式规则进行仿真对比。
穷举算法适用于小批量订单情形。新车厢进入存车线时依次枚举所有轨道，并仿真后续的组车。
遗传算法适合中批量订单情形。随着订单的增多，穷举算法的计算量难以承受，采用遗传算法选择车厢与存车线的对应关系。
启发式规则适合大批量订单情形。随着订单进一步增多，遗传算法收敛速度得不到保证，此时完全采用启发式规则选择存车线。
企业实际生产中往往是随机选择存车线，因此另外定义一种随机选择存车线的规则，用于实验的数据对比。随机规则在车厢进行入库操作时产生一个随机数，根据随机数选择轨道，如果该轨道的容量已满，则重新确定随机轨道。
3 启发式规则设计
穷举算法和遗传算法在此不再赘述，仅说明采用的启发式的调车规则(heuristic marshalling rule, HMR)。
HMR按顺序分为5个步骤，每个步骤对应一条选择规则。当车厢Ci,j到达交车线时，对5条规则依次进行判定，如当前规则可找到Ci,j的存放轨道，则HMR结束；否则进入下一条规则，直到找到Ci,j的存放轨道结束。
HMR具体规则如下：
(1)规则1。遍历当前所有具有空闲位置的轨道，在其排在最后的车厢中寻找k<j的同列车车厢Ci,k，如有多个Ci,k，则选择k最大的车厢所在轨道；如不存在Ci,k，则进入规则2。如图5所示，因为Q2中的最后车厢是C1,1，所以到达车厢为C1,j(j=2，3，4，5)时，可进入Q2。
图5 规则1示例
Fig.5 Example of rule 1
(2)规则2。寻找没有任何车厢的空轨道，如果有多条空轨道，则优先进入靠近暂存轨道Qbuffer的轨道。如没有空轨道，则进入规则3。
(3)规则3。遍历当前所有具有空闲位置的轨道，在有空闲位置的轨道最后的车厢中寻找同列车车厢Ci,j+1，如有存在Ci,j+1，则选择其所在轨道；如不存在，则进入规则4。假定车厢C1,3到达时， Q1上的最后车厢为C1,4，刚好是C1,3的后一节车厢，那么应该进入Q1，如图6所示。
图6 规则3示例
Fig.6 Example of rule 3
(4)规则4。遍历当前所有具有空闲位置的轨道，寻找可与Ci,j组车且满足k<j的所有车厢Ci,k，并记录Ci,k所在轨道的位置。将该位置与所在轨道排最前的空闲位置的距离定义为所在轨道的优劣值，按优劣值由小到大排序，优先选择优劣值小的轨道。如存在多条轨道优劣值相同的情形时，则进入规则5。如图7所示，如果到达车厢为C1,3，那么计算两条轨道的优劣值。在C1,3前方的车厢有C1,1、C1,2，分别位于Q1和Q2。Q1中C1,1之后的车厢有1节，所以Q1的优劣值为1。同理，Q2的优劣值为3，此时按规则4应该选择Q1。
图7 规则4示例
Fig.7 Example of rule 4
(5)规则5。针对满足规则4优劣值条件的多条轨道，因为靠近暂存轨道Qbuffer的轨道调度所需的距离较短，所以靠近暂存轨道Qbuffer的轨道优先。
上述HMR的5条规则的设计思路是：规则1尽量按照编组顺序存车，以最小化组车时所需的调车数为目标，形成轨道的车厢顺序。规则2的思路是，当无法按照编组顺序存车时，将车厢存入空轨道，目的同样是尽量减少调车。如果已经没有空轨道，那么为了保证最少的调车，设计了基于贪婪算法的规则4和规则5，保证每一步都是当前情况下的局部最优。由于贪婪算法专注于局部最优，可能会导致整体优化效果较差，因此设计了规则3对贪婪算法进行修正，优先保证相邻车厢的相邻存放。
定义没有规则3即只有规则1、规则2、规则4、规则5的调车方案为贪婪规则(greedy marshalling rule, GMR)。通过实验对比HMR和GMR的优劣性，利用几组实验和随机算法、遗传算法、穷举算法进行对比，证明HMR能够在短时间求得较为优秀的解。
4 实验分析
根据某动车生产企业的实际情形，轨道长度为130 m，车厢长度为16 m，每条轨道最多容纳8节车厢。每种列车也由8节车厢组成，可在一条轨道内完成组车。针对不同的订单批量设计3组实验。实验考虑了列车种类，同一种类列车的相同编号车厢可以替代使用。其中，小批量订单只针对1种列车，中批量针对2种列车，大批量针对3种列车。
4.1 小批量订单分析
小批量实验假定车间内有2条可用轨道，即Qt∈{Q1，Q2}。小批量实验的假定生产任务为1种列车，生成该种列车的10辆列车订单。每辆列车由8节车厢组成，同编号车厢可以互换。假定车厢到达交车线顺序随机，对比验证HMR和GMR的优劣。
通过一组随机数来打乱生产顺序，产生不同的生产任务，从而进行15组对照实验，增加实验结果的可信度。实验结果以平均运行距离计算，平均距离
的计算公式如下：
式中，Si为车厢i运行的距离；n为车厢数。
实验结果如图8所示，HMR和GMR明显优于随机规则的实验结果；相比于穷举算法，HMR和GMR均能够求出较优的结果；GMR的结果有时会有较大的偏差，而HMR的结果相对于GMR更稳定。GMR、HMR、随机规则与穷举算法得出的最优解如表1、表2所示。
图8 4种规则的对比(小批量)
Fig.8 Comparison of 4 rules(small batch)
表1 4种规则的比较(小批量)
Tab.1 Comparison of the 4 rules(small batch) m
穷举算法GMRHMR随机规则平均距离433535516840距离标准差461079887
表2 3种规则的比较(小批量)
Tab.2 Comparison of 3 rules(small batch) m
与最优解差值均值与最优解差值标准差结果偏差GMR102862HMR82662随机规则40669
根据小批量生产计划的实验分析结果可知，在小批量生产计划的条件下，HMR和GMR一般能得出相对较优的解，实验结果比较稳定，但在个别情况下会出现一些较大误差，且HMR的处理结果优于GMR的处理结果。
4.2 中批量订单分析
中批量实验定义车间内有3条可用轨道，即Qt∈{Q1，Q2，Q3}。本组实验需生产2种列车，每种列车均有10辆列车，每辆列车有8个车厢。因此中批量订单实验共存在(2×8×10)！=160！种情形，显然无法采用穷举算法求解，所以采用遗传算法作为参照。
如图9可知，HMR和GMR在大部分的情况下是优于其他规则的。相对于随机规则，HMR和GMR在大部分情况下能够极大缩短调度距离；HMR和GMR在大部分分情况下优于遗传算法(GA)，充分表明了启发式规则的可行性。
图9 4种规则的对比(中批量)
Fig.9 Comparison of 4 rules (middle batch)
表3证明了HMR和GMR的可行性。HMR和GMR的调度距离均值均小于随机规则的调度距离均值，但GMR的方差远大于其他2种规则的方差，表明GMR的结果稳定性较差，容易得出较大偏差的结果，HMR的结果略优于GMR的结果。
表3 4种规则的比较(中批量)
Tab.3 Comparison of 4 rules(middle batch) m
遗传算法GMRHMR随机规则平均距离9357907571051距离标准差331077876
本文遗传算法的解码过程采用离散事件仿真的方式对编码进行评价，为节约计算时间，设定最大代数为10，种群规模为20。为了弥补搜索范围过小的劣势，设计了补充实验。
补充实验采用“HMR+GA”的方式，先将HMR计算出的结果作为遗传算法的初始解，然后利用遗传算法进行运算，统计每节车厢的平均运行距离。对比两种结果的差距，差距较小则说明HMR结果与最优解差距较小，反之则说明差距较大。计算结果如图10所示。由图10可知，虽然“HMR+GA”能进一步获得比HMR结果更好的解，但仅有第4、第5次实验的优化效果能够达到10%，其他实验的结果优化效果均在5%以下，平均优化效果为2.76%，这说明HMR可以快速找到近优解。
图10 补充实验结果
Fig.10 Supplementary experiment results
4.3 大批量订单分析
对于大批量订单，穷举算法和遗传算法都很难在短时间获得较优解，因此采用 “HMR+GA”进行对比。
大批量生产计划实验包含3种列车，每种列车均有10辆列车，每辆列车有8个车厢。大批量实验定义车间内有5条可用轨道，即Qt∈{Q1，Q2，Q3，Q4，Q5}。实验结果如图11所示。由图11可以看出，HMR、GMR和HMR+GA对于随机规则在优化距离上都存在显著优势。10次实验中，HMR+GA的结果与HMR的结果完全相同，二者结果略优于GMR，但HMR+GA的计算时间平均为19 min55 s ，HMR的计算时间仅为13.7 s。这几种方案的均值方差如表4所示，HMR和GMR的实验结果明显优于随机规则的实验结果，HMR结果的稳定性相对于其他方法有明显的优势。
图11 大批量实验结果对比
Fig.11 Comparison of large batch experimental results
表4 3种规则的对比(大批量)
Tab.4 Comparison of 3 rules(large batch) m
平均距离距离标准差GMR58756HMR56541随机规则89647
5 结论
动车车厢组车过程是一个高动态和随机的过程，难以建立数学模型并求解，为此建立了离散事件仿真模型，并针对该问题设计了启发式规则。仿真实验表明，本文提出的HMR规则针对大、中、小三种批量，都能够快速找到近优解。HMR规则原理非常简单，易于实施，节约组车成本。
[1] 王典, 赵军, 彭其渊, 等. 重载铁路装车端编组站重载列车组合优化[J]. 铁道学报, 2017, 39(6): 10-19.
WANG Dian, ZHAO Jun, PENG Qiyuan, et al. Optimization of Train Combination Schemes at Marshalling Station in Loading End of Heavy Haul Railway[J]. Journal of the China Railway Society, 2017, 39(6): 10-19.
[2] 肖杰,林柏梁,王家喜,等. 技术站列车编组计划的综合优化方法 [J]. 中国铁道科学, 2016, 37(2): 128-136.
XIAO Jie, LIN Bailiang, WANG Jiaxi, et al. Comprehensive Optimization Method for Train Formation Plan of Technical Station[J]. China Railway Science, 2016, 37(2):128-136.
[3] 郭瑞,郭进,苏跃斌. 编组站配流问题中多阶段优化算法的启发式规则[J].铁道学报, 2017, 39(6): 1-9.
GUO Rui, GUO Jin, SU Yuebin. Heuristic Rules of Multistage Optimization Algorithm for Wagon-flow Alllocation in Marshaling Station[J]. Journal of the China Railway Society, 2017, 39(6): 1-9.
[4] 毕明凯, 何世伟, 李婷婷,等. 编组站编组去向与调车线数量协调优化研究[J]. 交通运输工程与信息, 2016, 16(5): 123-128.
BI Mingkai, HE Shiwei, LI Tingting, et al. Optimization of Train Blockings and Shunting Lines in a Railway Marshlling Yard[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(5): 123-128.
[5] 赵军, 彭其渊. 双向编组站配流问题整数规划模型及算法[J]. 铁道学报, 2014, 36(9): 10-19.
ZHAO Jun, PENG Qiyuan. Integer Programming Model and Algorithm for Wagon-flow Allocation Problem at Double-direction Marshalling Station[J]. Journal of The China Railway Society, 2014, 36(9): 10-19.
[6] 张其亮，陈永生. 列车调度问题模型与基于混合粒子群优化的求解算法[J]. 中国机械工程, 2013, 24(14): 1916-1922.
ZHANG Qiliang, CHEN Yongsheng. Train Scheduling Problem Model and Its Solution Based on Particle Swarm Optimization Algorithm[J]. China Mechanical Engineering, 2013,24(14):1916-1922.
[7] 许茂增, 余国印, 周翔, 等. 综合成本最小的低碳车辆调度问题及算法[J], 计算机集成制造系统, 2015, 21(7): 1906-1914.
XU Maozeng, YU Guoyin, ZHOU Xiang, et al. Low-carbon Vehicle Scheduling Problem and Algorithm with Minimum-comprehensive-cost[J]. Computer Integrated Manufacturing Systems, 2015, 21(7): 1906-1914.
[8] 张笛，钟鸣，陈龙，等. 基于改良C-W 节约算法的甩挂运输车辆调度模型[J]. 中国机械工程, 2018, 29(19): 2352-2356.
Zhang Di, ZHONG Ming, Chen Long, et al. A Vehicle Scheduling Model for Trailer Pick-up Transport Based on Modified C-W Saving Algorithm[J]. China Mechanical Engineering, 2018,29(19):2352-2356.
[9] ZHENG Huarong, NEGENBORN R R, LODEWIJKS G. Closed-loop Scheduling and Control of Waterborne AGVs for Energy-efficient Inter Terminal Transport[J]. Transportation Research Part E, 2017, 105: 261-278.
[10] 徐奇, 邵乾雯, 靳志宏. 基于混合流水作业组织的港口拖轮调度优化[J]. 系统工程理论与实践, 2014, 34(2): 485-493.
XU Qi, SHAO Qianwen, JIN Zhihong. Optimization on Tugboat Operation Scheduling Based upon the Hybrid Flout Shop Arrangement[J]. Systems Engineering-Theory & Practice, 2014, 34(2): 485-493.
[11] 梁亮, 陆志强. 集装箱码头装卸系统集成调度的建模与优化[J]. 系统工程理论与实践, 2010, 30(3): 476-483.
LIANG Liang, LU Zhiqiang. Modeling and Optimization of the Integrated Scheduling Problem of Container Handling System[J]. Systems Engineering-Theory & Practice, 2010, 30(3): 476-483.
[12] 曾庆成, 杨忠振. 集装箱码头集成调度模型与混合优化算法[J]. 系统工程学报, 2010, 25(2): 264-270.
ZENG Qingcheng, YANG Zhongzhen. Integrating Scheduling Model and Hybrid Optimization Algorithm for Container Terminals[J]. Journal of Systems Engineering, 2010, 25(2): 264-270.
[13] 李斌, 李文峰. 基于MAS的集装箱码头物流系统协同生产调度体系[J]. 计算机集成制造系统, 2011, 17(11): 2502-2513.
LI Bin, LI Wenfeng. Container Terminal Logistics Systems Collaborative Scheduling Based on Multi-agent Systems[J]. Computer Integrated Manufacturing Systems, 2011, 17(11): 2502-2513.
[14] VAN VIANEN T, OTTJES J, LODEWIJKS G. Simulation-based Determination of the Required Stockyard Size for Dry Bulk Terminals[J]. Simulation Modelling Practice and Theory, 2014, 42: 119-128.
[15] SCHROЁR H J L; CORMAN F; DUINKERKEN M B, et al. Evaluation of Inter Terminal Transport Configurations at Rotterdam Maasvlakte Using Discrete Event Simulation[C]//Proceedings of the 2014 Winter Simulation Conference. Washington D C, 2014: 1771-1782.
