双线铁路通过能力图解计算方法研究

2020-02-28褚文君

铁道运输与经济 2020年1期

褚文君

（中国铁道科学研究院集团有限公司运输及经济研究所，北京 100081)

1 铁路通过能力计算图解法

1.1 图解法分类

图解法是计算铁路线路通过能力的常用方法，通过实际编制列车运行图来确定线路在规定时间内最大可以开行的列车数，从而得到线路的通过能力[1]。对于图解法而言，采用的运行图编制技术是决定其计算效果的关键。根据编图技术的不同，既有的研究和实践中所用的图解法可以分为3 类，即人工图解法、模拟图解法和数学规划图解法[2]。

（1）人工图解法。早期的运行图编制主要依靠人工完成，由编图人员依据经验决定每条列车运行线的铺画位置。而能力计算的人工图解法则是通过人工铺画运行图满图来确定线路通过能力。

（2）模拟图解法。随着计算机技术在铁路运输领域的广泛应用，计算机模拟人工编图过程的方法被应用于运行图的编制。该方法以人工编图的策略和经验为依据，生成计算机判别准则，并通过这些准则对计算机编图过程进行控制，模拟人工编图全过程。这种图解法在一定程度上避免了个人编图经验的偏差对编图质量的影响。因此，在这种编图方式下，图解计算方法的准确性得到了一定程度的保证。胡安洲等[3]通过模拟图解法对双线自动闭塞区段旅客列车扣除系数进行研究，提出运用计算机模拟图解法进行列车扣除系数标定的具体思路。杨肇夏[4]在市郊和摘挂列车运行图铺画理论方法的基础上，研发能够模拟铺画最大列车运行图的计算机交互系统，运用此系统进行双线铁路通过能力分析与扣除系数的测算。赵丽珍[5]利用既有的计算机模拟编图软件对高、中速列车混跑条件下高速铁路通过能力进行图解分析，得出有停站高速列车相对于无停站高速列车、中速列车相对于无停站和有停站高速列车的扣除系数，并分析双线铁路区间通过能力随中速列车数量变化的趋势。徐意[6]基于以列车旅行时间最小化为目标的启发式分解算法，研发单线区段列车运行图计算机模拟铺画系统，利用该系统对提出的“虚拟限制区间法”的各项参数进行标定，以计算单线区段通过能力。贺涛[7]借鉴已有研究成果，开发双线铁路运行图模拟铺画系统，并运用该系统对兰新线武威南至张掖区段不同速差方案下的通过能力进行图解计算。

（3）数学规划图解法。计算数学的不断发展使大规模优化问题的高效求解成为可能，在这种情况下，有学者开始从优化模型构建的角度对运行图编制问题进行研究，许多有效的运行图编制模型与算法被相继提出。在此基础上，优化编图的思路被应用到通过能力的图解计算中。孟令云[8]在构建运行图优化铺画模型并运用LINGO 求解的基础上，通过测试不同列车开行数量下模型是否有可行解来确定线路的通过能力。张红斌等[9]构建客运专线运行图加密整数规划模型，设计基于OD 奖励值的贪心分步算法进行求解，实现运行图加密计算客运专线通过能力。

上述方法中，人工图解法较难对运行线间的耦合关系进行统筹分析，由于编图人员的经验存在差异，编制得到的运行图质量参差不齐，图解计算的准确性难以保证。基于模拟编图的图解计算方法在效率和准确性方面有较大提升，但其考虑的因素和采用的规则仍有较大局限性，在一定程度上制约其在通过能力图解计算中的应用，既有的研究更多地是用其标定分析计算法的参数。基于数学规划的图解方法理论上可以实现最准确的能力计算，但由于缺乏有效的优化求解算法，此类方法的研究和应用仍然比较少见。因此，提出一种基于数学规划的双线铁路通过能力图解计算思路，以时间跨度最小化为目标，构建运行图优化的析取图模型，并设计遗传算法求解，以得到的满图运行线数量作为双线铁路能力计算结果。

1.2 图解法计算思路

