王宇晴， 查伟雄,2*， 万平

(1.华东交通大学交通运输工程学院， 南昌 330013； 2.华东交通大学交通运输与经济研究所， 南昌 330013)

列车运行调整与到发线运用都是铁路行车调度指挥工作中的重点，列车运行调整的主要目标是列车占用区间的次序和列车占用区间的时长，同时需要调整列车的到发时刻等。到发线运用则是列车在车站具体占用进路和到发线的固定方案，故列车运行调整的维度相对于到发线运用较高。同时这两者也是相辅相成的关系。仅针对列车运行调整的优化问题，中外学者已有一定的研究成果，但是同时考虑到发线运用方面的研究还是较少。

Zhu等[1]建立了能够对多个突发事件同时进行优化的动态列车运行调整模型，并通过算例验证其有效性。Hong等[2]建立了列车取消运行情况下的运行图与停站方案一体化调整模型，通过能加停站次数，将延误旅客运送至目的地。Zhang等[3]提出一种运行调整与线路应急维护的协同优化策略，在解决线路应急维护的同时，进行运行调整降低列车延误，提升运行控制的鲁棒性。李晓娟等[4]以各列车在各车站的总延误时间最小为目标，设计了一种分阶段多叉树的算法来求解。户佐安等[5]以乘客总旅行时间最小为目标建立了基于列车运行一体化调整方法的模型，并设计嵌套式遗传算法进行求解。高如虎等[6]构建了基于Time-Station-Track网络的0-1整数规划模型，并设计拉格朗日松弛算法进行求解。牛晋才等[7]以列车进入车站和驶离车站的总晚点时间最少为目标，并运用人工鱼群算法求解。徐陪娟等[8]以到发线变更次数最少和列车晚点延误时间最短为目标，建立混合整数线性优化模型并设计两阶段近似算法进行求解。彭其渊等[9-10]以加权总晚点时间与到发线使用费用之和最小为优化目标，建立了线性0～1规划模型并设计了算法进行求解。王艺楠等[11]、李智等[12]分别将满意度与智能化应用加入列车运行调整的模型中，并设计算法进行求解。

从以上研究中可以发现，大多数学者在建模过程中约束和目标都考虑得比较全面。但在考虑到发线运用方面，大多只考虑了各站到发线的数量。在发生列车大面积的延误情况下，晚点列车占用到发线大多是依照调度人员的主观意识，在运输效率方面难以保证。在研究列车运行调整问题的同时，综合考虑到发线运用的协同优化问题非常有必要。

因此，现主要研究列车运行调整与到发线运用的协同优化问题。建模过程中，综合考虑宏观层面的列车流运行调整与微观层面车站的到发线运用调整，以列车的加权总到发晚点时间最少和到发线的占用总消耗最小为目标函数，并结合模型特点运用分层序列鸽群优化算法，以求得突发晚点情况下的列车运行调整计划时刻表和到发线运用变更情况，为铁路管理部门的临时调度情况提供决策借鉴。

1 问题描述

1.1 列车运行图描述

选用双线自动闭塞高速铁路的单一方向线路为研究对象，且假设列车仅在车站内发生晚点。为后续便于程序设计以及晚点情况的表达，将列车运行图的计划线分别用到达线与出发线表示，横轴表示时间，纵轴表示车站，列车运行线与到达线和出发线的交点即列车的到达时间与出发时间，同时将运行图分成以分钟为单位1 440个离散时间点的集合，如图1所示。

图1 列车运行图表示Fig.1 Train operation diagram

1.2 问题假设

在列车出现晚点情况后，调度员将列车运行调整与到发线运用结合，并根据故障信息，在短时间内及时的做出决策，是一项困难性较高的工作。在这个过程中需要考虑的方面比较多，如列车运行时的安全性、列车及车站设备的能力约束以及场站的各项调度规则等方面。为了简化建模过程中的不必要因素，结合现场实际调度情况，做出如下假设。

(1)仅考虑列车在车站出发晚点的情况，不考虑线路区段内的突发情况导致的晚点。

