编组站到发线运用计划优化的研究

姚宇峰

(中国铁道科学研究院集团有限公司通信信号研究所，北京 100081)

0 引言

编组站作为保障铁路安全有效运输的关键基层单位，承担了铁路货物运输环节的多项核心工作，包括但不限于列车接车作业、货物列车的解体和编组作业以及列车发车作业等。阶段计划作为整个车站工作计划的重要组成部分，既是对日班计划分阶段的工作细分，也可以有效指导车站工作人员完成日常的排班工作，提高工作效率。由于编制计划时考虑的相关因素较多，如何编制高效、高质量的编组站阶段计划一直都是众多学者的研究课题。

国内专家学者针对阶段计划自动编制的理论进行了一系列的研究。杨颖[1]研究了编组站固定设施和不同方向车流对编组站能力的影响以及编组站内部设备的均衡性对编组站接发车能力的影响；黄俊生等[2]提出以使用均衡性、列车到达不确定性、技术作业时间弹性、带重叠时间窗等为约束，带柔性重叠时间窗编组站终到列车到发线应用的优化模型；徐永梅等[3]分析了编组站综合自动化系统大数据平台的构建和典型应用；徐晶等[4]通过对影响铁路客运站到发线因素的分析建立整数规划模型，研究并提出求解该模型的启发式排序规则和禁忌搜索算法相结合的优化算法；康山松[5]对编组站到发线运用中的股道占用、咽喉占用资源冲突问题进行了研究，提出以行车设备的均衡利用和最小缓冲时间的长短为目标的数学模型；赵蕾[6]通过对编组站集群资源进行分析，提出对实体资源划分多个节点，结合资源边际效用情况引入了资源可用度的评价指标；易娇等[7]探讨了编组站阶段计划自动编制时存在的典型问题并分别针对到发线运用、调车机车运用和取送车运用进行了建模；高雪等[8]提出了基于启发式算法对编组站到发线运用问题进行研究的思路；李涛等[9]研究建立客运站到发线运用优化模型，采用模拟退火遗传算法求解实现到发线设备固定使用、均衡使用及保证行车作业安全的优化目标；李涛等[10]研究建立客运站到发线运用优化模型，采用改进的遗传算法求解实现列车占用到发线时间最小和到发线运用最均衡的优化目标；何林等[11]建立高速铁路车站到发线运用的0-1 规划模型，采用遗传算法求解实现上下行列车股道的均匀分配；孙波等[12]提出一种应用于机器人路径规划的遗传算法优化思路。

考虑到编组站现场实际作业的多样性、复杂性、随机性、突发性等特点，现阶段很难单独依靠计算机来进行阶段计划的全自动编制，仍旧需要人机结合来实现。为了尽可能弥补人工编制计划的不足，更合理地使用站内的相关资源，研究提出一种编组站到发线运用计划的优化模型与算法，在综合考虑编组站的实际作业情况、资源使用情况、资源冲突情况等多项约束条件下，利用启发式算法寻求一个可行的优化解，重点解决现阶段到发线运用计划中到达场股道资源分配特定场景下的资源优化问题，从而使得特定资源如股道的使用分配更为合理。

1 到发线运用计划

编组站到发线运用计划作为编组站阶段计划的核心工作之一，其主要任务是在综合考虑编组站的布局情况(参考车站布置图)、计划接发列车的数量、接发列车的性质、接发列车的密集度、站内车辆解编技术的作业过程、作业方式、作业时间等多种因素的基础上，制定出阶段计划内所有到发列车占用到发场线路的具体计划，规定所有到发列车占用到发线的具体时间段，并支持计划的快速调整，最终保障车站能够完成按计划接车、列车准点发车和避免或尽量减少列车线路交叉等多个计划任务，实现阶段计划内合理运用到发线的目标，提高编组站的运行效率。

到发线运用的基本分配原则如下。

（1）同一时间段内一列列车只允许占用一条到发线。

（2）同一时间段内一条到发线上只允许一列列车占用。

（3）到发线属性必须满足列车限制条件，如超限车限制、到发线长度限制。