无论是人工图解法、模拟图解法还是数学规划图解法，既有的通过能力图解计算都是将铺画时间域看作是约束条件，在此约束下寻找运行图铺画的可行解。将铺画时间域看作优化的目标函数，给定初始的运行线铺画数量，以时间跨度最小化为目标，求解双线铁路运行图优化编制模型，得到在当前运行线铺画数量下双线铁路运行图的最小时间跨度，判断运行图最小时间跨度是否大于规定的时间域，如果是(或否)，则逐渐增加(或减少)运行线铺画数量，直至运行图最小时间跨度小于(或大于)规定的时间域时止，输出当前(或前一次)运行线铺画数量作为双线铁路通过能力。双线铁路通过能力图解计算流程如图1 所示。

图1 双线铁路通过能力图解计算流程Fig.1 Graphic calculation flow of capacity of double track railway

2 双线铁路运行图优化问题建模

根据图解法计算思路，以时间跨度最小化为目标的运行图优化编制是实现图解计算方法的关键。运用析取图(Disjunctive Graph)建模方法构建模型，设计相应的遗传算法进行求解，形成以时间跨度最小化为目标的双线铁路运行图优化编制方法。

2.1 问题描述

假设双线铁路上、下行方向的列车运行互不干扰，以时间跨度最小化为目标的双线铁路运行图优化编制问题可以描述为：给定双线铁路特定方向上待铺画的列车集合，列车在各个双线铁路区间相应方向上的运行时分和在各个车站的最小停站时间均已知，各个车站的出发和到达间隔时间已知，在不考虑列车间缓冲时间的条件下，合理安排列车在各个双线铁路区间相应方向上的运行次序及在各车站的到发时刻，使运行图的时间跨度最小。

问题参数定义如下：Q为列车集合；i，j为列车编号；k为双线铁路区间和车站编号(按列车运行方向依次编号)；n为双线铁路区间数量，对应的车站数量即为n+ 1；ti,k为列车i在第k个双线铁路区间的运行时分；为列车i在第k个车站的最小停站时间；为双线铁路区间k相应方向列车到达追踪间隔时间为双线铁路区间k相应方向列车出发追踪间隔时间，k= 1，2，…，n；T为运行图铺画时间跨度。

2.2 双线铁路运行图编制析取图模型

析取图是作业车间调度问题(Jop Shop Problem，JSP)研究中常用的建模方法，是一种特殊的赋权有向图G= (V，A，E)，其中，V为节点集，通常包括所有工序对应的节点以及起始节点、终止节点2 个虚设节点；A为合取弧(又称连接弧)集合，是连接同一工件相邻工序的有向弧，用以表示该工件的工艺顺序；E为析取弧集合，是连接在同一台设备上进行的2 个工序的有向弧，用以表示这2 个工序进行加工的先后次序。析取弧的方向待定，建模时通常用1 对方向相反的弧来表示1 条析取弧。无论是合取弧还是析取弧，都具有一定的权值(以起始节点为起点的合取弧除外)，用以表示该弧起点对应工序的加工时间。在析取图模型中，通过为每条析取弧指定1 个方向(即在模型中每个析取弧对中选择1 条析取弧)，可使该析取图转化为普通的有向图，如果得到的有向图中没有回路存在，则此图可以表示1 个可行的调度方案，各节点与起始节点之间最长路径的长度即为该节点对应工序的最早开始时间。因此，在析取图模型中，优化车间调度方案问题等价于为图中每条析取弧选择合适的方向，使得到的无环有向图在给定的指标上达到最优。

将列车看作1 个工件，列车在双线铁路区间的某个特定方向上的运行过程看作1 个工序，构建双线铁路运行图编制析取图模型如下。

公式 ⑵ 给出析取图的节点集，0S和tS分别为虚设的起始和终止节点，Oi,k为工序节点，表示列车i在双线铁路区间k上的运行过程。公式 ⑶ 和 ⑷ 分别给出析取图的合取弧集和析取弧集，每一条弧都是由三维向量来描述，前2 个元素分别为该弧的起始节点与终到节点，第3 个元素为该弧的权值。公式 ⑶ 的合取弧集中存在3 类有向弧，分别为（1）连接起始节点与各趟列车第一个工序节点的弧，此类弧不对应列车运行过程，因而权值为0；（2）连接各趟列车前后相邻工序对应节点的弧，此类弧的权值等于其起点对应列车区间的运行时分与列车在前方车站的最短停站时间之和；（3）连接各趟列车最后一个工序节点与终止节点的弧，此类弧的权值即为对应列车在其最后一个区间的运行时分。公式 ⑷ 中析取弧连接相同区间不同列车的工序节点，其权值表示不同列车驶入区间的最小间隔时间，既应满足后方车站发车间隔时间要求，又应满足前方车站到达间隔时间要求，因而取和两者之中的较大值。