(2)车站出现晚点的情况后，在列车出现晚点伊始，列车晚点具体时间并不确定。需要对接下来使用晚点列车所占用到发线的到发线运用方案进行调整。

(3)列车在车站的到发线运用，仅考虑停站通过的情况。

(4)列车正常运行情况下，都是严格按图行车。本文假定各列车在发生晚点前与恢复图定运行时间后，都严格按照运行图行车。

2 模型的建立

2.1 变量与符号说明

以某高速铁路下行方向为例，有如下变量定义。

(1)下行方向进入运行调整时间段的列车集合为I={i1,i2…,im,…,iM}。

(2)下行方向列车运行调整区段内，车站集合为J={j1,j2…,jn,…,jN}。

(3)在一些大型车站，一条到发线可能对应着多个接发车进路，所有车站对应的接车进路数量为g1,g2，…，gn，发车进路数量为h1,h2，…，hn。

车站jn接车进路集合为JCjn={w1,w2，…，wgn}，发车进路集合为FCjn={r1,r2，…，rhn}。

(4)n个车站下行方向各站到发线数量为k1,k2，…，kn，以Kjn表示车站jn到发线的集合，如第二个车站Kj2={l1,l2，…，lk2}。

(6)车站内接发车进路与到发线之间的逻辑关系采取0～1变量的方式，定义如下。

(1)

(2)

(3)

(7)列车优先等级用η(im)表示，值越大表示列车优先等级越高。不同等级列车所对应的权重为φ(im)，不等级列车相邻两站之间的最小运行时分用Tim，jn-jn+1表示，列车的列车im在车站jn最小作业时分用Timjn表示，相邻两列车的达到通过同一车站的最小间隔时间用Tjn-jn表示。

(8)最小到达、出发时间间隔分别用Td和Tc表示，列车的起、停附加时分分别用tq和tt表示。

(9)列车im通过车站jn的作业类型用βimjn表示。

(4)

2.2 约束条件

所建立的列车运行调整模型共有10组约束条件，这些约束中(1)～(6)为列车运行计划相关的约束条件，(7)～(10)为结合列车运行调整实际情况所提出的到发线运用约束条件。

(1)同车站，前后两列不同列车均满足最小到达、出发时间间隔。

(4)

(5)

(2)列车在相邻两站之间的运行时间，必需满足列车最小运行时分，并加上起停附加时分。

∀im∈I，∀jn，jn+1∈J

(6)

(3)列车若在某站停车，作业时间不得小于该车站的最小作业时间：

(7)

(4)所有列车发车时间不得早于图定出发时分。

(8)

(5)相邻两列车到达通过同一站的最小间隔时间。

(9)

(6)列车越行条件(后车im+1满足该条件，才能越行前车im)：

η(im+1)>η(im)

(10)

∀im，im+1∈I，∀jn∈J

(11)

∀im，im+1∈I，∀jn∈J

(12)

(7)列车占用咽喉区接发车进路和到发线，两者的唯一性约束。每列车在进站时，只能占用一个接发车进路和一条到发线。

接发车进路唯一性：

(13)

到发线选择唯一性：

(14)

(8)到发线与接发车进路的选择确定：

∀im∈I，∀jn∈J，∀l∈Kjn

(15)

(9)到发线被占用约束：

∀im,im+1∈I，∀jn∈J，∀l∈Kjn

(16)

(10)到发线占用数量约束：

∀l∈Kjn

(17)

2.3 目标函数

当列车偏离图定运行计划后，不同速度等级列车晚点后的类型也有一定的差异，并且调整措施也不相同。高等级列车相比于低等级的列车来说，运行调整所产生的效益较大。同时用于评价运行调整目标的类型也较多，本文使用的优化目标为总加权到发晚点时间最小，φ(im)为不同等级高速列车的权重，目标函数为

(18)

