动车所一级修灵活作业顺序模型与算法

韩宝明，赵 鹏，李得伟

(北京交通大学 交通运输学院，北京 100044)

从京津城际线路的开通到现在高速铁路(以下简称“高铁”)成网，我国铁路线路上运行的动车组数量不断增加，动车组检修维护的需求随之增大，检修能力已成为影响动车组车底运用的主要因素.一级修作为动车组日常维护保养的关键环节，关系着上线运行的动车组数量，其作业效率已成为业界关注的重点.

随着动车组检修效率重要性的提高，近年来对于动车组检修计划的优化研究越来越多.文献[1]提出了动车组检修计划对运用效率有重要影响.文献[2]研究了动车组运用计划和检修计划的一体化安排，并在此基础上研究了动车组检修计划的优化问题，并将该问题转换为具有额外时空限制的作业车间调度问题[3].文献[4]研究了具有固定作业流程的动车所调车作业问题，并将其转换为具有特殊过程约束的混合流水作业车间调度问题.文献[5]为动车所检修问题建立了一个多项目资源受限制的作业车间调度模型，并用改进的粒子群算法对动车组检修问题模型进行求解.文献[6-7]在文献[2-3]的基础上研究了动车所的调车作业问题，以调车总钩数最少为目标建立整数规划模型，并基于粒子群优化算法求解.文献[8]以总延误时间最小为目标，建立动车运用所调车作业计划编制优化模型，基于微进化和作业线分配算法对模型进行求解.文献[9]考虑了动车组线路的双列位特性，建立了ETT模型，分析不同类型车场中的车组分配对作业效率的影响.针对动车组调车作业优化的研究，大都基于固定的作业流程去调整作业顺序及线路安排，将动车所调车问题抽象为JSP，并采用遗传算法等启发式算法来求解.文献[10]探究了多目标FJSP的形式以及过去十年来用于解决该类问题的各种启发式算法.文献[11]在研究JSP问题时考虑了工序间相关性，采用析取图模型建模时新增加相关弧解决该问题.文献[12-13]针对多目标柔性JSP问题，提出了基于Pareto等级的自适应变异算子及精英保留策略的改进遗传算法.文献[14]研究了每个操作需要多个机器同时作业才能完成的多机器JSP问题，提出了基于析取图的分散搜索模型.目前对于动车所一级修作业的优化问题，大多集中于现有的固定顺序作业条件下如何调整车辆的先后作业顺序及线路安排进行动车调车作业优化，对于考虑动车所内作业流程顺序及动车组运用计划的研究较少.

因此，本文作者提出了一种灵活作业顺序优化模型，在给定动车组数量、清洗检修线路数量、动车组运用计划要求以及各作业持续时间等信息的前提下，以最大完工时间最小为目标，得出最优的动车组先后作业顺序及各个动车组作业流程顺序，并采用改进遗传算法完成求解.

1 问题描述及模型构建

1.1 问题描述

按照我国动车组检修规程，动车组一级修主要有清洗和检修两项作业，目前清洗作业一般采用自动化机械洗车，作业耗时较短;检修作业环节较多，作业耗时较长.各动车所为简化作业计划制定过程，通常采用固定的“清洗—检修”一级修作业顺序.固定作业顺序流程见图1.

图1 固定作业顺序流程图Fig.1 Flow chart of the fixed operation sequence

动车组进入动车所的时间往往是非均匀分布的，且动车所的洗车线数量相对较少，当动车组密集到达时，采用图1的固定作业顺序流程会导致动车组需要在洗车线前排队等待，而此时检修线路空闲，造成了检修资源的浪费.因此，为了提高效率，部分动车所采用了在固定作业顺序的基础上增加人工洗车方式.在该模式下，当动车组在需要等待才能进入洗车线进行清洗时，会跳过清洗作业环节，直接进入检修场进行检修作业. 在检修过程中，采用人工洗车的方式对这些动车组进行清洗.固定作业顺序结合人工洗车作业流程见图2.

图2 固定作业顺序结合人工洗车作业流程图Fig.2 Flow chart of the fixed operation sequence plus manual cleaning

