仝 硕，陈绍宽，刘葛辉，刘 爽，毛保华

(1.北京交通发展研究院,北京 100073; 2.北京交通大学 交通运输部综合交通运输大数据应用技术交通运输行业重点实验室,北京 100044)

动车组运用计划是铁路客运日常工作的重要组成部分。随着我国高速铁路系统的快速发展，动车组开行密度不断增大，在降低运营成本、提高运营可靠性的要求下，优化动车组运用计划具有重要的理论意义与实际价值。

既有研究中，动车组运用计划编制优化问题主要涉及数学问题转化、运用场景选取、目标函数构造以及求解算法设计4个方面。首先，将动车组运用计划编制优化问题转化为多商品流问题和(多)旅行商问题等处理，Abbink等[1]针对单线周期运行图建立了最小化动车组数量和走行里程的双目标多商品流优化模型，优化了允许重联和摘解列车的周转计划；Giacco等[2]研究了维修条件下动车组运用计划，利用TSP问题建立混合整数规划模型；王超等[3]基于车辆线路问题理论，构建了动车组运行图与运用计划一体化优化模型。其次，基于实际情形，既有研究考虑了不同动车组运用方式、空车调拨、非单一编组和非单一车型等不同场景[4-5]，聂磊等[6]用实验证明空车调拨可以提高动车组利用率，在运行调整时可提高动车组运用的灵活性。然后，优化目标通常考虑动车组数量、动车组运用均衡性、检修均衡程度、检修次数等指标，例如，Canca等[7]以车底数最小和均衡性最大为目标；张才春等[8]以动车组数量最少和动车组总检修时间最小为目标；Cadarso等[9]在目标函数中考虑了运营中的延迟时间和人员需求，以优化路网车底运用计划的鲁棒性，但列车运用过程没有考虑检修约束；李建等[10]通过构建0-1整数规划模型实现了动车组接续时间最小化和动车组检修前累计运行里程最大化。最后，用于动车组运用计划模型求解的方法主要包括解析算法和智能算法两大类，前者主要有商业求解器[3]、分支-切割算法[7]、改进的分支定界法[11]等，后者则以蚁群算法[12]、模拟退火算法[13]、粒子群算法[10,14]等启发式算法为主。

既有研究较少涉及动车组运用计划中相邻列车任务接续的可靠性问题。动车组一般按时刻表执行交路段中的各运行任务，但实际中可能出现由突发事件或随机扰动造成的晚点情况，如列车到达晚点、检修(整备)任务完成晚点和空车调拨到达晚点。这类晚点会影响动车组在要求时间内完成接续和周转，即降低了接续可靠性。作为动车组运用计划的一部分，动车组接续延误会产生额外的运营调整和人员费用，所以在编制动车组运用计划时，应在降低接续时间成本的同时保证较高的接续可靠性。

本文结合我国动车组日常运用中的需求，基于运用网络图，应用晚点分布函数和概率论分析动车组接续可靠性，构建考虑动车组检修和热备的运用计划优化模型，设计基于蚁群算法的模型求解算法，并通过案例研究验证本文提出的方法。

1 动车组运用网络图构建

本文通过引入接续可靠性优化动车组的日计划，这一计划是动态的，即日计划均需根据动车组的初始状态、任务情况进行优化。动车组日计划需要基于维修历史数据、综合接续时间、检修里程和动车段所能力等约束，安排动车组在新的日计划中执行的各类任务，包括列车、检修(整备)和热备任务。其中，动车组在上一个日计划中的最后任务是新的日计划的初始任务，新的日计划的初始时刻为t0。动车组任务的接续关系见图1。

图1 反映各任务之间接续关系的动车组运用网络图

图1中k为动车组的编号；K为动车组总数；M为动车组集合；t为计划周期中的时刻，t∈[t0,T]，T为日计划的结束时刻。

1.1 任务节点

(1)

1.2 任务接续有向弧