在到发线运用方面，应考虑到调整过程中对于车站作业秩序的影响程度最小，即尽量少地去调整到发线运用方案。所以，到发线运用问题的最优化目标为列车占用到发线的总消耗最小，即尽量选择对车站作业秩序影响较小的到发线。由于列车在车站停站通过时，选用非原到发线运用方案后，车站内人员、设备、场站之间工作调整，存在一定的复杂性，表达目标函数时，对于不符合原到发线运用方案的列车占用到发线情况进行统一，采取仅考虑单一权重的方式。ωiml为表示列车im占用到发线l的权重，取值为1和100。ωiml取1 时表示列车im在占用到发线l时，符合到发线运用方案。当取值100 时，表示列车im可以占用到发线l,但是不符合原到发线运用方案。在现场实际操作时，应当首选ωiml=1的到发线，但是在ωiml=1的到发线能力紧张的情况下，确保不产生多余的干扰，则可以视情形选用ωiml=100的到发线进行接发车。目标函数为

(19)

上述两个目标函数所对应的函数值量纲不同，同时求解会十分困难，所以在鸽群优化算法的基础上，引入分层序列法，设计了一种适用于求解上述多目标不同量纲问题的分层序列鸽群优化算法，进行求解。

3 分层序列鸽群优化算法

3.1 算法介绍

由于多目标、多约束问题大多是求解难度较高的NP-hard问题，所以在求解该类问题时，对于算法的选择也是求解的关键一步。

分层序列法是解决两个或两个以上目标，不宜用加权合成为单目标问题进行求解的有效方法。仅需对不同的目标确定优先等级，并在求解时设定不同等级目标所对应的检验数集合Qn。通过算法迭代，当所有检验数为非负时，进入下一层级目标的算法迭代。当所有目标的检验数集合均为非负时，即得到整体目标规划模型的满意解。

鸽群优化算法是通过模拟鸽子飞行过程中受地磁与地标影响的归巢习性，模拟设计出的一种较简易的群智能算法。该算法原理简洁明了，在设计过程中需要调节的参数较少，在编程时相对其他算法容易实现，同时鲁棒性也较强[13-14]。鸽群优化算法中有两个基本部分，分别为：指南针算子、地标算子。当目的地距离鸽子较远时，它利用的是附近的地磁场来判别飞行方向。当目的地距离较近时，则用附近熟悉的地标来定位飞行。

指南针算子：鸽群前期在飞行的过程中，判断方向的依据主要来自地磁场，通过地磁场来不断的调整飞行方向。在函数优化问题方面，鸽群算法就是把每个可行解作为一个个体i，而每个个体都有其相应位置和速度，分别记为Xi=[xi1,xi2,…,xiD]和Vi=[vi1,vi2,…,viD]，其中i∈{1,2,…,Np}，Np表示可行解数量，即产生初始解初始鸽群的数量；D表示维度数。个体的位置与速度在D维解空间中每次都随着迭代而更新。在第t次迭代中，每个个体的位置Xi与速度Vi计算公式为

Vi(t)=Vi(t-1)e-Rt+rand[Xg-Xi(t-1)]

(20)

Xi(t)=Xi(t-1)+Vi(t)

(21)

式中：R为指南针算子中的指南针因子；rand为取0～1的一个数值；Xg为目前为止全局的最优位置，可以视作是指南针所指向的位置。

地标算子：当它们飞行逐渐靠近目的地后，会通过寻找附近熟悉的地标来导航，如果某个个体附近有熟悉的地标，则该个体就会径直飞向目的地，假如该个体附近没有熟悉的地标，它就会跟着熟悉地标的鸽子飞行达到目的地。在每次迭代过程中将鸽群数量Np减半，选择适应度值较优的前一半作为当前种群，计算剩余鸽群的位置中心Xc，求解本文模型的地标算子为列车的图定运行时间与原到发线运用方案，将其作为参考方向，对每只鸽子的位置进行更新：

(22)

(23)

Xi(t)=Xi(t-1)+rand[Xc(t)-Xi(t-1)]

(24)

式中：fitness为用来评价解质量的函数。鸽群优化算法在地标算子阶段的总体参考方向是那些相对较优个体的位置中心，因为该阶段没有个体自身的速度和惯性干扰，种群能够在很短的时间内快速收敛，并且得到最优值。当算法的迭代总次数达到了初始设定的最大值，地标算子停止运行，输出最优值。

