动态配件组装模式下的动车组高级修调度方法研究

贾志凯

JIA Zhi-kai

（中国铁道科学研究院集团有限公司 电子计算技术研究所，北京 100081）

(Institute of Computing Technology, China Academy of Railway Sciences Corporation Limited, Beijing 100081，China)

0 引言

目前我国高速铁路投入运营的“和谐号”“复兴号”动车组超过 2 800 组。根据 2016 年 5 月的运行图数据，全国铁路旅客列车开行数量已经超过3 400 对/d，其中动车组列车开行数量达到 2 100 对/d。动车组的高级检修针对大型配件进行系统分解检修，是保障动车组运行安全的关键环节。为满足全路动车组高级检修的需求，分别在北京、上海、武汉、广州、沈阳、成都和西安建设高级检修基地。由于动车组的技术含量比较高，其高级检修流程长，检修标准高，维修难度相应较大。因此，科学制订动车组高级检修调度计划，有利于降低检修成本，提高动车组利用率。

针对动车组高级检修车间调度优化问题，不少专家学者进行了研究。曾强等[1]研究了传统的车间调度问题并给出了启发式求解方法。Bucker 等[2]提出柔性作业车间调度问题，并设计了求解方法。陈婧等[3]采用调度节点和调度链的建模思想，实现在模糊加工环境下实时的动态调度。谢志强等[4]通过构造析取图并应用蚁群算法求解传统的车间调度问题。王忠凯等[5-6]针对动车组高级检修车间调度问题，在动车组配件“原位配件组装”模式下，提出数学模型并设计了求解算法。综上所述，专家学者主要是对普通模式下车间调度问题和动车组高级检修车间调度问题进行研究。为此，在既有理论研究的基础上，针对动态装配模式进行问题分析，构建在动态配件组装模式下的动车组高级修调度优化模型，并提出求解方案。

图1 动车组配件组装关系图Fig.1 The relation diagram of CRH-EMU component assembling

1 动车组高级修调度概况

1.1 动车组高级修调度

动车组的高级检修是按照工艺要求，针对修程定义的检修配件进行分解、检测 (维修) 和组装工序过程，发现并修复缺陷，保障配件及其总成处于良好的工作状态。动车组调度检修过程主要因素包括工序、配件、设备。

以动车组转向架检修为例，检修包含分解、检修和组装类 3 类工序，工序之间具有前后关系约束，约束关系分为串行工序关系和并行工序关系，其中“轮对镟修”与“轮对补漆”为串行工序，检修调度时需先完成“轮对镟修”，才能进行“轮对补漆”工序；“转向架架体检修”与“轮对检修”为并行关系，可以同时进行调度。工序规程中定义了完成该工序的必须耗时，调度过程的检修时间不能少于该时间。考虑部分检修工序耗时长，因而为该工序配备多台检修设备，以加快瓶颈工序的检修[7-9]。

高级检修待检修的配件范围事先可以确定，其组装关系可以通过树形结构描述。动车组配件组装关系图如图1 所示。

从图1 可以看出，“转向架 Z1”的下级配件包括空气弹簧、轮对 L1、构架体 G1 和轮对 L2，检修调度过程需要满足配件的装配约束。针对分解类工序，只有转向架完成分解工序后，才能得到构架和轮对并进行相应的检修。针对检修类工序，不产生新的配件。针对组装类工序，存在 2 种主要的装配模式，原位配件组装模式和动态配件组装模式。原位配件组装模式是指只使用上级配件拆卸下的下级配件完成其组装的检修方式；动态配件组装模式是针对检修工序耗时长的子配件，增大其成品配件库存，在组装过程中，利用成品配件直接组装，以加快父级配件的检修速度，从而提高动车组高级检修效率，压缩检修时间的方法。

1.2 动态配件组装模式下的动车组高级修调度

假设存在轮对配件成品库存成品轮对 1、成品轮对 2，综合考虑图1 中工序过程、设备、配件装配约束和成品库存约束，考虑动态配件组装模式的检修任务拓扑图如图2 所示。

“轮对镟修”和“轮辋轮辐探伤”检修耗时较长，是整体动车组高级检修的瓶颈，当存在备用轮对部件时，无需等待原转向架 Z1 拆下的轮对 L1 和轮对 L2 完成检修，可以直接采用成品轮对 A、轮对 B与构架体 G1 装配，从而加速总成配件转向架 Z1 的组装。

2 动车组高级修调度优化模型

动态配件组装模式下的动车组高级检修车间调度问题约束条件为：①工序拓扑约束。调度过程应按工序拓扑要求，依次完成工艺过程要求全部工序，并且检修时间不应小于工序要求的最小检修耗时。②配件装配关系约束。调度过程需要按照配件结构的父子关系和数量进行分解和组装。③检修设备约束。同一台设备同一时刻只能进行一个配件的检修，并且满足设备数量要求。④成品配件库存约束。可以使用成品配件进行组装，所使用的成品配件不应超过库存数量。