动车组执行完列车任务后必须执行检修(整备)任务，一般情况下需要在车站进行整备，之后执行后续列车任务。当累计运行里程达到检修规定的里程后，需要在运用所进行一级或二级检修。热备车在运用动车组故障时执行列车任务，执行热备任务的动车组需要定期更换且每隔一段时间内需要进行一次一级检修，以保证热备车良好的运行状态。各任务之间的接续弧分为图2所示的5种类型。

图2 任务之间的接续关系图

(1)入检(整备)接续弧aij∈ANF(i∈VN,j∈VF,φj=0，且满足式(1))，ANF为入检(整备)接续弧集合。

(2)出检(整备)接续弧aij∈AFN(i∈VF,j∈VN,φj=0)，AFN为出检(整备)接续弧集合。

(3)入备接续弧aij∈AFB(i∈VF,j∈VB,φj=0，且满足式(1))，AFB为入备接续弧集合。

(4)出备接续弧aij∈ABN(i∈VB,j∈VN,φj=0)，ABN为出备接续弧集合。

2 基于接续可靠性的运用计划优化模型

2.1 假设和符号定义

为简化问题的复杂性，提出以下合理假设：

(1)研究的动车组运用计划基于给定的运行图，暂未考虑运行图的调整。

(2)动车组运用模式为不固定区段方式，各站之间允许空车调拨。

(3)动车组日计划的制定主要考虑运用检修，运用检修包括一级检修和二级检修。一级检修周期为3 300 ～4 000 km，二级检修周期为27 000 ～30 000 km。本文未考虑其他高级检修，因为高级检修的停时均大于1 d，超过日计划的计划范围，同时日计划主要针对当日可用动车组，进行高级检修的动车组可以在计划前进行排除。

(4)采用最高允许速度为350 km/h的单一型号且编组固定动车组，暂不考虑动车组重联、解编的情形。

(5)列车任务完成后需要检修(整备)时，列车将在当前车站进行检修(整备)。

为方便模型构建，定义如下符号。

Lr,min(Lr,max):r(r=1,2)级检修任务的最小(最大)累计运行里程限制。

2.2 接续可靠性分析与计算

(2)

(3)

根据晚点时间分布和最小接续时间可计算动车组完成列车任务i-j接续的可靠性为

j∈VN,φj=0

(4)

(5)

全部动车组运用日计划由K列动车组的交路段组成，运用日计划的接续可靠性定义为全部交路段可靠性的平均值，计算方法为

(6)

考虑工程方案可行性要求，本文设定任一动车组的交路段接续可靠性均需要满足最低可靠度的要求。

2.3 优化目标与约束条件

基于上述对列车接续可靠性的分析，本文目标函数为动车组运营总惩罚费用最小

(7)

式中：z1为单位计划接续时间对应的惩罚费用，元/min；z2为空车调拨单位运行里程对应的惩罚费用，元/km；z3为单位接续可靠性下降对应的惩罚费用，元。z1和z2通过调研获得。

式(7)第一项表示动车组的计划接续时间总惩罚费用，除了必要的运行时间，计划中的接续时间主要表示动车组的在站等待时间，接续时间越小表示动车组的运用效率越高；第二项表示由空车调拨产生的惩罚费用；第三项表示由接续风险产生的惩罚费用，通过接续可靠性表示接续风险。由于接续可靠性覆盖了全部接续的列车任务，本文假设接续可靠性指标与前两项费用具有同等重要度，因此费用结果具有相同的数量级。

约束条件为

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

2.4 模型求解算法

本文针对所建立的优化模型设计蚁群算法：一只蚂蚁的路径表示一列动车组的运用日计划，所有蚂蚁的路径可表示全部动车组的运用日计划。算法设置最大迭代次数，每一次迭代中，设置时间步长t∈[t0,T]推动计算。根据各弧的转移概率实现列车任务的分配，并根据信息素浓度的变化不断更新转移概率，在系统时间结束时完成一次迭代，需要保证安排全部的列车任务。计算当前代的目标函数值并更新最优方案，之后更新全局信息素并继续迭代，在迭代达到最大次数时终止算法。其中，转移概率公式和全局信息素更新规则采用文献[15]的方法。

