考虑计划分配优先级与干扰条件的编组站阶段计划自动编制研究

何占元，许展瑛，姚宇峰，蒋继磊

(1.国能朔黄铁路发展有限责任公司 运输部，河北 沧州 062350；2.中国铁道科学研究院集团有限公司 通信信号研究所，北京 100081)

0 引言

编组站作为铁路运输网络车流集散中心，是铁路枢纽及干线畅通的关键节点，承担了铁路货物运输环节的多项关键工作，包括但不限于货物列车接发车作业、解编作业、检修作业及装卸作业等。阶段计划自动编制与动态调整作为编组站综合自动化系统的核心技术，计划编制质量的好坏直接关系到货物车辆中停时，从而直接影响铁路运输效率[1]。编组站阶段计划基本编制流程如图1 所示。现阶段，编组站阶段计划编制仍然以人工编制为主，编制周期长、出错率高，且调整不便。对此，如何高效编制编组站阶段计划为众多学者所研究的课题。

图1 编组站阶段计划基本编制流程Fig.1 Basic preparation process of stage plan of marshalling station

针对编组站阶段计划的动态调整，张岩[2]研究提出了包括时间预测、动态车流推算、计划调整、计划实施、实时信息采集反馈等步骤的阶段计划动态调整流程，并建立了基于作业过程用时精准预测的动态车流推算模型。宋宇[3]研究了我国编组站运输调度工作存在的问题，从硬件结构、软件结构、系统功能和系统流程4 个方面为切入点设计了编组站运输调度自动化系统。马亮等[4]提出了阶段计划的自动调整算法并进行验证。黎浩东等[5]分别对确定条件下和不确定条件下的阶段计划编制及阶段计划计算机编制与实现的研究现状进行了综述。杨颖[6]以编组站的实际工作为研究重点和核心，从编组站综合能力的角度出发，以编组站能够充分利用各设施设备的能力为目标进行了一系列的深入研究。赵军锋[7]基于新丰镇编组站运输组织现状，研究分析制约车站运输能力提升的客货列车混跑、点线能力不协调、驼峰设备缺陷等主要因素，进而从线上扩能、点上扩能、管理扩能等方面提出运输组织优化对策。赵蕾[8]研究了编组站资源的可用度计算方法，根据可用度的计算原理给出编组站资源可用度的计算方法及步骤，并进一步构建了编组站解编计划耦合优化模型。刘俊[9]在分析了铁路运输调度高质量发展实践成效和经验启示的基础上，研究提出铁路运输调度指挥高质量发展优化策略。张明[10]借鉴博弈思想，对站内调机和分配车流进行协同优化，研究建立编组站调机运用与配流协同优化模型，验证了编组站阶段计划自动编制、自动调整的系统方案。王琦[11]研究提出确定环境下的阶段计划优化模型，引入了延误系数进行模型的补充完善，以列车平均待解时间最大和在站停留时间最短为目标进行了模型求解。

考虑编组站现场实际作业的随机性、复杂性及突发性等特点，如遇到实际列车晚点、临时调度命令下达等事件，会造成已编制好的计划不能正常实施，人工调整较为耗时耗力。且现阶段完全基于计算机进行阶段计划的全自动编制很难实现，仍考虑人机相结合的方式来实现。对此，基于阶段计划中到发线运用计划的自动编制和计划变动时到发线运用计划的自动调整2 方面，以适度降低现阶段人工编制计划的工作量为切入点，建立一种编组站到发线运用计划编制模型，并设计考虑股道优先级与股道干扰权重最小原则实现到发线运用计划的自动编制。同时，编组站到发线运用计划编制系统可实时跟踪计划的实际执行情况，当到发线实际占用情况与原计划不一致时，系统可根据算法中的调整原则实现到发线运用计划的自动调整。

1 自动编制

1.1 应用场景

针对实际现场应用场景利用计算机辅助技术研究编组站到发线运用计划自动编制系统，根据车流状况、调机剩余能力及到发线空闲能力，包括但不限于实现以下功能：①出发计划后的到发线自动分配功能；②阶段计划中确认接车顺序后自动分配到达计划的到发线功能；③系统接收到实际作业情况同计划不一致时自动调整相关到发线运用计划的功能；④作业人员对到发线运用计划进行人工干预时自动调整相关到发线运用计划的功能；⑤系统接收施工计划时对到发线进行自动占用标记等功能。上述功能的实现可有效提高到发线运用计划的编制效率。

1.2 到发线分配原则

作为编组站阶段计划的核心工作之一，编组站到发线运用计划的主要任务是在综合考虑编组站场型布局、接发列车的数量、种类、解编技术作业的过程、时间等多种因素的基础上，制定出阶段计划内所有到发列车占用到发场线路的具体计划和具体时间段，实现合理运用到发线的目标，提升运输生产效率。

在实际工作中，到发线运用的分配原则如下[12]。

（1）一条到发线同一时间段只能接发一列列车，直至列车离去。

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