动态配件组装模式下动车组高级修调度的优化目标为提前总成待检修配件的检修完工时间，可以将其描述为

式中：M 为提前总成待检修配件的检修完工时间；c 为动车组需要检修的配件，c 的属性包括 uc，Dc和Ac，其中 uc为 c 的上级配件，Dc为 c 的下级配件集合，集合 Ac为 c 的备用配件集合；E 为检修后的完工配件集合；j 为动车组检修工序的序号；UE为完工配件的最后一道检修工序；s 为可选检修设备；Sjc为配件 c 的检修工序 j 可选检修设备集合；为决策变量，表示配件 c 在设备 s 上执行工序 j 的结束时间；xcjs为决策变量，表示配件 c 在设备 s 上执行工序 j 的情况，当配件 c 在设备 s 上执行工序 j 时，xcjs为 1，否则为 0。

当 xcjs= 1 时，配件的检修时间应大于工序最小检修耗时的约束，其公式可以表示为

图2 考虑动态配件组装模式的检修任务拓扑图Fig.2 The topological graph of the overhauling tasks under the dynamically assembling mode

式中：为配件 c 在设备 s 上执行工序 j 时的开始时间；tcj为配件 c 在设备 s 上执行工序 j 的必须检修耗时；C 为动车组需要检修的全部配件集合；jc为配件 c 的检修工序；Jc为配件 c 的检修工序集合；Sj为工序 j 的可选检修设备集合。

将配件的检修工序只在一个设备上完成，可以将其公式描述为

将成品库存配件使用约束可以表示为

式中：zd为决策变量，表示是否使用配件 c 的备用配件进行其上级配件的装配，zd为 1 时表示使用其备用配件装配其上级配件，否则为 0；NAc为 Ac中配件数量。

配件在同一个设备上检修的先后次序变量与设备选择变量关系约束可以描述为

式中：d 为不同于 c 的动车组需要检修的配件，属于集合 C；xdjs为决策变量，表示配件 d 在设备 s 上执行工序 j 的情况，当配件 d 在设备 s 上执行工序 j 时，xdjs为 1，否则为 0。yscd为决策变量，表示检修配件之间执行工序的次序，当配件 c 在设备 s 上执行工序 j 先于配件 d 在设备 s 上执行工序 j 时， yscd为 1，否则为 0；ysdc为决策变量，表示检修配件之间执行工序的次序，当配件 d 在设备 s 上执行工序 j 先于配件 c 在设备 s 上执行工序 j时，ysdc为 1，否则为 0。

对于拆卸类工序和检修类工序，将工序拓扑和配件装配关系组合约束可以描述为

∀jc∈ Jc－K，c ∈ C，g(jc) ∈ G(jc)，r(jc) ∈ R(jc) ⑹式中：K 为全部组装类工序集合，在配件集合、配件的装配关系、检修工序集合和检修工序拓扑关系已知的前提下，检修任务之间的拓扑关系是已知的，定义以下变量描述工序拓扑和配件拓扑。G(jc) 表示 jc 的全部前驱工序检修的检修配件集合；g(jc) 表示 G(jc) 中配件；r(jc) 表示 jc 的某个前驱工序；R(jc) 表示 jc 的全部前驱工序集合；st为的一部分；se为 xg(jc)r(jc)的决策变量，表示配件 g(jc) 在设备 s 上执行工序 r(jc) 的情况，当配件g(jc) 在设备 s 上执行工序 r(jc) 时，xg(jc)r(jc)为 1，否则为 0；tg(jc)r(jc)为决策变量，表示配件 g(jc) 在设备 s 上执行工序 r(jc) 的结束时间。

当决策变量 zg(jc)= 0 时，对于组装类工序，如果不采用备用配件组装，则工序拓扑和配件装配关系组合约束可以描述为

当 zg(jc)= 1 时，对于组装类工序，如果采用备用配件组装，则工序拓扑和配件装配关系组合约束可以描述为

式中：fg(jc)为某道分解工序，该工序针对的配件是ug(jc)工序完成后得到配件 g(jc)；xug(jc)fg(jc)为决策变量，表示配件 ug(jc)在设备 s 上执行工序 fg(jc)的情况，当配件 ug(jc)在设备 s 上执行工序 fg(jc)时，xug(jc)fg(jc)为 1，否则为 0为决策变量，表示配件 ug(jc)在设备 s 上执行工序 fg(jc)的结束时间。

3 动车组高级修调度优化模型求解算法

3.1 调度拓扑图构造算法

算法的输入是工序集合，配件装配结构，配件备用集合[10]。输出为调度拓扑图 G = (V，A)，其中V 为全部可能的检修任务节点的集合，A 为任务之间的有向弧集合，调度拓扑图构造算法步骤如下。