对于任一动车组，清洗和检修这两项作业实际上是相互独立的，其先后顺序没有硬性要求.因此，本文针对一级修作业，提出了灵活作业顺序的模式，即动车组在进入动车所后，动车组可以不按照“清洗—检修”的固定作业顺序模式，而是可对清洗、检修作业进行选择，在完成一项作业后去往另一作业区进行相应作业，完成全部作业后在存车区等待运用.一级修灵活作业顺序流程见图3.

图3 一级修灵活作业顺序流程图Fig.3 Flow chart of the first-level maintenance with the flexible operation sequence

因此，动车运用所一级修作业计划的优化问题可以描述为：在给定动车组数量集合、清洗检修线路集合、动车组运用计划要求以及各作业持续时间等约束条件后，通过合理地调整优化动车组的先后作业顺序和各动车组的作业流程顺序，提高线路的利用率，减少动车组的不必要等待时间和线路空闲时间，进而提高动车所的一级修作业能力，最终得出最优的动车组作业顺序及线路安排方案，使得完成全部动车组一级修作业耗时最短.

模型涉及的集合有：N为全部动车组的集合，N={i|i=1,2,…,n}；W为清洗作业线路集合,W={j|j=1,2,…,w}；M为检修作业线路集合，M={k|k=1,2,…,m}.

为保证问题研究的可行性和科学性，本文作如下假设：

①存车场线路足够多；

②各车场为通过式车场，两端咽喉区均可进出动车组，车组进出无交叉干扰；

③因动车组本身自带动力，转场不需要调车机车，故不考虑动车组迂回径路成本.

1.2 模型构建

1)目标函数

在所有动车组完成作业的基础上，调整动车组的先后作业顺序及所内作业流程顺序，使得全部动车组完工时间最小.

Z=minttotal

(1)

2)约束条件

∀i=1,2,…,n

(2)

(3)

(4)

(5)

(6)

(7)

∀i=1,2,…,n

(8)

∀i=1,2,…,n

(9)

∀i=1,2,…，n

(10)

∀i=1,2,…，n

(11)

∀i,i′=1,2,…,n,i≠i′

∀j=1,2,…,w

(12)

∀i,i′=1,2,…,n,i≠i′

∀k=1,2,…,m

(13)

式(2)表示每个动车组完成一级修的时间.式(3)表示全部动车组完工时间要不低于每个动车组一级修的完工时间.式(4)和式(5)分别表示每个动车组只能在一条洗车线和检修线上完成作业.式(6)和式(7)分别表示共有n个动车组需完成洗车和检修作业.式(8)和式(9)表示作业持续时间及顺序的约束，即动车组需在完成一项作业后经过转场方可进行下一步作业.式(10)和式(11)表示动车组开始和结束作业的时间要满足动车组运用计划，开始作业时间要晚于当日动车组运用结束时间，结束作业时间要早于次日动车组运用开始时间.式(12)和式(13)表示同一线路上前后动车组的约束，在清洗检修过程中一条线路同时只能进行一辆动车组的线上作业.

2 求解算法

所构建模型的复杂性由3个预先设定的参数规模决定，即动车组数量、洗车线数量和修车线数量.当模型参数规模较小时，可利用枚举法进行精确求解；当规模较大时，利用现有非线性求解器难以精确求解，且目标函数形式在求解器中难表示，故拟采用启发式算法进行求解.考虑模型结构和不同启发式算法的优缺点，本文采用遗传算法进行求解.

2.1 算法说明

1)染色体编码

图4 染色体编码图Fig.4 Code pattern of chromosome

采用整数编码方式，染色体长度为2n，染色体编码图见图4.前n个基因位为修车基因段，根据总列车数及分配在每个修车线上的车数，可对应确定每条修车线上服务的列车及顺序，因此，前n个基因位为1,2,…，n的随机排列；同理，后n个基因位为洗车基因段，按照列车总数及洗车线数量，可确定分配在每条洗车线上的车数，并确定各洗车线上服务的列车及顺序，后n个基因位也是1,2,…，n的随机排列.对于同一列车的洗车与修车顺序，在解码时按照紧前工序原则确定.