（4）到发线的使用应尽量符合车站的相关规定。

（5）到发线的运用计划应提高抗干扰能力，在满足到发线能力的前提下，应考虑最大化列车作业占用行车设备的缓冲时间。

（6）到发线的既有行车技术设备应尽量均衡地使用，对于确定的列车运行图和车站既有行车设备的利用率应趋于均衡。

2 数学模型

为了利用编组站的有限资源来实现计划的自动编制，评测效果的优劣，需要把到发线运用计划涉及的关联资源统一定义成模型表示，并进一步基于模型规则来求解输出编制好的计划。模型符号定义如表1所示。

表1 符号定义Tab.1 Symbol definition

股道占用约束条件如下。

（1）一趟车次作业周期内只能占用一条股道，作业中途不能更换股道，即

（2）作业时间有冲突的2 趟车次不能占用同一条股道，即

（3）超限车次只能占用可容纳超限车次的股道，不能占用常规股道，即

优化目标为使得股道资源使用更均衡，各股道占用时间方差最小，即

该目标评价车次使用股道资源的均衡性，好的到发线运用计划应该使得各股道的资源占用尽量保持均衡，而不是只集中占用某些股道。

3 算法设计

铁路编组站到发线运用优化问题属于多约束条件组合优化问题，随着问题规模(如接发车辆、股道数量、限制约束条件)的增大，搜索空间可急剧增大，使用常规的算法很难求出最优解，退一步求次优解来部分解决现有的问题较为可行，在当前流行的启发式优化算法[8]中，遗传算法(Genetic Algorithm，GA)[5]是其中的佼佼者。遗传算法借鉴了自然界生物进化的选择和遗传机制，模仿生物的优胜劣汰思路来进行多群体、多参数的优化，较适用于用常规搜索算法难以解决的复杂非线性问题。鉴于问题领域的特定场景，研究采用改进的遗传算法来进行问题求解。遗传算法流程如图1所示。

图1 遗传算法流程Fig.1 Flow chart of genetic algorithm

（1）编码。研究采用自然数方式编码基因，按照车次占用到发线股道的先后顺序依次排列，则基因xj表示列车j占用的股道编号，编码简单，可读性好便于对应解空间。个体P可表示为基因x的序列，如[x1，x2，x3，…，xn-1，xn]，典型的个体P编码实例如[108，101，110，…，106，109]，其中j的取值范围为1～n，表示车次的先后自然排序编号，xj的取值范围为车场股道的编号。

（2）生成初始种群。随机产生若干个体P，其中符合股道占用约束条件的予以保留，不符合的则进行淘汰，确保符合要求的个体数量满足种群数量的参数要求即可。

（3）定义适应度函数。适应度函数f作为遗传算法中个体优劣的评判准则，通常同目标函数Z一致，用来保障适应度较高的个体有较大机率遗传到下一代。若求解目标函数最大值时，则目标函数可直接作为适应度函数f=Z，若求解目标函数最小值时，则变换公式为f=M-Z，其中M为大的正整数。

（4）选择操作。研究采用适应度最大值选取法，每一轮选择操作中，计算种群内个体的适应度数值并按照大小排序，依次选择前K个(选择参数阈值)适应度较高的个体，而非采用传统的轮盘赌选择法。将选择出来的父代个体直接作为子代个体予以保留，然后利用选择的这些父代个体进行交叉及变异操作生成新的子代个体，最终保持种群规模数量不变。这样可以较为快速地筛选出符合股道占用约束条件的解，淘汰掉不符合的无效解。

（5）交叉操作。研究采用均匀交叉基因点的方法，依次选取2条父染色体，然后随机产生一个[0，1]区间的均匀分布序列，其长度与父染色体长度一致，根据随机数的大小(交叉概率阈值)且交换后的相邻基因符合股道占用约束条件来交换2 条父染色体对应位置的基因，从而生成2 条子染色体，而非简单基于概率交叉。这样可以尽力保障生成符合股道占用约束条件的有效解。