（1）设置零号节点，作为任务图的开始。

（2）遍历工序集合。根据工序关系，从无前驱节点的工序开始。

（3）根据工序性质和检修的配件类型，在检修配件集合中查找该类型的全部配件。当工序为检测(检修) 类工序，则配件经过工序检修后的配件类型不发生改变；当工序为分解类工序，则配件经分解后，产生多个子配件；当工序为组装类工序，则多个子配件组装后，得到上一级配件。

（4）构造调度节点={工序，配件}，将其加入V 集合。

（5）根据工序和设备的对应关系，检索设备集合，扩展调度节点为{工序，配件，设备}，并设置可以多个设备检修的节点之间为互斥关系。

（6）根据工序性质，设置调度节点的拓扑关系，将其加入 A 集合。

（7）如果工序为组装类工序，则判断子配件的备用配件集合为组装调度节点设置备用配件的工序拓扑链路，该链路可以替代子配件的全部检修工序节点序列。

（8）根据工序拓扑，查询当前工序的后续工序集合，并采用深度遍历方式进行递归构建过程，如果工序集合不为空，则返回步骤（3），否则转步骤（9）。

（9）目前已构造不考虑成品库存配件条件下的调度任务拓扑图，以此为基础，再次遍历拓扑图，转步骤（10）。

（10）取当前节点，如果节点非空，则转步骤（11），否则转步骤（15）。

（11）判断当前节点的工序需要检修的配件类型，根据该类型在成品库存配件中查找可以替代的配件，如果存在成品库存配件，则转步骤（12），否则转步骤（14）。

（12）构造替代节点 = {成品库存配件 1}，{成品库存配件 2}，...，{成品库存配件 n}，将其加入节点 A 集合，转步骤（13）。

（13）构造替代节点的前驱和后继关系，基于替代节点是可以替代待检修配件的全部检修工序链这一事实，在已构造的任务拓扑图中查找待检修配件的最后一道检修工序节点，令当前节点为开始，令查找到的最后一道检修工序节点为结束，取整个调度任务拓扑图的子图，令替代节点的前驱后继关系与该子图相同，将关系加入集合 V。

（14）取当前节点的后继节点集合，进入循环递推过程，如果该集合为空，则递推过程结束，转步骤（15），否则转步骤（11）。

（15）算法结束。

3.2 蚁群迭代优化算法

蚁群迭代优化算法输入为调度拓扑图和人工蚂蚁集合，结果为动车组高级检修调度方案。蚁群迭代优化算法步骤如下。

（1）初始化蚁群算法基本参数。

（2）输入拓扑图。

（3）开始蚁群循环迭代，设置当前的迭代变量为 iret。

（4）求解全部蚂蚁的解，每个蚂蚁 ant 的求解过程为：①随机选择一个初始调度节点 vi，将其加入调度序列；②根据 G 中关系集，获取调度节点vi后续候选项集合 allowk；③根据状态转移规则选择下一个调度节点 vnew，将该节点加入已访问集合，并将其加入调度序列最后。④设置调度节点vnew的互斥调度节点为已访问状态；⑤如果完成了全部必须候选项的遍历，结束蚂蚁 ant 的求解，得到该蚂蚁 ant 的调度序列。如果存在未得到调度序列的蚂蚁，则继续迭代，否则转步骤（5）。

（5）根据目标函数评价蚂蚁 ant 的解。

（6）根据蚁群算法的信息素更新规则，调整信息素。

（7）如果迭代为结束，则转步骤（8），否则转步骤（3）。

（8）将迭代求解的优化调度序列转换为动车组高级检修车间调度计划。

（9）算法结束。

4 仿真算例

以动车组 CRH2 系的三级检修为仿真算例，对调度拓扑图构造算法和蚁群迭代优化算法进行验算。限于篇幅和便于描述，算例将三级检修工序简化，算例中涉及的工序及检修设备情况如表1 所示。

待配件集合包括 16 个转向架及其下级配件，转向架命名为 Z1，Z2，…，Z16，其下级构架体命名为 G1，G2，…，G16；轮对命名为 L1，L2，…，L32，其中 L1，L2 为转向架 Z1 的下级配件。成品库存配件包括 5 条轮对，用 B1，B2，…，B5 表示。采用检修任务调度拓扑图生成算法，得到转向架 Z1 的检修任务拓扑。

仿真算例的运行硬件处理器平台为 Intel(R)Core(TM) i7-5500@2.5GHz，操作系统平台为windows10。蚁群算法的参数为：信息素影响因子为 1.8，启发信息影响为 3.6，信息素初始值为350，信息素挥发因子为 0.5，迭代次数为 300，蚂蚁数目为 50。蚁群优化迭代过程如图3 所示，前期蚁群搜索空间较大，以避免算法进入局部极小。每次仿真求解的计算时间为 3 min 左右。