上述模型有两个优化目标：总加权到发晚点时间最小、列车占用到发线的总消耗最小。直接用单一算法进行求解较为困难。所以将分层序列法引入鸽群优化算法中，用于求解模型。以总加权到发晚点时间最小为优先层级的求解目标，其检验数集合为Q1，列车占用到发线的总消耗最小次之，其检验数集合为Q2。

3.2 分层序列鸽群优化算法步骤

求解列车运行调整与到发线运用协同优化模型的分层序列鸽群优化算法步骤如下。

步骤1参数输入，图定列车到发时刻、列车数与车站数、列车等级权重、最小到达出发时间间隔、最小列车运行时分、起停附加时分、各站到发线数量以及占用费用、晚点情况假设等。

步骤2初始化种群数目Np、解空间维度D、不同层级目标的检验数集合Qn、指南针算子最大迭代次数Nc1、地标算子最大迭代次数Nc2，随机产生初始解的适应度函数值。

步骤3对列车运行调整目标进行计算，鸽群中的每个个体寻优路径和速度进行设置。把每只鸽子的适应度值进行对比，得到最好的飞行路径，即对正点列车顺序进行保留，对晚点列车及后续列车进行调整。

步骤4进入指南针算子操作。通过式(20)和式(21)，对每只鸽子速度与路径的更新。接着依据约束条件再对比鸽子的适应度值，得到较优的列车运行调整方案。

步骤5当Nc>Nc1max后，指南针算子操作中止，进入到下一步操作。否则，继续步骤4。

步骤6进入地标算子操作。对已经得到的适应度值，依据式(22)进行减半。接着依据式(23)找到留下来适应度值的中心，即鸽子的理想目的地。将所有鸽子依据式(24)调整方向。最后，存储该最佳目标函数与相应的列车到发时刻。

步骤7当Nc>Nc2max后，地标算子操作中止，输出计算结果。否则，转到步骤 6。

步骤8验证列车运行调整目标的检验数集合Q1。若均为非负，则进入下一层级的目标计算。否则，转到步骤3。

步骤9对到发线运用目标进行计算，鸽群中的每个个体寻优路径和速度进行设置。把每只鸽子的适应度值进行对比，得到最好的飞行路径，即对正点列车到发线运用方案进行保留，对晚点列车及后续列车到发线运用方案进行调整。

步骤10进入指南针算子操作。通过式(20)和式(21)，对每只鸽子速度与路径的更新。接着依据约束条件再对比鸽子的适应度值，得到较优的到发线运用方案。

步骤11当Nc>Nc1max后，指南针算子操作中止，进入到下一步操作。否则，继续步骤10。

步骤12进入地标算子操作。对已经得到的适应度值，依据式(22)进行减半。接着依据式(23)找到留下来适应度值的中心，即鸽子的理想目的地。将所有鸽子依据式(24)调整方向。最后，存储该最佳目标函数与相应的到发线运用调整情况。

步骤13当Nc>Nc2max后，地标算子操作中止，输出计算结果。否则，转到步骤12。

步骤14验证到发线运用目标的检验数集合Q2。若均为非负，输出所有层级目标的计算结果。否则，转到步骤9。

4 算例分析

为了验证模型与分层序列鸽群优化算法求解的有效性，选取文献[15]中郑西高铁某区间段13：00—19：00的实际运行数据为仿真算例。已知数据如下：下行方向列车数11，车站数6，将列车速度等级分为一级、二级、三级，对应的列车权重φ(im)为3、2、1。11列车的等级为[1 1 1 1 3 3 3 3 2 2 2]，相应列车等级权重为[3 3 3 3 1 1 1 1 2 2 2]。列车的起停附加时分为2 min和1 min。各站到发线的数量分别为3、3、3、2、2、3条，各站到发线集合为K1,K2，…，K6，且有3条到发线的车站中，到发线l3是占用权重为100。

