基于改进果蝇算法的地铁列车运用计划编制研究

Scheduling of Train Operation Plans for Subway Based on Improved Drosophila Algorithm

摘要

针对地铁列车运用计划编制问题，基于改进果蝇算法开发了一种地铁双车辆段列车运用计划编制模型，使列车在规定时间内能完成检修规定里程数，前往不同车辆段完成对应检修任务。在满足列车检修周期内行驶路程要求、列车均衡运用的基础上，将双车辆段的所有列车与车次任务综合规划；根据列车与车次的匹配关系，将列车运用计划编制问题转化为柔性作业车间调度问题；以列车-车次匹配成本最小为优化目标建立列车运用计划编制模型，并以国内某地铁列车运用计划为算例验证模型的有效性和可行性；就人工方案编排的不合理的检修日期，提出一种自动检修日期更新修改方案。实验结果表明：所有列车均能按时完成检修要求的行驶路程，抵达规定车辆段进行检修，实现列车均衡运用；通过对不合理的检修日期（来自人工方案）进行修改，使列车检修日期平均提前14 d，从而提高了列车检修资源的利用率。

Abstract

Aiming at the scheduling of train operation plans for the subway, this paper develops a scheduling model of the double depot based on the improved drosophila algorithm, which can make the train complete the required maintenance mileage within a specified time and conduct the corresponding maintenance tasks at different depots. Based on meeting the mileage requirements of train maintenance cycles and balanced train operation, all trains and schedules are comprehensively planned. According to the matching relationship between trains and schedules, the scheduling problem of train operation plans is transformed into a flexible operation scheduling problem. The optimization goal is to minimize the matching cost of trains and schedules. Meanwhile, the effectiveness and feasibility of the built scheduling model of train operation are verified by employing the train operation schedules of a domestic subway. An automatic maintenance schedule is proposed to modify the unreasonable maintenance dates scheduled by humans. Experimental results show that all trains can complete the required maintenance mileage and arrive at specified depots for maintenance on time, achieving balanced utilization. Additionally, by modifying unreasonable maintenance dates proposed by humans, the train maintenance dates are advanced by 14 days, which improves the utilization of train maintenance resources.

Graphical abstract

关键词

地铁列车 / 城市轨道交通 / 列车运用计划编制 / 改进果蝇算法 / 柔性作业车间调度问题

Key words

Subway Train / Urban Rail Transit / Scheduling of Train Operation Plan / Improved Drosophila Algorithm / Flexible Operation Scheduling Problem

0　引言

列车运用计划的编制是地铁车辆段的重要组成部分，列车的合理运用与使用效率是影响列车检修频率与检修安排的关键。列车使用频繁容易造成列车检修不及时，出现安全隐患；列车使用次数过少，则容易造成资源浪费。因此，列车运用计划编制问题对地铁车辆运营的经济效益和服务质量具有重要意义。赵鹏等^[1-3]将动车组运用问题视为商旅问题，分别考虑了单基地多车站与多基地多车站2种情况，以列车运行图安排与检修条件为约束，建立动车组运用计划编制模型进行求解；李建等^[4]基于接续网络，以动车组接续时间总和最小化和动车组检修前累计运行里程最大化为优化目标，以检修周期与检修前累计里程为主要约束，构建了动车组运用计划编制模型；徐安雄等^[5]在编制列车运用计划时，考虑了列车的检修任务对列车次日发车安排的影响，将车次与列车的匹配问题视为指派问题，将任务与列车的总指派费用最小当作目标函数，采用启发式算法进行求解。上述文献^[1-5]在编制列车运用计划时，考虑了列车检修需求与检修周期等约束对列车运用计划编制的影响，但未考虑列车均衡运用对列车运用计划编制的影响。若列车运用不均衡，同一检修周期内走行里程数大的列车安全性会降低，而走行里程数少的列车则容易造成检修资源浪费。基于此，安琪、陈旻瑜等^[6-7]考虑了列车的均衡运用，以动车组检修里程、接续时间、接续地点为约束条件，以使用车底成本最小为目标，构建动车组运用计划优化模型；魏国静等^[8]从车底总接续时间短、列车使用均衡、列车使用率高3个角度对列车运用计划进行编制。上述文献^[6-8]是以当日列车运行图为依据制定当日的列车运用计划，以列车行驶里程数为依据制定列车的均衡使用方案，但未考虑检修周期内的检修要求对列车运用的影响。臧瑶等^[9]以检修周期内列车行驶里程数趋于一致为目标，提出均衡运用原则的列车运用计划编配方案，使检修周期内的每一列列车的行驶里程趋于一致，实现了列车的均衡运用；Li等^[10]考虑了检修周期的时间约束与检修周期时间内列车行驶里程数要求，以检修周期内列车行驶里程最大化为目标建立列车运用模型。文献[6—10]的研究主要针对列车收发车车站都是单车辆段的情况，不能适用于多车辆段的情况。文献[11—14]对多车辆段的列车运用计划进行研究，协同考虑列车运用计划与检修计划，将车辆运用与检修计划编配问题转化为连续的时空网络组合路径寻优问题^[10-11]和网络流问题^[12]进行求解。但是，文献[11—12]只考虑了当日列车运用计划，若列车在运行中行驶里程数到达临检值，则立即回库进行检修，没有对列车的检修要求进行统筹规划，未考虑列车检修日期对于列车运用计划编制的影响。文献[13—15]的列车运用计划只是为列车的检修计划服务，使列车检修时的接续时间最少，未考虑列车的均衡运用与检修日期对列车运用计划编制的影响。综上所述，目前列车运用计划的问题主要有以下3点：①相关研究多针对单一车辆段^[1-2，4-10]；②编制列车运用计划时未考虑列车使用的均衡性^{[1-5，13-15]}；③忽略了检修计划与检修日期对列车运用计划编制的影响^{[6-8，11-12]}。随着城市规模的扩大和城市轨道交通客流量的增加，单车辆段的运营能力会达到饱和，难以满足城市载客量的需求，而通过增加车辆段数量以提高运营效率将是轨道交通适应城市规模发展的重要举措。双车辆段运营可以减少车辆在途中的时间，提高发车频率，平衡所有车辆段的运营压力；而且在提高整个系统可靠性和可用性的同时还能在不同的地理位置提供更多的停车和检修设施。目前北京地铁7号线和10号线、上海地铁8号线、广州地铁3号线均已采用双车辆段的设置。为此，依托北京地铁某号线的运营数据提出一种综合考虑双车辆段车辆的运营计划编制问题，在满足地铁列车检修计划(月修和里程修)、检修日期约束需求的基础上，使列车实现均衡运用。

