客运专线动车组交路计划模型研究

杨文韬，周 强

（1. 中国铁道科学研究院 运输及经济研究所，北京 100081；2. 南昌铁路局 运输处，江西 南昌 330002）

动车组交路计划是铁路运输部门根据中国铁路总公司下达的列车运行计划、动车组检修里程及检修基地能力等情况而编制的动车组运用计划。该交路计划决定动车组的使用数量，同时也是影响运营成本及运输组织的重要因素。由于动车组交路计划编制为非确定多项式 NP 问题，存在限制条件多、求解维度大等特点，至今还没有比较满意的算法。为此，在分析动车组交路计划编制特点的基础上，提出基于装箱问题的动车组交路计划编制模型及算法。

1 既有算法概述

目前对动车组交路计划的研究主要基于以下 2种算法，分析其特点如下。

（1）基于先到先发接续算法[1-2]。该算法的思想是在大闭环内的动车组先到先发，然后按照交路的长度进行分割并调整，动车组每次接续的都是当前列车在其所在站所能接续的最早出发的列车。但是随着列车的不断接续，动车组到达某车站时，已经不是最早到达该站的列车，其接续的列车可能应由在其之前到达的列车来接续，若调整时没有考虑这一点，会导致该动车组在非动车段所在站长时间占用到发线。

（2）基于回溯算法的搜索算法。该算法以回溯为主要思想进行可行解的搜索，在每次得到不可行解时，回退前一步并更换选择后继续进行接续，直至完成所有交路。该算法存在以下不足：一是当搜索到后期遇到不满足条件的解时，可能需要对已经获得的序列进行大量调整，降低算法效率；二是该算法同样不能保证动车组交路在非动车段所在站得到满意的接续。

2 列车接续方式分析

基于以上分析，针对动车段所在站和非动车段所在站分别制定接续方式的动车组交路提出计划编制方法。按照编制方法将客运专线上的车站分为 2类：一是非动车段所在站，主要指中间站，一般只办理旅客乘降作业或少量的始发终到列车；二是动车段所在站，是列车始发和终到的主要场所。针对这2类车站分别制定动车组接续方式如下。

（1）在非动车段(所) 所在站的接续方式。客运专线的中间站到发线数量较少，始发、终到列车也较少，到达该站的列车如果不接续最早可接续的列车，将等待很长时间才会出现下一列可接续列车，造成动车组长时间占用到发线。由于中间站一般不配备备用动车组，当到达列车发生晚点时，有可能导致接续的始发列车无动车组可用。为解决这样的问题，有可能采用较早到达的列车在站停留一定时间来预备接续较晚出发的列车，该方法同样也会造成列车长时间占用到发线。对于整个交路计划而言，只要动车组数量不增加，则中间站的接续方式不会影响动车组的总接续时间。因此，在中间站是否考虑使用某列较早到达的动车组担当备用任务，或在站停留多长时间，应根据具体情况由计划编制人员来指定，其余动车组则应尽量采用先到先发的方式接续。

（2）在动车段(所) 所在站的接续方式。由于所有在非动车段(所) 所在站的始发、终到列车都已经确定了接续关系，则可以将所有动车组视为从动车段(所) 始发，以动车段(所) 为终到站。为了使所接续的动车组交路满足检修标准的限制，对该问题建立基于装箱问题的数学模型。考虑到问题的复杂度，主要针对单基地的动车组交路计划进行研究。

3 模型建立

3.1 问题描述

编制动车组交路计划的主要目标是使用最少的动车组数来满足所有运行线需要，并且保证动车组受到检修时间和里程的约束[1-2]。一般来说，动车组检修里程可以在一定范围内波动，但是不能超过检修标准的上限和下限。但在实际运用中，允许少量动车组的走行里程略大于或小于检修标准的下限，同时为提高动车组的利用率设置相应的罚函数，其值随动车组走行里程与检修标准差值的增大而增大。

动车组交路计划的上述特性与装箱问题非常相似，即用最少的箱子完成所有物品的装箱工作，并且所装物品不能超过箱子的容量。为将动车组交路计划的编制问题转换为装箱问题，如图1 所示，对其进行如下处理。

图1 动车组交路计划编制问题向装箱问题转化

（1）将动车组交路计划视为箱子，列车运行线视为待装箱的片状物品(设物品形状与箱子的截面相同)。

（2）列车运行线之间的接续时间视为物品之间的保护层，保护层的最小厚度即为列车接续时间标准。

（3）列车必须按照时间方向接续，因此物品必须正放，而且物品底面代表列车在车站的出发时间，物品顶面代表列车在车站的到达时间。

3.2 定义函数