（3）同一到发线接发相邻到发列车的时间间隔要满足最小安全时间间隔要求。

（4）到发线属性必须满足接发列车条件，如超长、超限列车等。

（5）指定到发线的计划在作业时间段内不可更改到发线。

（6）到发线运用计划编制应分类处理。除考虑到发线列车占用情况，还需要因考虑施工计划、调机走行、减轴车辆等产生的占用情况，大体归为2类：①可调整的到发线占用。包括到发列车、调机走行的到发线占用等；②不可调整的到发线占用。包括施工计划、停放机车影响的到发线占用等。

1.3 计划编制与调整

按照计划应用场景，可将到发线自动编制系统功能具体划分为计划编制和计划调整两大功能。

（1）计划编制功能。到发线运用计划编制功能主要用于新增到达、出发列车计划、施工计划等，新增时存在多个计划同时提交，计划编制时分类按序编制。编制顺序遵循先编制不可调整计划，后编制可调整计划，避免可调整计划抢占不可调整计划到发线资源，具体流程如下。①循环编制不可调整的到发线占用计划。②循环编制可调整的到发线占用计划。

（2）计划调整功能。针对已编制完的计划进行调整，分为自动调整和人工调整。自动调整主要考虑随着计划的执行，实际站场运用情况可能与计划有所偏离，为保证后续计划的可用性，需根据到发线实际占用情况进行动态调整。人工调整需考虑的是到发线占用计划的规则检查与受到影响后的后续计划调整。具体流程如下。①接受到发线实际占用信息时，对比原到发线占用计划，当到发线占用信息不一致时，将原到发线占用计划更新为实际占用的到发线，到发线占用结束时间延用原计划的占用结束时间，并筛选出移动后有冲突的到发线占用计划重新进行编制。②到达/出发计划实际占用股道出清时，应删除当前到发线占用计划。③人工对计划调整时，若与不可调整到发线占用计划冲突且禁止调整或存在其他异常情况，应筛选出有冲突的占用计划重新进行编制。

2 模型设计

为有效利用编组站资源，将到发线运用计划自动编制时所涉及的关联资源进行统一定义，模型符号定义如表1所示。

表1 模型符号定义Tab.1 Model symbol definition

目标函数：若原计划无法正常实施，对计划进行调整时应尽量降低原股道运用计划的波动性，即减少股道调整次数，即

股道占用约束如下。

（1）任务分配股道满足超限规则，即当=e，满足≤。

（2）股道占用唯一性：作业时间内有冲突的列车不应占用同一条股道，即∀Te，Tf∈T，当则

（3）占用同一条股道的前后2 项任务，需满足后项任务的股道占用开始时间与前项任务的股道占用结束时间之差不小于最小安全间隔时间，即当则

（4）依据股道干扰值、优先级加权最小值原则分配股道，对于任务Tj任意2条编号为p和q的待选股道，首先计算股道p的加权值，获取任务优先级=k，则股道p的加权值Wp的计算公式为

式中：FI(p)为股道p的干扰值函数，计算公式为

式中：FC(i)为当前任务与已分配任务占用股道i的重叠时间；干扰因子Iip、优先级Pkp通过查表可得。同理，计算股道q的加权值。

根据结果评判，若WPWq，则=q。

（5）股道占用均衡性：以每条股道占用时间总和与各股道平均占用时间之差的标准差来表示，即

式中：Ej为股道占用均衡性系数，既有研究表明股道占用均衡系数越小，股道占用均衡性越好；反之越差。

3 算法分析

按照计划的优先顺序依次对计划进行到发线占用分配。分配应遵循以下规则。①不可调整的到发线占用计划优先级高于可调整的到发线占用计划。②占用开始时间早的计划优先级高于占用开始时间晚的计划。③有限制条件的计划优先级高于无限制条件的计划。④冲突时优先度高的计划可以抢占优先度低的计划资源。⑤到发线占用冲突的计划重新进入到发线分配流程进行再次编制。

（1）初始化。①初始化股道配置参数(是否超限、股道有效长等)。②初始化股道之间干扰值矩阵。③初始化股道优先级矩阵。

（2）循环处理待分配计划。①按照优先规则对待分配计划列表进行排序。②依序处理不可调整计划，判断是否有冲突，若无冲突可直接分配到发线；若存在冲突，冲突对象是不可调整到发线占用计划时，标识本计划为冲突计划，如果冲突对象是可调整到发线占用计划，将冲突对象占用解除并推入待处理占用计划列表，为本计划分配到发线，直至所有不可调整计划分配完毕。③依序处理可调整计划，查询可分配且无冲突的到发线，依据优先级和干扰值加权平均最小原则分配到发线，如所有可分配到发线都有冲突，在所有冲突对象中查找占用开始时间大于本次分配计划开始时间并且冲突干扰最小的到发线，然后解除找到的冲突对象的到发线占用并推入待处理占用计划列表，为本计划分配到发线，直至所有可调整计划分配完毕。④输出已分配计划，同时标识冲突计划，等待人工审核。