为了解决一个时间周期内双车辆段地铁列车均衡运用编制问题，基于改进果蝇算法^[16]建立地铁列车运用计划编制模型。将列车当作加工机械，将车次任务当作加工工序，以列车与车次任务匹配成本最小为目标函数，将求解列车与车次的匹配问题转化为求解柔性作业车间调度问题，将双车辆段的所有车次任务与列车进行统一编制，建立列车与车次任务的匹配程度表，求解出一个时间周期内的最优列车运用方案。为了加强果蝇算法寻找全局最优解的能力，将果蝇算法的搜索步长与灰狼算法^[17]的收敛因子与距离公式相结合，提出一种新的搜索步长公式用来加强果蝇算法搜索最优解的能力。

1　问题描述

针对A，B两车辆段的列车运用计划编制问题进行研究。A车辆段共有k列车次，其中g列车次为A车辆段发车、B车辆段回库的车次；k-g列车次为A车辆段发车后再返回A车辆段车次，g\le k；B车辆段共有m列车次，其中l列车次为B车辆段发车、A车辆段回库的车次，m-l列车次为B车辆段发车后再返回B车辆段车次，l\le m。列车定修包括月修与里程修，月修里程为18 000~22 000 km；里程修为40万里程修，当列车总里程数到达40万km时进行里程修。

每日列车运用计划编制需要依据列车的当前状态和提前设置的车次任务，选择合适的列车安排给车次，完成当日的车次任务。因此，将列车发车时的运用计划编配问题以列车-车次匹配成本最小为目标函数建立列车的运用计划编配模型，拟重点解决以下3个问题：一是基于车次公里数与列车当前的行驶里程(月修里程与总里程数)，如何合理编配列车运用计划，以保证列车在运用计划编制周期内实现均衡运用；二是基于相同的匹配成本会出现多种列车-车次匹配方案，不同方案的选择会影响长期列车运用计划编制的情况，如何建立以列车均衡运用和一个编制周期内总匹配成本最小为目标的列车长期运用计划编配模型；三是在编配长期运用计划时，如何统筹考虑2个车辆段的所有车辆与车次情况，通过合理编配运用计划，以保证列车在运用中担任最合适的车次。

2　模型建立

2.1　建模说明

地铁列车长期运用计划编配是个极其复杂的问题，为了突出研究重点、降低模型的复杂程度，做出以下说明。

（1）每日车次计划已知。模型只考虑每日固定的车次计划，不考虑临时增加车次问题，若需要临时增加车次时，则由调度员为临时车次指派合适的空闲列车。

（2）不考虑列车每日停靠股道对车次选择的影响。模型求解长期列车运用计划编配问题，每日回库列车以第二日的运用计划为依据选择合适的停靠股道。

（3）指定车次已知。在制定运用计划前确定好指定车次的日期、指定车次和担任指定车次任务的列车编号，若因突发情况导致某日的指定车次安排出现变化，由调度员进行重新安排。

（4）在编制双车辆段的列车运用计划时，将双车辆段所有的列车与车次统一编配，通过合理地编制列车运用计划，使列车在运用中自动调整到最合适的车辆段，担任最合适的车次。

（5）模型中只有B车辆段具有定修能力，所有需要定修的车辆必须抵达B车辆段进行定修。