假定用来装物品的箱子具有以下特性：箱子的容量标准为 C，容许所装物品的总量在 C(1±α)之间浮动(α 为浮动系数，一般取 10%)。但当物品的总量超过C 时，对因超重给予一定的惩罚；而当物品总量没有达到C，但大于浮动下限时，对所产生的箱子能力的浪费也给予一定的惩罚，当所有物品的总重未达到浮动下限时，应对其给予额外的惩罚，惩罚函数设计按下式计算。

式中：F(m) 为惩罚值；M 为一个很大的数；m 为物品的总量；k1为当重量介于容量标准与容量上限之间的惩罚系数；k2为当容量介于容量标准与容量下限之间的惩罚系数；k3为容量低于容量下限的额外惩罚。

3.3 建立模型

目前部分动车组运用计划研究[3]将动车组运用的均衡性作为编制动车组交路计划的第二个目标，该目标虽然会使各交路的累计走行里程与检修标准的差值较均衡，但是会导致较多的交路达不到检修标准。因此，不将交路的均衡性作为目标，而是考虑尽可能多的动车组交路具有较小的惩罚值，即接近或达到其检修标准。由于考虑尽可能多的交路达到检修标准，针对个别交路与检修标准差距较大的情况，当列车发生晚点时可以将这些交路的动车组作为热备车使用，从而减少备用车的数量。综上所述，建立基于装箱问题的动车组交路计划编制问题的数学模型。

式中：z(y)min为最小化动车组的使用数量，即最小化所使用的箱子数；Kmax为最大化满足罚值限制的交路数，即接近动车组检修标准的动车组交路数量；⑴式表示交路中运行线的总走行公里小于交路标准；⑵式、⑶式表示所有的运行线都有且仅有 1 组动车组担当；⑷式表示动车组接续时间大于接续时间标准；⑸式表示动车组进行一级修时的接续时间大于一级修时间标准。其中，yi为动车组序号；ωj为承担运行任务的运行线里程；xij为j动车组担当1条运行线i的任务；eij为j 动车组担当i运行线任务后形成的车站间隔时间；Tjx为动车组在站最小接续时间；Tyjx为动车组在段一级修最小接续时间；Fbz为相关类型动车组检修里程标准。

4 遗传算法设计

4.1 遗传表示

对于装箱问题主要采用基于种群的表示方法。设有以下编码方式表示的列车交路序列[3]，其中染色体的物品部分为 1435234，这标志着第1列车放入交路1，第2列和第 7 列车放入交路 4，第3 列和第6列车放入交路3，第4列车放入交路 5，第5列车放入交路2。染色体的群体部分仅表示交路，这里采用带方括号的数字来表示交路，通过查询交路，可以得到群体名表示含义：[1]={1}，[2]={5}，[3]={3，6}，[4]={2，7}，[5]={4}，如图2所示。

图2 列车交路序列

在图2 中，群体表示有意义的积木块，列车部分仅用于判定由哪些列车形成该群体，按照所属解的期望质量来转运信息。遗传算法的关键之处是利用遗传算子对染色体的群体部分进行操作。

4.2 遗传算子

4.2.1 杂交

基于种群的杂交包含交路和列车 2个部分。因此杂交需要处理可变长度的染色体，该染色体用基因表示交路，步骤如下。

Step 1：随机选择 2个杂交位置，对每个父代选定杂交部分。

Step 2：将第一个父代杂交部分的内容插入到第二个父代的杂交位置之前。由于杂交对染色体的部分群体进行操作，即从第一个父代插入一些群体到第二个父代中。

Step 3：从产生的后代中的原有的交路中去掉所有重复出现的列车，使得这些列车原先的从属关系让位于“新”插入的交路，因而产生的后代中的某些群体发生了改变。

Step 4：如果需要，采用 FF(First Fit) 方法或BF 方法调整新产生的交路。

Step 5：改变 2个父代的角色并重新应用Step 1 — Step 4 生成第二个子代。

杂交过程图如图3 所示。

4.2.2 变异

图3 杂交过程图

变异是指随机删除 1个动车组交路，然后采用FF 启发式方法进行修补的策略。从问题的形式可以看出，惩罚值小的交路接近检修标准，惩罚值大的交路远离检修标准。当惩罚值大的交路被删除时，其产生新解的变化较小，而当惩罚值小的交路被删除时，产生新解的变化较大。因此，采用轮盘赌的方法选择将要进行变异的染色体，染色体被选择进行变异的概率与交路的惩罚值成反比。

4.2.3 适应值函数

基于装箱问题的动车组交路计划编制模型的首要目标是使动车组的使用数量最小化，在降低设备成本的同时最大化接近检修标准的交路数量。建立适应值函数计算公式为