通过计算得到的调度方案为：最后一道工序的检修完成时间分别为“Z1(63)，Z2(59)，Z3(55)，Z4(51)，Z5(23)，Z6(67)，Z7(47)，Z8(43)，Z9(39)，Z10(35)，Z11(31)，Z12(27)，Z13(73)，Z14(71)，Z15(45)，Z16(43)”，其中“Z1(20)”表示“转向架 Z1”在第 20 个时间节开始进行“车体与转向架连接”，并在 2 个时间节后完工。成品库存轮对 B1，B2，...，B5 分别替代原转向架拆卸轮对 L25， L32，L31， L30，L29 进行转向架 Z13，Z15，Z14的组装，转向架 Z1，Z2，…，Z16 完成检修后，动车组的三级检修亦即完成。被替换下的轮对 L25， L32，L31， L30，L29 可以在动车组高级检修完工后继续进行相应工序链的检修，并与其他动车组进行周转。

通过仿真算例表明，构建的模型和设计的算法能够使动车组高级检修在动态组装模式下采用成品配件替代原位配件进行组装，压缩高级检修的瓶颈检修工序链，达到提高动车组高级检修车间检修能力的目标。

表1 工序及检修设备情况Tab.1 The process and maintenance equipment

图3 蚁群优化迭代过程Fig.3 The ant colony optimization process

5 结束语

随着动车组配属量的不断增加，高级检修压力日益加大。在既有研究的基础上，对广泛采用动车组高级检修动态配件组装的检修模式提出优化求解方案，进而最大化利用备件进行动态组装模式，有效压缩高级检修的瓶颈检修工序链，充分利用目前有限的高级检修资源，提高各检修基地的检修效率，减少动车组在高级检修基地的滞留时间。动车组在实际的高级检修调度中，由于设备故障或配件库存变化等原因导致的二次调整问题，后续还需进一步研究。

[1] 曾 强. 离散制造企业批量生产车间调度智能优化研究[D].重庆：重庆大学，2010.

[2] BRUCKER P，SCHLIE R. Job-Shop Scheduling with Multipurpose Machines[J]. Computing，1990，45(4)：369-375.

[3] 陈 婧，张树有. 基于关联调度模型的模糊环境下车间动态调度[J]. 浙江大学学报，2011，45(2)：240-246.

[4] 谢志强，杨 静，周 勇，等. 基于工序集的动态关键路径多产品制造调度算法[J]. 计算机学报，2011，34(2)：406-412.XIE Zhi-qiang，YANG Jing，ZHOU Yong，et al. Dynamic Critical Paths Multi-Product Manufacturing Scheduling Algorithm based on Operation Set[J]. Chinese Journal of Computers，2011，34(2)：406-412.

[5] 王忠凯. 动车组运用检修计划优化方法研究[D]. 北京：中国铁道科学研究院，2012.

[6] 王忠凯，史天运，林博梁，等. 动车组高级检修车间调度

(  )(  )问题的优化模型与算法[J]. 中国铁道科学，2016，37(6)：82-89.WANG Zhong-kai，SHI Tian-yun，LIN Bo-liang，et al. Optimization Model and Algorithm for Overhaul Job Shop Scheduling of Electric Multiple Unit[J]. China Railway Science，2016，37(6)：82-89.

[7] 赵忠生. 济南铁路局动车组检修设施布局规划研究[J]. 铁道运输与经济，2017，39(4)：1-6.ZHAO Zhong-sheng. Study on Layout Planning of EMU Maintenance Facilities in Ji’nan Railway Administration[J].Railway Transport and Economy，2017，39(4)：1-6.

[8] 李 莉，王克强. 基于改进型蚁群算法的 MFJSSP 研究[J].计算机应用研究，2011，28(5)：1641-1643.LI Li，WANG Ke-qiang. Research on MFJSSP based on Improved Ant Colony Algorithm[J]. Application Research of Computers，2011，28(5)：1641-1643.

[9] 李兢尧，孙树栋，黄 媛. 基于自适应参数混合蚁群算法的双资源约束作业车间调度[J]. 西北工业大学学报，2011，29(1)：54-61.LI Jing-yao，SUN Shu-dong，HUANG Yuan. Solving Dual Resource Constrained Job-Shop Scheduling Problem(DRCJSP) based on Hybrid Ant Colony Algorithm with Self-Adaptive Parameters[J]. Journal of Northwestern Polytechnical University，2011，29(1)：54-61.

[10] 张文斌. 铁路行包运输网络拓扑结构分析[J]. 铁道货运，2016，34(1)：46-49，53.ZHANG Wen-bin. Analysis on Network Topology of Railway Luggage Transportation[J]. Railway Freight Transport，2016，34(1)：46-49，53.