（6）变异操作。研究采用随机变异基因点的方式选取染色体的变异位置(设定变异点个数、变异概率阈值)。为了提高解空间的搜索速度，达到快速局部收敛的目的，变异的值从可行解的待分配股道(符合股道占用规则，不会发生资源冲突)中随机选取。

（7）停止准则。通过设置最大迭代次数，同时观察适应度函数的变换曲线，综合评判选取最优解。

4 实例研究

研究选取某编组站某一天的典型运行数据来进行实例分析。该编组站的布局为双向三级六场纵列式编组站，其中下行到达场车场的编号为一场，其中配备有14 条股道，编号分别为101—114，均可用来接发列车，其中101，106，107，108，111 号股道为超限股道，支持容纳超限车次。

下行到达场某一天接车作业计划如表2 所示(股道占用开始、结束时间已由车流推算系统计算得到)。其中，序号分别为69，71，75 的3 趟车次为超限车次，车次号分别为45908，41071，22165，目前分配的股道分别为106，101和107。

表2 下行到达场某一天接车作业计划Tab.2 Schedule of pick-up operation on a certain day at the downward arrival site

续表

基于该站一天的接车作业计划数据，计算当天车次股道占用时间冲突矩阵F如表3所示。

表3 车次股道占用时间冲突矩阵FTab.3 Track occupation time conflict matrix F

通过遗传算法进行求解，种群规模设置为30，选择参数K设为16，即每轮保留约一半染色体，交叉概率Pc设置为0.95，变异点个数为2，变异概率Pm取0.05，迭代次数100，目标优化函数为Z(股道占用时间方差最小)，适应度函数为f=100-Z，且规定如果解空间不符合股道占用约束条件则适应度为0。适应度函数变化曲线如图2 所示，目标优化函数变化曲线如图3所示。

图2 适应度函数变化曲线Fig.2 Fitness function curve

图3 目标优化函数变化曲线Fig.3 Objective optimization function curve

由图2、图3 可知，种群个体在迭代了大约85 代时，适应度函数达到了平衡状态。得到目前较优的股道分配新方案[106，113，108，110，105，104，101，103，109，111，113，102，101，108，114，105，112，113，109，107，103，111，112，104，105，113，108，106，102，110，114，111，112，109，106，102，110，105，107，101，108，103，111，104，102，109，114，113，110，112，105，108，107，106，104，103，109，114，113，111，106，110，103，107，104，109，102，111，108，107，106，114，102，113，107，105，110，111，107，102，114，112，104，101，106，103]。其中超限车次45908，41071，22165 分配的新股道为108，106，107。

由图2、图3 可以看出，股道分配新方案较之原有的股道分配方案，股道占用时间方差较小，股道占用时间更均衡，新旧股道分配方案股道使用时间对比如图4所示。

图4 新旧股道分配方案股道使用时间对比Fig.4 Comparison of track utilization time between old and new track distribution schemes

此时得到的股道分配方案仍然可能是一个局部最优解，这是由于遗传算法本身的局限性导致的。但是，针对目前的编组站来说，此解具备可行性，可以在一定程度上解决现阶段股道资源均衡使用的问题。通过在真实场景的验证表明优化设计经受住了实践的考验，取得了良好的应用效果。

5 结束语

编组站到发线运用属于典型的NP-C 问题，目前缺乏单一的优化算法。通过借鉴国内的最新研究成果，结合编组站的实际布置情况和工作中面临的实际问题，采用计算机辅助手段对编组站到发线运用中的到发场股道分配问题进行研究和分析，提出一种自动优化模型与算法，并在真实场景下进行了模型验证和测试，效果明显。由于编组作业的复杂性和应用场景的特殊性，建设一个高效的智能编组站难度很大，除了在算法和模型上不断探索和改进，还需要硬件设施、人员、多方系统的相互配合。提高编组站作业的智能化水平绝不是依靠一个单一的系统就能解决的问题。以现实为依托，深入了解编组站日常作业的难点与痛点，合理地规划计算机与人员的分工，不断改进和完善到发线运用自动化系统，可以更为有效地提高和改善编组站作业效率和作业质量。