经过数次实验平台仿真分析后，初始参数设置如下：初始鸽群数量设置为No=30，地图和指南针算子最大迭代次数Nc1=5，地标算子最大迭代次数Nc2=15，地图与指南针因子R=0.2。为验证分层序列鸽群优化算法在求解上述模型时的有效性，结合文献[15]中设定的三种不同的晚点情况，并增加三种晚点情况都发生的情况进行模型求解分析。

三种假设晚点情况为：车次5在车站1晚点 10 min、车次9在车站1晚点15 min、车次8在车站3晚点30 min。运行调整结果如表1～表5所示，加粗字体表示经过调整后的到发时刻。

从表1和表5中可知：第一种晚点情况，车次5在车站1晚点10 min后，经调整，列车在第4站恢复为图定运行时间，同时造成车次6在第1站晚点4 min、第2站晚点1 min。到发线运用方面由于车次5在第1站发生晚点，为车次6更换至车站1的到发线2办理接发车作业。最后得到目标函数值Z1为56，总到发晚点时间为56 min，列车占用到发线总消耗Z2不变。

第二种晚点情况，车次9在车站1晚点15 min，算法调整结果以及到发线运用方案调整情况，如上表2所示。从表3中可知，第三种晚点情况，车次8在车站3晚点30 min后，经调整，车次9、10和11在车站3对车次8越行，只有车次8晚点，同时通过加快列车区间运行速度与压缩列车停站时分，总晚点时间为72 min，目标函数值Z1为144。并且在第三种晚点情况下，鸽群优化算法要明显优于免疫蚁群算法，优化效果为81.4%。从表4中可知，三种晚点情况都发生的场景下，经调整后的总晚点时间为394 min，也较优于免疫蚁群算法的调整结果，优化效果为7.3%。从表5中可知，假设的4种晚点情况，在到发线运用调整方面，调整后得到列车占用到发线总消耗Z2的值均为71，若现实中依据调度人员的主观判断调整该值则会无法确定，所以上述模型在实际生产调度方面具有一定的指导意义。

表1 第一种晚点情况算法调整后的列车运行时刻表

表2 第二种晚点情况算法调整后的列车运行时刻表

表3 第三种晚点情况算法调整后的列车运行时刻表

表4 三种晚点情况都发生算法调整后的列车运行时刻表

表5 不同晚点情况下到发线运用方案调整情况表

图2 第二种晚点情况目标Z1算法收敛曲线图Fig.2 Convergence curve of Z1 algorithm in the second case of delay

图3 第二种晚点情况目标Z2算法收敛曲线图Fig.3 Convergence curve of Z2 algorithm in the second case of delay

表6 不同晚点情况免疫蚁群算法与分层序列鸽群优化算法求解总到发晚点时间的结果对比

算法求解第二种晚点情况下，目标Z1与Z2的迭代图，如图2和图3所示。不同晚点情况免疫蚁群算法与分层序列鸽群优化算法求解总到发晚点时间的结果对比，如表6所示。从图2和表6可知，总到发晚点时间鸽群优化算法仅用4次左右迭代就得出了结果。而文献[15]中免疫蚁群算法在求解总到发晚点时间时，需要迭代50次左右，所以鸽群优化算法在求解本文优化模型时，具有一定的优越性。

5 结论

建立了列车运行调整与到发线运用协同优化模型，以列车在各站的总加权晚点时间最少以及列车在各站占用到发线的总费用最小为目标，同时考虑列车运行调整约束和到发线运用约束。结合现有群体智能算法求解该类问题时，收敛速度较低、求解速度慢的缺点，在鸽群优化算法的基础上引入分层序列法，对列车运行调整与到发线协同优化模型进行求解，得到的运行调整结果与免疫蚁群算法相比总是相同或者优于后者，算法迭代次数明显较少，并且还得到了满意的到发线运用调整方案，具有一定的实际参考价值。但是，模型考虑的仅为单方向条件下列车运行调整与到发线运用协同优化问题，下一步研究重点将是探究双线调度区段的列车运行调整与到发线运用协同优化问题。