2)染色体解码

在染色体解码过程中，为提高效率，对检修作业采用紧前工序原则确定检修时段，在此基础上考虑同一列车洗修作业间的相互制约，结合紧前工序原则采用插入法确定列车洗修顺序以及清洗时段.紧前工序原则是在考虑本流水线上前一工件完工时间及该工件前一工序完工时间前提下的最早允许开始时间，即避免流水线上因不必要的等待而延长最终完工时间.具体解码过程如下：

Step1 按照修车基因段，分配各修车线上修理的列车并按基因段顺序排序.

Step2 考虑列车到达时间、本修车线上前一列车完成时间等因素，按照紧前工序原则确定各列车修车时段.

Step3 按照修车基因段，分配各洗车线上清洗的列车并按基因段顺序排序.

Step4 按洗车线上顺序遍历每列车，考虑列车到达时间、本洗车线上前一列车完成时间，若该车可在其修车前清洗完成，则进行插入：先洗车后修车，否则，再考虑其完成修车的时间，先修车后洗车，以确定该列车的洗车时间.

3)目标函数值计算

按照染色体解码结果，可以得到全部列车完成所有操作的时间，即为目标值结果.在此基础上，由于列车最晚完成时间的限制，任一列车不满足此条件时，增加一个罚数到目标值中，以此避免该约束不满足的情况.

4)染色体选择

为避免算法陷入局部最优解，在染色体选择过程中，需尽可能提高染色体的多样性，在不增加种群数量的前提下，二进制锦标赛法可以做到这一点，且该方法具有较低的复杂度、易并行化处理等优点，故采用该方法进行染色体选择.具体方法如下：

Step1 从父代中随机取染色体pop1和pop2.

Step2 比较pop1和pop2的目标值，取较优者进行后续操作.

Step3 重复Step1、Step2，直至达到选择染色体的个数.

在二进制锦标赛法中，选择两个染色体中较优的一个，选出的种群有较多的较优解.同时，每个染色体都有与其他个体竞争的机会，即使较差的个体，也可能匹配到更差的个体，从而具有被选到的概率，该方法保留了轮盘赌法的优点，又不易陷入局部最优解.

5)染色体交叉及修复

为适应染色体特征，提出分段交叉的交叉规则.即两父代在交叉生成子代的过程中，两父代的修车和洗车基因段分别随机选择交叉起终点对应进行交叉.交叉可能会使染色体变为不可行解，为修复染色体，在交叉后分别检查修车和洗车基因段，找出坏损(重复)基因位，并进行随机修复(随机补充缺失基因段).染色体交叉修复过程见图5.

图5 染色体交叉修复过程Fig.5 Process of chromosome cross repair

6)染色体变异

为避免染色体的不可行，提出点位交换的变异规则，变异过程见图6.在修车或洗车基因段随机选取两基因位进行交换，以达到变异的目的，同时避免染色体在解码时成为不可行解，该方法可有效提高变异效率.

图6 染色体变异过程Fig.6 Process diagram of chromosome variation

2.2 算法框架

Step1 算法初始化：随机生成初始种群poporg，设置算法参数种群数量popmax、交叉概率Pc、变异概率Pm、最大迭代代数Itermax、初始迭代代数Iter、最优解Rbest、最优方案Sbest.

Step2 利用式(1)～式(3)计算父代种群目标函数值.

Step3 生成新种群.

Step3.1 用二进制锦标赛法随机选出两条父代染色体pop1、pop2；

Step3.2 若随机数Rand>Pc，则跳至Step3.3；否则，跳至Step3.4；

Step3.3 交叉操作，并修复染色体；

Step3.4 若随机数Rand>Pm，则跳至Step3.5；否则，跳至Step3.6；

Step3.5 进行变异操作；

Step3.6 将两染色体加入子代种群，若达到种群数量,跳至Step4；否则，跳至Step3.1.

Step4 计算子代种群目标函数值，并找到本代最优解Rbest(Iter)和本代最优方案S(Iter).

Step5 若Rbest>Rbest(Iter)，跳至Step6；否则，跳至Step7.