（6）里程修重要程度大于月修。月修结束后，列车月修里程从0开始重新记录；里程修结束后，列车累计里程不清零。

2.2　建立模型

模型涉及的集合如下：E为全部列车集合，E=\{E_Z,E_J\}。其中，E_Z 为A车辆段的列车集合，E_Z=\{E_{Z,i}|i=\mathrm{1,2},\cdots ,n\}，n表示有n辆车停靠在A车辆段；E_J为B车辆段的列车集合，E_J=\{E_{J,i}|i=\mathrm{1,2},\cdots ,q\}，q表示有q辆车停靠在B车辆段。F为所有车次集合，F=\{F_Z,F_J\}。其中，F_Z为A车辆段的车次集合，F_Z=\{F_{Z,j}|j=\mathrm{1,2},\cdots ,k\}，k表示A车辆段有k列固定车次；F_J为B车辆段的车次集合，F_J=\{F_{J,j}|j=\mathrm{1,2},\cdots ,m\}，m表示B车辆段有m列固定车次；A车辆段发往B车辆段车次为F_{Zh}=\{F_{Zh,j}|j=\mathrm{1,2},\cdots ,g\}，g\le k；B车辆段发往A车辆段的车次为F_{Jh}=\{F_{Jh,j}|j=\mathrm{1,2},\cdots ,l\}，l\le m。T为运用计划编制总天数集合，T=\{T_t|t=\mathrm{1,2},\cdots ,p\}。