基于以上析取图，以时间跨度最小化为目标的运行图编制问题可转化为确定图中每个析取弧的合理方向(即在每个有向弧对中选择1 条)，使图中起始和终止节点间的最长路径L(S0，St)最短，因而决策变量定义如下。

xi,j,k为0-1 变量，表示是否存在由节点Oi,k到节点Oj,k的有向弧。

图中析取弧只用于连接不同的工序节点，即

同时，同一双线铁路区间对应的不同工序节点间应当有且只有一条有向弧，以表示它们的先后关系，即

此外，应避免出现死锁现象，选择得到的有向图必须是无环的，以保证对应的铺画方案可行，即

目标函数可以表示为

3 双线铁路运行图优化遗传算法

借鉴作业车间调度问题遗传算法的设计思路，设计基于析取图的双线铁路列车运行图优化算法。

3.1 编码与解码

采用基于工序的编码方式，设计染色体为列车编号组成的序列，序列中每个列车编号出现的次数等于该列车对应工序的数量(即经过双线铁路区间的数量）。解码时，按照染色体中列车编号出现的顺序依次确定列车的各道工序，即可以得到其对应的无环有向图的拓扑排序。染色体编码与解码方法如图2 所示。

图2 染色体编码与解码方法Fig.2 Chromosome coding and decoding

3.2 适应度计算

析取图模型的目标函数是令图中起始节点S0与终止节点St间的最长路径长度最小，选择操作采用比例选择法，将染色体的适应度定义为其对应的无环有向图中起止节点间最长路长度的倒数，即

其中，L(S0，St)可以采用拓扑排序法计算，具体流程如下。

步骤1：初始化。对染色体进行解码，得到对应无环有向图的拓扑排序；令所有工序节点与起始节点间最长路长度为0，即= 0，∀i，k；令迭代参数g= 0。

步骤2：令g=g+ 1，得到拓扑排序中第g个节点

步骤3：更新拓扑排序中g之后第一个与节点对应列车相同的节点的最长路径长度，令其等于节点的最长路径长度与相应合取弧的权值之和，即

步骤4：更新拓扑排序中a之后所有与节点对应区间相同的节点的最长路径长度，令其等于节点的最长路长度与相应析取弧的权值之和，即

步骤5：如果g等于染色体长度，则得到图中起始节点和终止节点间的最长路长度为

否则，返回步骤3。

3.3 遗传操作设计

（1）选择操作采用比例选择法。通过适应度值确定当前种群中各个染色体被选择的概率，随机选择出父母个体。

（2）交叉操作采用线性次序交叉。针对选择操作得到的父染色体，随机产生一个列车编号，保留父染色体中该列车编号对应的所有基因位，其余基因位清空，然后保持所保留基因位相对位置不变，整体向左或向右随机移动一定距离，得到一个子代原型；然后将其余列车编号按照在母染色体中的相对顺序依次加入子代原型的空基因位中，生成1 个完整的子代个体；重复上述过程，生成第2 个子代个体。线性次序交叉操作如图3 所示。

（3）变异操作采用位置变异。从染色体中随机选择2 个位置，然后交换这2 个位置的值。

图3 线性次序交叉操作Fig.3 Linear order crossover operation

此外，为保证算法的收敛性，进化过程结合使用最优保存策略，即当经过以上遗传操作得到的子代种群中，最优个体的适应度劣于父代种群中的最优个体时，用父代种群中的最优个体替换子代种群中的最差个体。

4 算例分析

以一个包含10 个车站的双线铁路区段下行方向为例，对前文提出的运行图编制方法及通过能力图解计算思路进行验证。已知该线路上开行2 种速度等级的列车，各等级列车在双线铁路区间下行方向运行时分如表1 所示。

表1 各等级列车在双线铁路区间下行方向运行时分Tab.l Operation time of all level trains in the downward direction of double track railway

高等级列车有2 种开行方案，各等级列车的停站方案设置如表2 所示，低等级列车的停站不作要求。此外，各个车站下行方向列车出发和到达间隔时间均为4 min。

表2 各等级列车的停站方案设置Tab.2 Station stop scheme of all level trains

基于以上设定，可以按照速度等级和停站方式的不同，将此区段下行方向开行列车分为3 类，各类列车在双线铁路区间下行方向的运行图参数如表3 所示。

表3 各类型列车在双线铁路区间下行方向的运行图参数 minTab.3 Scheduling parameters of all kinds of train in the downward direction of double-track railway

4.1 双线铁路运行图编制算法分析

设定第Ⅰ、第Ⅱ、第Ⅲ类列车的开行数量依次为10，20，30，运用图解计算方法确定最优的铺画方案。算法通过C#语言编程实现。遗传算法参数设置如表4 所示，遗传算法计算过程如图4 所示。

表4 遗传算法参数设置Tab.4 Parameter setting of genetic algorithm

由以上计算过程得到，运行图的最小时间跨度为349 min。

4.2 双线铁路通过能力分析

在以时间跨度最小化为目标的运行图优化编制的基础上，进一步分析上述双线线路下行方向的通过能力。规定运行图中有效的铺画时间域为 600 min，区段通过能力使用600 min 内可以铺画的列车数量来表示。

（1）单类列车最大开行数量计算。将第Ⅰ和第Ⅱ类列车开行数量分别设为15 和25，运用运行图编制方法得到运行图时间跨度随第Ⅲ类列车数量的变化如图5 所示。由图5 可见，600 min 有效铺画时间域内第Ⅲ类列车的最大铺画数量为49。基于这种方法，可以计算对任2 类列车数量固定情况下，第3 类列车的最大开行数量。

图4 遗传算法计算过程Fig.4 Calculation process of genetic algorithm

图5 运行图时间跨度随第Ⅲ类列车数量的变化Fig.5 Variation of scheduling time horizon with the number of train Ⅲ

（2）列车扣除系数分析。以第Ⅲ类列车为基准列车，对第Ⅰ和第Ⅱ类列车的扣除系数进行量化分析。首先，计算得到平行运行图条件下给定时间域(600 min)内可以铺画第Ⅲ类列车的最大数量(103列)；然后，在给定第Ⅰ或第Ⅱ类列车开行数量的情况下，计算第Ⅲ类列车的最大铺画数量；在此基础上，以第Ⅲ类列车减少铺画的数量除以第Ⅰ或第Ⅱ类列车的开行数量计算第Ⅰ或第Ⅱ类列车的扣除系数，得到第Ⅰ、第Ⅱ类列车扣除系数变化情况如图6 所示。

由图6 可见，随着开行数量的增加，2 类列车的扣除系数均总体呈现先上升再下降的趋势。对于第Ⅰ类列车，其开行数量在10 ～ 25 列时，对于第Ⅲ类列车铺画的影响最为明显，扣除系数一直维持在1.4 左右；当其开行数量超过25 列以后，扣除系数逐渐减小。第Ⅱ类列车对于第Ⅲ类列车铺画的影响更为显著，当其开行数量在10 ～ 35 列时，扣除系数一直在1.6 左右；开行超过35 列后，扣除系数逐渐减小。上述分析说明，列车的扣除系数在一定程度上受到其自身开行数量的影响，因而以固定的扣除系数计算通过能力会导致存在一定的误差。

（3）基于帕累托最优的线路通过能力描述。在铺画时间域给定的情况下，3 类列车的最大铺画数量存在此消彼长的关系，因而可以用3 类列车铺画数量的帕累托最优集来描述线路的通过能力。上述通过固定2 类列车开行数量计算第3 类列车最大铺画数量的方法所得到的结果可以看作帕累托最优集中的一个非支配解，在此基础上，可以进一步求解所有类型列车开行数量的帕累托最优集。

首先，固定第Ⅰ类列车的开行数量，对第Ⅱ类列车不同开行数量下第Ⅲ类列车的最大铺画数量进行计算，得到第Ⅱ、第Ⅲ类列车开行数量的帕累托最优集。第Ⅰ类列车开行数量为15 情况下，第Ⅱ、Ⅲ类列车开行数量的帕累托最优集如图7 所示。

进一步地，对第Ⅰ类列车不同开行数量下第Ⅱ和第Ⅲ类列车开行数量的帕累托最优集进行求解，得到3类列车开行数量的帕累托最优集如图8所示。