式中：N 为解中使用的动车组数量；Fi(m) 为第 i个交路的惩罚值；Fbz为可接受的罚函数标准；k 为对接近检修标准的交路的重视程度，常数(k>1)，k 值越大，接近检修标准的交路比一般的交路受到的重视就越大，此处 k 取 2。

4.2.4 初始解的构造

装箱问题有 2种产生初始种群的方法：随机方法和启发式方法。随机产生初始解虽然简单，但解的性能不能保证，用 FF 启发式方法产生装箱问题所有的个体也比较容易，同时解的性能与随机产生相比有较大提高。因此，主要采用 FF 启发式方法生成初始解。

5 实例分析

动车组交路计划编制的目标是最小化动车组的使用数量，从而降低设备成本，现以南昌铁路局杭深线福州南动车所动车组所运行的实际交路为实例进行模拟对比。

5.1 杭深线福州南动车所设备及运用情况

福州南动车所设有动车组检查库和存车线，配属 CRH1A 动车组 23 组(图定运用动车 19 组，热备车 1 组，检备车 3 组)，CRH1E 动车组7组(图定运用动车6组，检备车 1 组)。每晚动车组入库一级修18～19 组。在实际运营中，福州南动车所每日使用26 组动车组开行跨局至上海虹桥站、杭州南站和南昌铁路局管内厦门、龙岩站的动车组列车共48对，总运行距离38250km，平均单组动车组运行距离1530km。

5.2 装箱模型计算

模拟程序采用 VS2008 平台下的 Visual C++ 编程语言，按照遗传算法定义染色体和遗传算子并构造初始解，根据适应值函数进行迭代求解。在迭代过程中将交叉概率设置为 0.5，变异概率设置为0.2，经过 20次迭代后发现最优解已经没有变化，所以选择迭代终止。动车组实际运营交路与计算机模拟改进交路对比分析如表1 所示。

由于福州南动车所动车组配属数量及检修能力有限，并且部分开行至上海虹桥、杭州南站的车次运行距离较长。因此，现场实际运用和计算机模拟2个方案在动车组使用数量上没有差别，均为 19 组。在单组动车组运用里程和时间上二者也较为接近，仅在确认列车的开行和最早、最晚 1 趟车次的安排上有较小差别(如 D3109 和 D6257)。虽然计算机模拟结果没有显示动车组运用数量上的节省，但是验证了装箱模型的可行性及遗传算法求解的有效性，模拟迭代产生的动车组运用效率指标分析如表2所示。

表1 实际交路与模拟交路对比表

表2 动车组模拟交路运用效率指标分析表

通过计算机模拟，得出动车组运行距离总计为31 102km，平均单组动车组运行距离为 1 636km，计算机模拟动车组的运行效率略高。从与实际交路完全相同的动车组计算机模拟运用效率指标来看，部分动车组利用效率较低，非生产时间超过 500min，等待服务和检修的时间也都接近400min，其中运用效率指标最差的 3 组动车组分别是 D3207(上海虹桥 11:05 — 厦门北19:58) 接续D6256(厦门北 21:13—福州22:55)、D3203(上海虹桥10:22—厦门19:19) 接续 D6252(厦门19:47—福州21:55) 和 D3209(上海虹桥 10:27—厦门北19:40) 接续 D6250(厦门北20:00—福州21:45)，造成该状况的主要原因是没有从整个路网的角度考虑动车组的运用问题。由于动车组的配属问题导致其跨局服务频率较低，而过早入段或过晚出段也极大地影响了动车组的运用效率。建议从全路动车组运用的角度进行优化，将上海虹桥站早上 10 点后的动车组发车时间提前 2～3h，这样下午到达厦门的车底还可以套跑南昌铁路局管内的短交路，而晚上 20 点前到达上海虹桥站的车底也可以继续套跑上海铁路局管内的短交路，从而能够最大程度优化动车组使用效率。

6 研究结论

动车组交路计划是典型的非确定多项式 NP 问题，获得其最优解比较困难。通过提出在编制动车组交路计划时区分考虑动车段所在站和非所在站，采用装箱问题进行建模及采用遗传算法进行求解。由于现场数据规模有限，以杭深线上的福州南动车段交路为例进行了计算机模拟计算，如果求解对象是覆盖若干条线路及地区枢纽站的小规模路网，则其动车组的运用条件会更加复杂，求解空间的维度也会更大，从而对算法的求解效率和收敛速度提出更高的要求。因此，如何加入更多的实际限制条件对模型进行完善并求解还有待进一步研究。

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

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

[3]吴庄胜，赵 清，王伯铭. 高速列车运用检修及动车段的设计研究[J]. 西南交通大学学报：自然科学版，1997，32(2)：277-282.