上述过程中可以通过接续控制保证约束式(8)～式(16)，为了保证解的可行性，将约束式(17)构造为惩罚函数并加入目标函数

(18)

式中：z4为惩罚系数，由于全部动车组的日计划接续可靠度小于目标要求是不可接受的情形，因此设定惩罚系数z4的数量级为连续接续任务可靠度惩罚系数z3的3倍，以剔除不满足约束式(17)的解。

解空间的构造方法和启发式信息素的设置如下：

(1)构造解空间

Step1初始化变量和参数，按照2.1节生成非列车任务的相关参数和接续条件，设置初始时间为t0、时间步长为1 min。

Step5令t=t+1，如果t≤T，进行Step2，直到t>T，结束算法。

(2)启发式信息素更新

(19)

式中：b为启发式因子重要程度参数。

3 案例研究

本文以某客运专线A、B、C 3站间的动车组运用日计划编制进行案例研究。3站都有配属的动车运用所，且3站间开行AB、AC两条线路的列车，通过调研已知28对列车(编号为1～56)的时刻表、各动车组初始任务(初始列车任务编号首位为0)和3站配属动车组情况、检修能力、晚点分布等基本数据。假设热备任务和检修任务之间的距离(时间)忽略不计，与本文研究直接相关的其他主要参数设置见表1。

表1 案例研究相关参数取值

文本采用MATLAB 2014a实现所设计的蚁群算法，算法中信息素重要程度参数α=1，启发式因子重要程度参数b=10，信息素增加强度系数Q=10 000，信息素蒸发系数v=0.3，迭代代数为150代，多次求解运算后获得结果见表2。

表2中，方案1是未考虑列车接续可靠性的运用方案，方案2是考虑列车接续可靠性的优化运用方案。方案1中交路段可靠性低于50%的交路段有3个，分别是1、3和8号动车组交路段，特别地有交路段1的可靠性非常低，执行这些交路段的动车组在任务到达(完成)晚点时不能正常接续下一列车任务的概率很大；而方案2中不存在接续可靠性低于50%的交路段，一方面全部交路的整体可靠性有所提高，另一方面低可靠性的交路段数量减少，整体上较大幅度地降低了动车组接续的风险。

两个方案的进一步指标分析结果见表3。由表3可知，方案2中已经不存在0～49%的交路段，比方案1减少了3个，而可靠性大于90%的交路段个数增加了7个；两个方案使用的动车组总数没有变化，表明适当提高接续可靠性的优化方案不会额外增加动车组数量。方案2的动车组接续时间惩罚费用比方案1多199 600元，即增加1 996 min的接续时间，主要原因是方案2中部分热备车承担运行任务，而接续时间是以列车任务为基准进行计算的，因此相比方案1会增加较多的接续时间。例如，动车组10、23的初始接续时间之和为1 992 min，说明方案2不会对既有运营条件有较大的影响。方案2的空车里程有所增加，实际上为1个AC方向的空车运行变为1个AB方向的空车调拨。接续可靠度方面，方案2将平均接续可靠性提高了16.74%，从而有效优化了接续风险总惩罚费用和总费用。以上分析表明运营条件基本不改变的情况下提高动车组接续可靠性可以有效避免因为晚点等运行波动造成的运营风险。

表2 考虑列车接续可靠性的运用日计划方案

表3 动车组运用计划优化前后指标对比

4 小结

本文定量分析了动车组运用计划的列车接续可靠性，以总惩罚费用最小建立了运用计划优化模型，设计基于蚁群算法的求解方法，通过算例验证了模型算法。结果表明：考虑列车接续可靠性的动车组运用计划可以减少接续可靠性低的任务接续的数量，虽然会增加空车运行里程和接续时间，但可以有效降低接续风险总惩罚费用。

提高动车运用计划中的列车接续可靠性，减少因动车运用计划未实现而重新调整接续的列车数量，可为优化动车组运用计划提供依据，也能更好地适应运营环境的变化。今后将进一步研究未实现可靠接续的动车组运用计划的优化调整方案。