模型涉及的变量如下：X_{ij}为0-1决策变量，表示列车i与车次j的分配情况，当列车i担任车次j时，X_{ij}为1，否则为0；U_i为0-1变量，表示列车i状态，0表示列车定修，1表示列车正常，U_i^{\mathrm{\text{'}}}表示第二日车辆状态；L_i为0-1变量，表示定修列车i的里程修状态，1表示列车正在进行里程修，否则为0；D_i为0-1变量，表示列车i是否完成里程修情况，当列车i完成里程修时，D_i为1，否则为0；Q_i为0-1变量，表示定修列车i的月修状态，1表示列车进行月修，否则为0。

C_{ij}代表列车i与车次j的适应值，C_{ij}越小表示列车i匹配车次j的成本越低。在运用计划编配时，计算列车与车次的匹配程度，使得列车-车次匹配成本最小化，模型的目标函数如下。

\mathrm{m}\mathrm{i}\mathrm{n}({\displaystyle \sum _{t=\mathrm{1}}^p}{\displaystyle \sum _{i=\mathrm{1}}^{n+g}}{\displaystyle \sum _{j=\mathrm{1}}^{k+m}}{C}_{ijt}{X}_{ijt})⑴

C_{ij}的计算步骤如下。

步骤1：将指定车次任务的列车号填入相应的车次任务中。

步骤2：将2个车辆段所有可运行的列车按月修里程的公里数从小到大排序，其中里程修里程(累计里程)大于420 000 km且尚未进行里程修的列车单独挑选出来排在最后。

步骤3：将2个车辆段所有的车次按车次里程大小从大到小排序，里程数相同的车次排名也相同。

步骤4：把步骤2中列车的排序名次与步骤3中车次的排序名次之差当作列车与车次的适应值C_{ij}。C_{ij}的计算公式如下。

C_{ij}=|R_i-R_j|⑵

式中：R_i表示列车i在步骤2中的排名；R_j表示车次j在步骤3中的排名。

约束条件如下。

U_i=\mathrm{1}\begin{array}{cc}& \end{array}\forall i=\mathrm{1,2},\cdots ,n+q⑶

{\displaystyle \sum _i^n}{U}_i=a\begin{array}{cc}& \end{array}\forall i=\mathrm{1,2},\cdots ,n;a\le n⑷

{\displaystyle \sum _{i=\mathrm{1}}^a}{X}_{ij}=\mathrm{1}\begin{array}{cc}& \end{array}\forall j=\mathrm{1,2},\cdots ,k⑸

{\displaystyle \sum _{i=\mathrm{1}}^q}{X}_{ij}=\mathrm{1}\begin{array}{cc}& \end{array}\forall j=\mathrm{1,2},\cdots ,m⑹

{\displaystyle \sum _{j=\mathrm{1}}^k}{X}_{ij}\le \mathrm{1}\begin{array}{cc}& \end{array}\forall i=\mathrm{1,2},\cdots ,n⑺

{\displaystyle \sum _{j=\mathrm{1}}^m}{X}_{ij}\le \mathrm{1}\begin{array}{cc}& \end{array}\forall i=\mathrm{1,2},\cdots ,q⑻

{\displaystyle \sum _{i=\mathrm{1}}^q}{L}_i\le \mathrm{1}\begin{array}{cc}& \end{array}\forall i=\mathrm{1,2},\cdots ,q⑼

{\displaystyle \sum _{i=\mathrm{1}}^q}{Q}_i\le \mathrm{3}\begin{array}{cc}& \end{array}\forall i=\mathrm{1,2},\cdots ,q⑽

公式⑶表示参与车次分配的列车i必须可运用；公式⑷表示B车辆段可运行列车数量，a表示B车辆段正常运用的列车总数；公式⑸、公式⑹表示每个车次只能由一列同车辆段的列车担任。公式⑺、公式⑻表示一列列车最多可以担任一个同车辆段的车次；公式⑼表示B车辆段最多同时有1列列车进行里程修；公式⑽表示B车辆段最多同时有3列列车进行月修。

2.3　模型转换

在有关轨道交通问题研究中，将相关模型转化为柔性作业车间调度问题进行求解是一种常见方案^[18-19]。其中，柔性作业车间调度问题是指一个加工系统有M台机器，要求加工N个工件，每个工件有W道工序，每个工件必须按照工序的先后顺序加工。

研究将列车运用问题转换为柔性作业车间调度问题进行求解，列车运用问题实质是依次为每个车次任务指派合适的列车，柔性车间调度问题实质是为工件依次在每道工序指派合适的加工机器；模型转换时，将车次任务转换为工序，将列车转换为加工机器，将列车与车次的匹配关系X_{ij}转换为工件，由于一列列车最多可以担任一个同车辆段的车次，以及每个车次只能由一列同车辆段的列车担任，因此工件数目只能设置为1，让该工件在每道工序中寻找合适的加工机器，所选的工序与加工机器的组合既为X_{ij}=\mathrm{1}的列车与车次的匹配关系。如此一来，可通过工件在每道工序中选择的加工机器来表示车次任务与列车的编排关系。在列车运用问题中，适应值C_{ij}的数值随着列车与车次的不同产生变化，而柔性作业车间调度问题中，每道工序的加工时长是允许依据加工机器的不同而变化的，于是用C_{ij}的数值来表示转换后的加工时长。模型转换后，编制双车辆段列车运用计划步骤如下。

步骤1：计算出所有的列车i担任车次j的适应值C_{ij}，将C_{ij}视为工件在当前工序选择不同机器加工的加工时间。

步骤2：列车运用计划需要将指定车次任务的列车与有早晚高峰任务的列车安排到对应车次，将这些有指定任务的列车与车次的编排关系视为工件在特定工序中选择指定机器进行加工。

步骤3：列车运用计划中需要依次为车次任务指派合适的同车辆段的列车，将为车次指派合适的列车这个过程视为工件从第一个工序开始选择满足加工要求的加工机器，工件在当前工序完成加工后，将选择的机器从机器合集中去除，工件进入下一道工序进行加工，依次类推，直到完成所有工序。

步骤4：重复上述操作至最大迭代次数，选出所有工序累计加工时间最少的工件加工方案，该方案即为最优的列车运用计划编制方案。

3　求解算法

果蝇算法^[16]具有复杂度低、全局寻优能力强、收敛速度快、控制参数少等优点，适用于求解连续优化问题、离散优化问题、多目标优化问题等。地铁列车运用计划的编制问题是一类特殊的指派问题，也是一类典型的NP-完全问题^[15]；对地铁列车运用计划进行编制实质就是求解多目标离散优化问题。目前对该问题求解多采用遗传算法、蚁群算法、粒子群算法与模拟退火算法等启发式算法，但这些算法在求解过程中普遍具有陷入局部最优解、求解速度慢、参数设置困难等问题。相较于上述这些传统启发式算法，果蝇算法求解实现过程简单、参数设置简单、不需要进行复杂的参数调整和编码解码操作，且在搜索过程中能充分利用群体的信息，不断地更新位置，从而实现全局搜索和快速搜索。因此采用果蝇算法对地铁列车运用问题进行求解。

3.1　算法说明

种群中的果蝇个体通过嗅觉搜索的方式搜寻空气中的果实气味浓度，然后找出味道浓度最大的位置，记录当前果蝇个体的位置，其余果蝇通过视觉搜索的方式集中到此位置，重复此操作直到找出果实的具体位置。其中嗅觉搜索的公式表示如下。

\left\{\begin{array}{l}X=X\_axis+L\\ Y=Y\_axis+L\end{array}\right.⑾

式中：X\_axis，Y\_axis表示当前所有果蝇个体集合位置；L表示搜索步长；X，Y表示搜索后的果蝇个体位置。

搜索步长L的取值会对果蝇算法的性能产生重要的影响，在传统果蝇算法中，L的取值为一个固定值，L的取值过大会降低局部搜索能力，L取值过小则降低全局搜索能力。因此，找出一种更加合理的搜索步长L的取值方法，对于提升果蝇算法的搜索能力十分重要。

研究借鉴灰狼算法^[17]的搜索方案思路，将灰狼算法的搜索因子和距离公式与果蝇算法相融合，使果蝇个体在迭代过程中结合上一代果蝇个体位置生成新的个体位置。改进的果蝇嗅觉搜索公式如下。

\left\{\begin{array}{l}X=X\_axis+L\mathrm{\text{'}}\times D_X\\ Y=Y\_axis+L\mathrm{\text{'}}\times D_Y\end{array}\right.⑿

式中：L\mathrm{\text{'}}为动态搜索步长；D_X，D_Y为距离公式。

动态步长L\mathrm{\text{'}}计算公式如下。

L\mathrm{\text{'}}=L\times a\mathrm{\text{'}}⒀

⒁

式中：a\mathrm{\text{'}}为改进的灰狼算法搜索因子，t\mathrm{\text{'}}为当前迭代次数，t{\mathrm{\text{'}}}_{\mathrm{m}\mathrm{a}\mathrm{x}}为最大迭代次数。

距离公式D_X与D_Y计算公式如下。

\left\{\begin{array}{l}{D}_X=|\mathrm{2}\times r_{\mathrm{1}}\times (X\_axis-X\mathrm{\text{'}})|\\ D_Y=|\mathrm{2}\times r_{\mathrm{1}}\times (Y\_axis-Y\mathrm{\text{'}})|\end{array}\right.⒂

式中：r_{\mathrm{1}}为[0，1]中的随机值；X\mathrm{\text{'}}，Y\mathrm{\text{'}}为前一代果蝇个体位置。

改进的动态步长迭代曲线如图1所示。由图1可知，L\mathrm{\text{'}}随着迭代次数的增加逐渐减少。在0~50次迭代计算期间，L\mathrm{\text{'}}减少较慢，保证了果蝇在迭代初期具有较大的搜索步长进行全局搜索；在50~100次迭代计算期间，L\mathrm{\text{'}}减少加快，使果蝇在后期以较小的步长进行局部搜索，提高搜索精度。

传统果蝇算法、只加入收敛因子a\mathrm{\text{'}}的果蝇算法与改进果蝇算法以文献[16]中的测试方案得出的3种算法对比结果如图2所示。由图2可知，改进果蝇算法的搜索能力较经典果蝇算法和只加入收敛因子a\mathrm{\text{'}}的果蝇算法有显著提升。

3.2　编码

果蝇编码片段如图3所示，每个片段21列，代表21个车次，每列数字代表担任当前车次任务的列车。在求解过程中，果蝇的编码片段作为果蝇的信息参与迭代。

在求解过程中，采用文献[20]中的转换方法，先将图3数据送入公式⒃，计算得到位置信息，再将位置信息从第一列车次开始，依次送入公式⑿求解，然后将求解得到的新的编码信息送入转换公式⒄进行信息转换得到新的列车-车次匹配方案。

x(h)=\frac{\mathrm{2}\epsilon }{z(h)-\mathrm{1}}(u(h)-\mathrm{1})-\epsilon　　 z(h)\ne \mathrm{1}⒃

u(h)=round(\frac{x(h)+\epsilon }{\mathrm{2}\epsilon }(z(h)-\mathrm{1})+\mathrm{1})　 \mathrm{1}\le h\le \mathrm{21}⒄

式中：h表示当前车次；x(h)表示第h车次求解得到的数据；\epsilon为21；z(h)表示第h车次可用的列车数；u(h)表示列车在h车次可用的列车集中的序号，即车次可用列车集中第u(h)号列车担任该车次任务。

每求解完一列车次，就更改列车状态，使其在后续车次任务中不可被选中。

3.3　求解流程

研究应用改进的果蝇算法，对列车的长期运用计划进行调整，求解最优的列车担任车次，求解流程如下。

步骤1：信息参数初始化。初始化列车运用计划编制总天数与总迭代次数。

步骤2：列车与车次信息初始化。初始化车辆段信息、列车总数、列车运行里程、列车检修计划、列车里程修情况、车次总数、车次时间、车次里程。

步骤3：将指定车次任务的列车与有早晚高峰任务的列车安排到对应车次，将其余列车与车次生成列车担任车次的适应值C_{ij}。

步骤4：更新列车运用状态。列车运用状态受列车定修安排影响。列车运用状态更新树状图如图4所示。A车辆段今日可运行且明日不定修的列车，可参与今日运用计划的编制；A车辆段今日可运行且明日定修的列车可担任今日A车辆段到B车辆段的车次任务；A车辆段今日可运行且明日不定修但行驶里程达到定修里程的列车可担任今日A车辆段到B车辆段的车次任务。B车辆段今日可运行且明日不定修的列车可参与今日运用计划的编制；B车辆段今日可运行且明日定修但却未到达定修里程的列车可担任B车辆段到B车辆段的车次任务；B车辆段今日可运行但明日定修且到达定修里程的列车可不参与今日运用计划编制。设置A车辆段的月修里程标准为21 000 km，若无21 000 km列车，则以500 km为幅度，逐次下降至19 000 km；B车辆段的月修里程标准为20 000 km。设置A，B车辆段的40万里程修标准限制为420 000 km。

步骤5：依据C_{ij}、列车运行状态、列车与车次所在车辆段信息生成初始列车-车次匹配关系。列车只能担任同一车辆段的车次任务，需要通过指定车次去往不同车辆段的列车只能担任指定车次任务。

步骤6：果蝇算法初始化。初始化果蝇种群数目、搜索因子、搜索步长、最大迭代次数，生成初始种群。每只果蝇个体内包含21组数，代表一套完整列车-车次匹配关系，将列车-车次匹配关系转化为果蝇的位置信息。

步骤7：果蝇算法优化。找出并记录当前迭代中适应度值最优的果蝇个体的位置；所有果蝇个体飞到适应度值最优的果蝇个体处集合，更新数据准备下次迭代。

步骤8：输出并保存最优果蝇个体数据，将其转化为列车i与车次j的匹配关系，再计算列车i与车次j的匹配成本C_{ij}。

步骤9：重复步骤5至步骤8，达到最大迭代次数后，结束算法，输出并保存最优解，即当日的列车运用计划。

步骤10：自动检修安排。统计空闲月修股道，将最优解中，B车辆段未与车次匹配、里程数大于20 000 km、距离月修检修日期大于7 d的列车按里程数从大到小排列，按顺序安排进空闲月修股道，直至空闲月修股道数量为0。若无里程数大于20 000 km的列车，则以500 km为幅度，逐次下降至19 000 km。

步骤11：重复步骤2至步骤10，达到运用计划编制总天数后，停止迭代，将每日运用计划的匹配成本求和，输出并保存所有的运用计划与求和成本。

步骤12：重复步骤11，达到总迭代次数后，停止迭代，输出求和成本最小的总天数运用计划。

研究计算列车与车次的适应度C_{ij}的方案容易使检修日期安排不合理的列车长期不被使用，不利于列车均衡运用，于是提出一种自动检修方案应用于步骤4与步骤10中，使上述列车进行动态调整。在编制每日运用计划时，会出现相同的匹配成本包括多种运用方案的情况，不同的运用方案会对后续日期的运用计划产生不同的影响，使最后的总天数运用方案并不是最优方案，因此，通过步骤12，选出最优的总天数运用方案。

4　实例仿真

4.1　基本参数

研究中，2个车辆段共有30列车，21个车次，某城市的地铁列车车次时间表如表1所示，表1中包括了车次的运行时间与公里数，其中1号—11号车次从A车辆段发车，12号—21号车次从B车辆段发车。其中，第2、第3、第5、第7、第8、第9、第10号车次为A车辆段发往B车辆段车次；第1、第4、第6、第11号车次为A车辆段发车最终返回A车辆段车次；第12、第14、第15、第16、第17、第18、第20号车次为B车辆段发往A车辆段车次；第13、第19、第21号车次为B车辆段发车最终返回B车辆段车次。地铁列车信息表如表2所示。设置种群个数为100，算法最大迭代次数为100次，计划编制天数为60 d。对算法进行10次求解，取10次中的最优结果为该算法编制的最优60 d运用计划方案。

4.2　对比分析

为了验证算法的有效性和适用性，分别利用灰狼算法、果蝇算法、改进果蝇算法对同一天的列车运用计划进行求解。单日运用计划编制结果如图5所示，从图5可以看出，改进的果蝇算法求解精度更高，求解速度更快。

60 d列车-车次匹配成本变化如图6所示，3种算法求解的60 d运用计划成本如表3所示。可以看出，改进的果蝇算法求解得到的列车-车次匹配成本最低，取得了最好的运用结果。

4.3　实验结果分析

理想状态下，30列列车的月修里程均为0 km，则修程后公里数为0的60 d列车行驶里程如图7所示。从图7可以看出，除列车2、列车11、列车25、列车26、列车30外，其余所有列车60 d内累计行驶里程十分接近，里程数曲线增长过程十分紧凑且无明显波动，表明列车得到了均衡运用，不存在部分列车被大量使用的情况以及分阶段使用的情况，证明研究方案在使列车均衡运用方面具有很明显的效果。

特殊列车数据情况如表4所示。其中列车2先是因为总累计里程达到了设定的42 000 km还未进行过里程修，影响了列车运用计划编制，随后列车2开始里程修，导致剩下天数未能参与运用计划编制；列车11与列车30因为总累计里程达到了设定的42 000 km还未进行过里程修，影响了运用计划编制，行驶里程明显少于正常车辆的行车里程；列车25因为里程修影响，导致60 d中有部分日期未能参与运用计划编制，行驶里程明显少于正常车辆的行驶里程；列车26受里程修影响，在计划前期未参与运用计划编制，在里程修结束后迅速参与运用计划编制，最终行驶里程数据十分接近正常车辆。

实际情况中，列车的月修里程不可能全为0，在编制运用计划时，不同的运用里程数势必对运用计划编制产生影响，列车均衡运用的目的是减少对列车的过度使用情况，所以在编制运用计划时，若某列车运用里程数过大，则在运用计划编制过程中，要适当减少该列车的使用次数。采用表2完整数据生成的60 d运用计划行驶里程如图8所示。图8中，多数列车的行驶里程曲线依旧集中在一块，但是较图7相比分散很多；图8中出现多条行驶里程数明显低于常规里程数的曲线，除列车2、列车11、列车25、列车26、列车30外，新增列车为列车1、列车5、列车7、列车13、列车14、列车19、列车22、列车23、列车24。

从图8可以看出，在第20日，有多列列车处于长时间停滞状态，于是就以第20日列车数据为例对问题进行分析，第20日运用计划编制的停滞列车车辆信息如表5所示。

从表5可以看出，第20日运用计划编制中停滞列车的运用里程排名靠后，表明列车运用里程数过大，且未达到检修里程标准，根据均衡运用原则，列车运用里程过大就要适当减少该列车的使用次数。同理，列车5、列车7、列车13也因为运用里程数问题导致运用计划编制周期内的行驶里程数较少。图8中列车5、列车7、列车13的里程数曲线缓慢增长，未出现长时间停滞，也表明研究方案均衡运用原则针对运用里程数过大但未达到检修界限的列车采用的是适当减少该列车使用次数方案，而不是禁止参与运用计划编制。

人工编制列车运用计划时，容易出现列车行驶里程到达检修标准却未能按时检修，依旧参与运用计划的情况，存在很大安全隐患。自动检修方案与人工方案的检修日期对比如表6所示，其中列车16、列车20、列车27无明确人工计划方案，系统依据列车运行里程数自动生成检修日期安排，列车1、列车12、列车24、列车30的自动检修方案比人工方案平均提前14.75 d。实验证明，研究方案不仅能确保列车按时进行检修，还能对不合理的检修安排进行自动调整。

5　结束语

考虑检修里程约束与周期约束的列车运用计划编制研究，可以促进列车的合理使用，降低城市轨道交通系统的列车运用成本。研究考虑列车检修后运行里程、检修周期及车辆段检修能力等约束，构建双车辆段条件下地铁列车运用计划编制优化模型，采用改进果蝇算法进行求解，得出地铁列车运用计划编制方案。结果表明，改进果蝇算法取得了最快最精准的求解结果；求解60 d的最优运用计划编制方案时，改进果蝇算法也取得了最低的编配成本；在理想化条件测试下，研究方案实现了列车均衡运用，在运用计划编制周期内，所有列车的行驶里程趋于一致；在真实条件的测试中，列车在检修后运行里程、检修周期等约束条件的影响下，依旧实现了列车的均衡运用；自动检修方案可以有效地更改不合理的检修日期安排，改进列车运用与检修安排的合理性。

参考文献

[1] 赵鹏，富井规雄.动车组运用计划及其编制算法[J].铁道学报，2003(3)：1-7.

[2] ZHAO Peng， NORIO Tomii.Train-set Scheduling and an Algorithm[J].Journal of the China Railway Society，2003(3)：1-7.

[3] 赵 鹏，富井规雄.基于概率局域搜索的动车组平日运用计划编制算法[J].系统工程理论与实践，2004(2)：123-129，144.

[4] ZHAO Peng， NORIO Tomii.An Algorithm for Train-set Scheduling on Weekday Based on Probabilistic Local Search[J].Systems Engineering-Theory & Practice，2004(2)：123-129，144.

[5] 赵 鹏，富井规雄.基于路段交换的多基地动车组运用计划的编制算法[J].铁道学报，2004(1)：7-11.

[6] ZHAO Peng， NORIO Tomii.An Algorithm for Multiple-Bases Train-set Scheduling Based on Path-exchange[J].Journal of the China Railway Society，2004(1)：7-11.

[7] 李 建，林柏梁，耿令乾，等.基于交路接续的动车组运用计划优化模型与算法[J].交通运输系统工程与信息，2015，15(5)：172-177，194.

[8] LI Jian， LIN Boliang， GENG Lingqian，et al.Optimization Model and Algorithm for Motor Train Set Utilization Scheduling Based on Routes Connection[J].Journal of Transportation Systems Engineering and Information Technology，2015，15(5)：172-177，194.

[9] 徐安雄，王 鑫，曲正钢. 地铁车辆基地综合自动化管理系统收发车计划编制及动态调整方案[J]. 城市轨道交通研究，2020， 23(12)：193-197.

[10] XU Anxiong， WANG Xin， QU Zhenggang. Formulation and Dynamic Adjustment of Vehicle Receiving and Dispatching Plan of Metro Vehicle Base Integrated Automation Management System[J].Urban Mass Transit，2020，23(12)： 193-197.

[11] 安琪，王建英.检修条件下动车组运用计划编制研究[J].铁道运输与经济，2012，34(3)：56-60.

[12] AN Qi， WANG Jianying. Study on EMU Use Planning under Maintenance Condition[J].Railway Transport and Economy，2012，34(3)： 56-60.

[13] 陈旻瑜，张雨洁，张守帅，等.基于车底使用数量最少的动车组运用计划优化研究[J].铁道运输与经济，2022，44(8)：52-57.

[14] CHEN Minyu， ZHANG Yujie， ZHANG Shoushuai，et al.Operation Plan Optimization of Electric Multiple Units Based on the Minimum Number of Rolling Stock[J].Railway Transport and Economy，2022，44(8)：52-57.

[15] 魏国静，毛保华，王永亮.城市轨道交通动车组运用计划编制方法研究[J].城市轨道交通研究，2013，16(6)：97-100.

[16] WEI Guojing， MAO Baohua， WANG Yongliang.On Plan Compiling Methods of Urban Rail Transit Vehicle Scheduling[J].Urban Mass Transit，2013，16(6)：97-100.

[17] 臧 瑶，徐 刚，黄 瑛，等.基于均衡运用原则的列车运营日计划编配研究[J].城市轨道交通研究，2018，21(12)：24-29.

[18] ZANG Yao， XU Gang， HUANG Ying，et al.Research on the Daily Schedule of Train Operation Based on Balanced Application Principle[J].Urban Mass Transit，2018，21(12)：24-29.

[19] LI J， LIN B， WANG Z，et al.A Pragmatic Optimization Method for Motor Train Set Assignment and Maintenance Scheduling Problem[J].Discrete Dynamics in Nature and Society，2016，2016(3)：1-13.

[20] 姜建萍，徐永能，吴任飞，等.基于时空网络的地铁车辆运用与检修优化模型[J].四川兵工学报，2020，41(11)：171-176.

[21] JIANG Jianping， XU Yongneng， WU Renfei，et al.Optimization Model of Metro Vehicle Operation and Maintenance Based on Spatio-Temporal Network[J].Journal of Ordnance Equipment Engineering，2020，41(11)：171-176.

[22] 姜建萍.基于均衡检修的地铁列车运用计划优化方法研究[D].南京：南京理工大学，2021.

[23] JIANG Jianping.Research on Optimization Method of Metro Train Utilization Plan Based on Balanced Maintenance Strategy[D].Nanjing：Nanjing University of Science & Technology，2021.

[24] 彭其渊，廖珮茹，何必胜，等.全天候运行条件下的城市轨道交通车底运用与检修协同优化[J].中国铁道科学，2022，43(6)：194-206.

[25] PENG Qiyuan， LIAO Peiru， HE Bisheng，et al.Collaborative Optimization of Urban Rail Transit Car Bottom Operation and Maintenance under All-Weather Operation Conditions[J]. China Railway Science， 2022，43(6)：194-206.

[26] 冯 佳，李国威，付义龙，等.共享车辆基地的城轨车底运用与检修计划协同编制[J].交通运输系统工程与信息，2023，23(1)：131-140.

[27] FENG Jia， LI Guowei， FU Yilong，et al.The Utilization of Urban Rail Car Bottom in the Shared Vehicle Base is Coordinated with the Maintenance Plan[J].Journal of Transportation Systems Engineering and Information Technology，2023，23(1)：131-140.

[28] 佟 璐，聂 磊，赵 鹏.蚁群算法在动车组运用问题中的应用[J].交通运输系统工程与信息，2009，9(6)：161-167.

[29] TONG Lu， NIE Lei， ZHAO Peng.Application of Ant Colony Algorithm in Train-Set Scheduling Problem[J].Journal of Transportation Systems Engineering and Information Technology，2009，9(6)：161-167.

[30] PAN W T.A New Fruit Fly Optimization Algorithm：Taking the Financial Distress Model as an Example[J].Knowledge-Based Systems，2012，26(2)：69-74.

[31] MIRJALILI S， MIRJALILI S M， LEWIS A.Grey Wolf Optimizer[J].Advances in Engineering Software，2014，69(3)：46-61.

[32] 童佳楠，聂磊，贺振欢.基于遗传算法的动车运用所一级检修作业计划优化[J].铁道运输与经济，2016，38(8)：59-65.

[33] TONG Jianan， NIE Lei， HE Zhenhuan.Optimization of First-Level Maintenance Plan in EMU Depot Based on Genetic Algorithm[J].Railway Transport and Economy，2016，38(8)：59-65.

[34] ZHAO Peng， HAN Baoming， LI Dewei，et al.Model and Algorithm for the First-Level Maintenance Operation Optimization of EMU Trains[J].Journal of Intelligent & Fuzzy Systems，2021，41(1)：2145-2160.

[35] YUAN Y， XU H， YANG J D.A Hybrid Harmony Search Algorithm for the Flexible Job Shop Scheduling Problem[J].Applied Soft Computing，2013，13(7)：3259-3272.

基金资助

山东省自然科学基金项目(ZR2021MF076)

山东省自然科学基金项目(ZR2016FB04)

国家自然科学基金项目(21606141)

山东省重点研发计划项目(2018GHY115025)

电网运行风险防御技术与装备全国重点实验室基金项目(SGNR0000KJJS2302137)