调整计划分配方案如图2所示。

图2 调整计划分配方案Fig.2 Adjustment of plan allocation scheme

（3）求解算法。铁路编组站到发线运用优化问题属于多约束条件组合优化问题，使用常规的算法很难在多项式时间内求出最优解，可考虑利用萤火虫优化算法(Firefly Algorithm，FA)来解决。萤火虫算法通过模拟萤火虫个体之间的相互吸引从而达到寻优的目的。

萤火虫算法主要包含亮度和吸引度2 个要素。亮度体现了萤火虫所处位置的优劣并决定其移动方向，吸引度决定了萤火虫移动的距离，通过亮度和吸引度的不断更新，从而实现目标优化[13]。从数学角度对萤火虫算法的主要参数进行以下描述。

①发光强度。如果求解的是最小值问题，则处于空间xi(xi，1，xi，2，…，xi，d)的萤火虫的发光强度Ii的计算公式为

式中：f(xi)为当变量为xi时的目标函数值。

如果求解的是最大值问题，则处于空间xi(xi，1，xi，2，…，xi，d)的萤火虫的发光强度Ii的计算公式为

②两只萤火虫之间的距离。第i只萤火虫与第j只萤火虫之间距离rij的计算公式为

式中：xi，k为第i只萤火虫空间坐标xi的第k个分量；d为问题的维数。

③吸引力。萤火虫的吸引力计算公式为

式中：r表示这只萤火虫与另一只萤火虫的距离；β0是常数，表示最大吸引力；γ为光吸收系数。

④萤火虫位置的更新。如果第j只萤火虫的光强度大于第i只萤火虫的光强度，那么第i只萤火虫就会被吸引，第i只萤火虫的空间位置xi也会发生变化，xi的计算公式为

式中：α∈[0，1]为步长因子；rand是均匀分布在[0，1]之间的随机数；xi，xj为萤火虫i，j所处的空间位置。

算法步骤如下。

①初始化算法基本参数。设置萤火虫数目n，最大吸引度β0，光强吸收系数γ，步长因子α，最大迭代次数M。

②随机初始化萤火虫的位置，计算萤火虫的目标函数值作为各自最大荧光亮度I0。

③计算群体中萤火虫的相对亮度I和吸引度β，根据相对亮度决定萤火虫的移动方向。

④更新萤火虫的空间位置，对处在最佳位置的萤火虫进行随机移动。

⑤根据更新后萤火虫的位置，重新计算萤火虫的亮度。

⑥当达到最大搜索次数，则转下一步；否则，搜索次数增加1，转第3步，进行下一次搜索。

⑦输出全局极值点和最优个体值[14]。

萤火虫算法流程图如图3所示。

图3 萤火虫算法流程Fig.3 Flow of firefly algorithm

4 应用效果

选取某编组站一个班次413列(到达218列，出发195 列)列车进行3 种方式(人工分配，不考虑股道间干扰的自动分配，考虑股道干扰及加权优选的自动分配)的到发线分配操作，基于萤火虫优化算法，辅以计算机技术将其嵌入到现有的编组站系统中进行求解，对操作次数及操作时长进行比较，不同方式下的调整次数如表2 所示，不同方式下的调整用时如表3所示。

表2 不同方式下的调整次数次Tab.2 Statistics of adjustment times in different ways

表3 不同方式下的调整用时 minTab.3 Statistics of adjustment duration in different ways

由表3 可知，通过计算机辅助可大幅减少作业人员人工分配、调整计划方案次数及编制到发线运用计划的工作时长，且在考虑股道干扰和加权优选方案的情况下，需人工做计划调整的数量有明显下降，实验结果表明，该模型其作业效率比常规未考虑股道优先级和股道干扰条件的自动编制方案作业效率提高近2倍，比人工编制方法效率提高近4倍。上述模型及算法已成功应用在某编组站的运输调度自动化系统，实现到发线分配作业计划系统自动编制。通过现场试验验证表明系统满足了现场应用需求，可大幅降低场站作业人员劳动强度，提高作业效率，取得了良好的运用效果。

5 结束语

编组站到发线运用问题作为一种多约束条件组合优化问题[15]，目前缺乏固定的优化算法。对此，结合编组站实际布置情况及工作中面临的具体问题，将影响到发线运用计划分配优先级条件与干扰条件融入到发线占用资源分配优化模型中，基于萤火虫优化算法，并辅以计算机技术将其嵌入到现有编组站系统中进行模型有效性验证及测试，模型效果显著。考虑到编组站作业流程复杂，作业过程涉及的资源种类多，建设一个高效、智能的编组站除了需要软件层面优秀模型及算法支撑外，还需要完善的硬件基础设施，更需要多个系统间相互协调配合才能实现。因此，结合编组站运用实际需求，对阶段计划自动编制软件不断完善改进，才能够不断提升编组站作业效率和质量。