Step6Rbest=Rbest(Iter),Sbest=S(Iter).

Step7Iter=Iter+1，若Iter

Step8 输出最优解Rbest和最优方案Sbest.

3 实例分析

以太原动车所一级修作业为例，该动车所共有2条洗车线，6条检修线，存车场位于清洗场和检修场之间.某夜间共有19列动车组需完成一级修任务，其运用计划见表1.动车组洗车作业耗时30 min，检修作业耗时180 min，转场耗时30 min.

表1 太原动车所动车组的运用计划

按照灵活作业顺序和其他两种常见固定作业顺序模式进行模拟计算.

3.1 灵活作业顺序模式计算结果

利用改进的遗传算法在Matlab R2012b平台上进行求解，在内存为8 GB、CPU为i7-6500的笔记本电脑上运行.设置种群个数为50，最大迭代次数为200，交叉概率Pc=0.8，变异概率Pm=0.01.求解共用时4.23 s，迭代过程见图7.得到的一级修安排情况见表2，目标函数值为780 min(对应时刻为6:30)，对应线路安排甘特图见图8.

图7 最优解迭代过程Fig.7 Iteration process of the optimal solution

表2 灵活作业顺序动车组一级修安排情况

图8 灵活作业顺序模式动车组线路安排甘特图Fig.8 Gantt chart of EMU-to-track arrangement with flexible operation sequence mode

3.2 固定作业顺序计算结果

利用先到先服务、作业用时最短的贪婪算法原则进行模拟计算，可分别计算出两种固定作业顺序模式下的计算结果分别为840 min(对应时刻为7:30)和800 min(对应时刻为6:50)，对应线路安排甘特图见图9.

图9 固定作业顺序模式动车组线路安排甘特图Fig.9 Gantt chart of EMU-to-track arrangement with fixed operation sequence mode

3.3 对比分析

根据图8、图9和表2，计算3种模式下的等待时间、线路利用率和最晚完工时间，见表3.

表3 不同作业模式计算结果

由表3可得，灵活作业顺序模式下的全部车组等待时间比其他两种模式分别缩短了10、8 h.这是由于动车组到达时间不均匀，作业持续时间大于动车组到达间隔.采用固定作业顺序，动车组进行作业前，可选择的线路较少，部分动车组等待线路空闲，尤其在动车组到达时间相对密集的时间段内，等待时间会更长.采用固定作业顺序加人工洗车，部分动车组跳过了清洗等待环节，但并未减少检修等待环节，甚至由于部分车组直接到达检修线，增加了车组检修等待时间.而采用灵活作业顺序，统筹车场线路的利用，对密集到达的车组进行疏解，车组线路选择变多，从而减少了车组的等待时间.

灵活作业顺序模式最晚完工时间较另外两种模式分别提前了60、20 min.这是由于线路的统筹安排，合理利用车场资源，减少了不必要的等待时间，用更短的时间完成了全部车组的一级修作业.

整体看来，动车组检修作业耗时较长，检修线利用率较高，检修线利用效率关系着整个一级修作业的完成效率.随着动车组数量增多，需不断提高检修技术，缩短检修时间，提高作业效率.同时，灵活作业顺序模式的线路利用率较其他两种方式都有所提高，采用该模式在一定程度上提高了线路利用率.此外，若在进行检修作业过程中采用人工洗车的方式进行洗车，因部分环节需进行通电，存在一定安全隐患.

4 结论

针对动车所一级修作业问题，构建了灵活作业顺序的动车所一级修作业计划模型，利用了遗传算法进行实例验证，得出以下结论：

1)构建的模型对动车所一级修作业优化是有效的，模型将动车组作业顺序以及单个动车组的作业流程进行了优化，并将动车组检修作业计划与运用计划进行了综合考虑.

2)采用灵活作业顺序模式，较其他两种固定作业顺序模式，可以适当缩短一级修作业时间，减少动车组等待时间，加强线路利用率，提高工作效率和能力，并减少不必要的安全风险.

3)在动车组密集到达、且到达时间间隔较短时，灵活作业顺序模式的优势更加明显，对于提高一级修作业效率有重要意义.