基于禁忌搜索算法的铁路客运站到发线运用计划编制研究

徐晶，李季涛

(大连交通大学 交通运输工程学院，辽宁 大连 116028)*

铁路客运站的到发线运用是铁路行车技术作业的重要作业之一，合理有效的使用到发线是提高车站通过能力和车站作业效率的重要途径，同时建立客运站到发线运用模型及设计相应算法是实现铁路客运站作业自动编制的重要内容.基于此，不少专家和学者对到发线的运用进行了研究.刘杰等以作业计划稳定性强和接发车进路条件优为目标建立多目标优化模型，运用改进的带精英策略的非支配排序遗传算法(NSGA-Ⅱ)对模型进行求解[1].彭其渊等人以列车运行晚点和车站作业秩序影响双方面最小化为目标,建立了混合整数线性规划模型.还以列车加权总晚点时间与到发线使用费用之和最小为优化目标建立线性0-1规划模型，运用分支定界法和模拟退火算法求解[2-3].黄俊生等人构建了带柔性重叠时间窗编组站的终到列车到发线应用优化模型，并用模拟退火算法求解[4].江秀等人建立了满足到发线固定使用方案和到发线均衡使用的多目标二次0-1规划模型，运用LINGO软件进行求解[5].乔瑞军等人以列车在站内走行时间最短和到发线均衡运用为优化目标，并运用LING软件求解[6].史峰等人将一端咽喉区接发车进路排列方案与列车权重等级相结合建立了综合优化模型，运用了模拟退火算法求解[7].王保山等人提出了到发线平均利用率，并以其建立到发线均衡运用模型，运用遗传算法求解模型[8].张苏波等人将列车占用到发线的权值最小、到发线的均衡运用与旅客乘降方便系数相结合建立了整数规划模型，并运用遗传算法进行求解[9].基于此，本文提出运用启发式排序规则和禁忌搜索算法相结合的优化算法来研究到发线的运用.

1 问题描述与分析

在铁路车站作业计划中，列车对到发线的占用不仅和列车性质及到发密集度有关，还和车站的设备设施关系密切.到发线运用方案的目标是保证车站不间断的接发旅客列车，避免列车的不必要的等线，保证出发旅客列车能够正点发出，以提高车站的通过能力.故在实际作业中，到发线的运用要满足以下约束条件，这里假设客技库线容量足够大.

(1)一列旅客列车在同一时间片内只能占用一条到发线，一条到发线在同一时间片内至多被一列旅客列车占用；

(2)同一到发线的相邻到发的两旅客列车的作业时间应满足其最小间隔时间；

(3)两列或多列旅客列车之间进路存在交叉干扰时，应安排平行进路；

(4)到达旅客列车与到达旅客列车使用靠近同一个站台的两条到发线时，应满足其最小间隔时间；

(5)到达旅客列车和出发旅客列车使用靠近同一个站台的两条到发线时，应满足其最小间隔时间；

(6)具备旅客换乘关系的旅客列车尽量安排停靠在同一站台的到发线；

(7)接入到发线的旅客列车应满足接入的到发线的有效长约束；

(8)有上水作业需求的旅客列车必须接到有上水设备的到发线；

(9)为了保证旅客进出站的安全，通过列车应尽量安排在正线上.

2 模型分析与建立

2.1 模型的建立

将1d或一个阶段计划或自定义的一个时间段的时间划分为B个列车密集到达和出发程度不相同的时间，即划分为B个时间片，处于同一时间片的列车在占用到发线的时间上存在着交叉干扰，不能使用同一条到发线[10].定义列车为m，且m∈T{1,2,…,M}，M为旅客列车数量.定义到发线为g，且g∈U{1,2,…,G}，其中G为到发线条数.Wm为列车等级权重，规定列车等级越高的列车Wm取值越小.Xmg为0-1变量，当Xmg=1时表示列车m占用到发线g，反之则不占用.将旅客列车占用到发线的时间表示如下：

Tm为旅客列车占用到发线的全部作业时间；t1为旅客列车准备接车进路的时间、信号开放时间和列车通过进站点距离的时间；t2为旅客列车出发时刻至其完全排空股道并可接入下一旅客列车的作业时间；t3为旅客列车在到发线停留时间(可根据旅客列车的出发时间-到达时间、入库时间-到达时间或出发时间-出库时间求出)；

则有

Tm=t1+t2+t3

(1)到发线固定使用方案

该目标是在遵循到发线的固定使用原则上，使车站不间断接发旅客列车，以确保车站的正点率.所以该目标是达到使所有旅客列车对到发线占用消耗最小，同时保证了不同等级和种类列车接入到发线的优先程度.

(1)

(2)均衡运用行车技术设备即均衡的运用到发线

为了达到各到发线空费时间均衡，本文运用各条到发线的占用时间与到发线的平均占用时间之差的平方和最小来衡量到发线的均衡运用度.

(2)

(3)方便旅客的旅行

对于铁路客运站来说，其服务对象便是旅客，所以提高旅客的服务质量对于铁路客运部门是极其重要的，所以该目标函数以平均旅客走行距离最短为优化目标，从而提高旅客服务质量.Nm是第m列旅客列车乘降旅客数，Dg是第g条到发线旅客乘降站台离基本站台的距离.

(3)

2.2 约束条件

(1)一列旅客列车在同一时间片内只能占用一条到发线

m∈T(1,2,3,…,M)

(4)

(2)一条到发线在同一时间片内至多被一列旅客列车占用

g∈U(1,2,3,…,G)

(5)

(3)同一到发线的相邻两旅客列车的作业时间应满足其最小间隔时间

(6)

(4)两列或多列旅客列车之间进路存在交叉干扰时，可安排如下平行进路约束

Pmgm′g′≥XmgXm′g′Rmm′

(7)

Rmm′为当旅客列车m和旅客列车m′在咽喉区进路占用上存在交叉时取1，反之取0.Pmgm′g′为当旅客列车m和旅客列车m′在咽喉区进路产生交叉干扰并可以为其安排平行进路时取1，反之取0.

(5)到达旅客列车与到达旅客列车使用靠近同一个站台的两条到发线时，应满足其最小间隔时间

(8)

(6)到达旅客列车和出发旅客列车使用靠近同一个站台的两条到发线时，应满足其最小间隔时间

(9)

(7)具备旅客换乘关系的旅客列车尽量安排停靠在同一站台的到发线

(∀m,m′∈T,g,g′∈U)

(10)

Hgg′为当到发线g和g′靠近同一站台时取1，否则取0.Qmm′为当旅客列车m和m′具有换乘关系时取1，否则取0.

(8)接入到发线的旅客列车应满足接入的到发线的有效长约束

(11)

Lg为到发线g的有效长；lm为旅客列车m的长度.

(9)有上水作业需求的旅客列车必须接到有上水设备的到发线

(12)

Ts为需要上水作业的旅客列车集合；Us为有上水设备的到发线集合；b为有上水需求的列车总数.

(10)为了保证旅客进出站的安全，通过列车应尽量安排在正线上

m′∈Vm(1,2,3,…,m)

(13)

Z(g)为客运站正线集合；Vm为通过列车集合.

2.3 多目标优化模型

(14)

(15)

(16)

(17)

(18)

(19)

Pmgm′g′≥XmgXm′g′Rmm′

(20)

(21)

(22)

(∀m,m′∈T,g,g′∈U)

(23)

(24)

(25)

(26)

3 算法设计

本文建立的铁路客运站到发线运用模型属于非线性的0～1整数规划模型，直接求解此模型存在着较大的困难，故在结合到发线和旅客列车之间的关系基础上采用启发式排序规则与禁忌搜索算法相结合的优化算法求解模型.

3.1 启发式排序规则生成初始方案

运用禁忌搜索算法求解对初始解的质量要求较高，初始解的质量的好坏决定了最终优化方案的优劣程度.启发式排序规则是根据车站行车作业的长期实践经验、技术作业标准构建的一组行车作业安排优先级的决策规则.遵循这些规则，逐一安排每列旅客列车的行车作业，便可构造出一个确定性的可行解.其决策规则如下：

(1)旅客列车的到达时间或出发时间的确定规则

由列车运行图或车站列车时刻表确定.

(2)列车进路选择规则

若两列或多列旅客列车之间进路存在交叉干扰时，则应根据进路的最小占用时间间隔进行安排.

(3)旅客列车股道占用安排规则

股道和列车的唯一性规则；若两列旅客列车使用同一到发线则其到达时间或出发时间应满足其最小安全间隔时间；若到达列车与到达列车(出发列车)使用靠近同一站台的到发线时则应满足其最小安全时间间隔；到发线的长度应满足旅客列车的长度；若两列旅客列车存在换乘关系则应安排在靠近同一站台的到发线；若是通过列车则应安排在正线上.

依据以上决策规则生成如下旅客列车占用到发线的初始方案步骤：

Step1 初始化行车作业所需的各设备参数

列车类型(普速旅客列车、高速旅客列车)，旅客列车的到达与出发的时间，股道和道岔以及它们之间的联系，进路的最小间隔时间、同一到发线使用的最小间隔时间以及靠近同一站台的到发线使用最小间隔时间，到发线及旅客列车的长度；

Step2 生成普速旅客列车集合和高速旅客列车集合；

Step3 本文对5∶00～10∶00这一时间段的旅客列车按小时进行编排.即对5∶00～6∶00，6∶00～7∶00，7∶00～8∶00，8∶00～9∶00，9∶00～10∶00时间段的旅客列车进行到发线占用的安排.首先对5∶00～6∶00这一时间段的到发旅客列车进行到发线的分配；

Step4 检索在高速旅客列车集合中是否存在着在该时段内的旅客列车，若存在则在列车选择进路规则与股道占用规则基础上优先安排在靠近站舍侧的到发线，若没有则检索普速旅客列车在这一时间段内的旅客列车并按时间、列车进路选择规则及股道占用规则对其进行分配；

Step5 对6∶00～7∶00时间段内旅客列车进行到发线分配，转Step4；

Step6 对7∶00～8∶00时间段内旅客列车进行到发线分配，转Step4；

Step7 对8∶00～9∶00时间段内旅客列车进行到发线分配，转Step4；

Step8 对9∶00～10∶00时间段内旅客列车进行到发线分配，转Step4；

Step9 检索普速旅客列车集合和高速旅客列车集合，若集合不为空，则转Step3；若集合为空则输出初始方案.

3.2 禁忌搜索算法

禁忌搜索算法是局部邻域搜索算法的推广，是人工智能在组合优化算法中的一个成功应用.它的一个重要思想是标记已得到的局部最优解，并在进一步的迭代中避开这些局部最优解.[11]它的主要参数包括邻域结构、评价函数、禁忌长度、藐视准则和终止准则，下文将具体设计这些参数.

(1)编码方式

本文求解到发线运用最优方案的核心问题是确定到达或出发的每列旅客列车所占用的到发线，使得最终的优化方案能够满足列车和到发线的相关技术及理论约束条件.基于禁忌搜索算法的特点，将所研究时间段以小时进行分段，进而将每小时内的旅客列车两两进行移动交换形成解的邻域，其每小时段编码序列如图1所示.其中每一个小长方形代表一条到发线，以左边第一个为靠近站舍侧依次排列，用g表示，m1,m2,…,mn表示旅客列车，这样的编码方式为后续操作奠定基础.

图1 每小时段编码序列

(2)邻域和候选集结构

通过移动或交换每小时段的两旅客列车位置产生邻域解，在邻域解中选出部分较优的解以构成候选集，也可以将所有的邻域解作为候选集，但由于其搜索范围大且操作时间过长所以一般不采用.

(3)评价函数的构造

评价函数是用于判断邻域解的优劣性，本文将目标函数作为评价函数，根据文章的目标函数将评价函数设定为：

f=αZ1+βZ2+γZ3

(27)

式中,Z1,Z2,Z3是子决策目标，α,β,γ是子决策目标的权重系数且α+β+γ=1，依车站实际工作经验将α设为0.4，将β,γ设为0.3.

(4)禁忌表的设置

(5)选择策略

当新解计算得到的评价函数的值比原解对应的评价函数值小，则将此新解作为本次迭代的邻域最好的解.用公式表示如下：

(28)

式中,l为当前解，l1为选出的邻域最优解，s(l)为候选解集，f1(s(l))是s(l)的评价函数值.

(6)藐视准则

为避免最优解的丢失，规定了在找不到邻域解及迭代一定次数后特赦禁忌表中的最优值作为当前解以继续迭代搜索.若禁忌表中的某值出现频率超过某设定值时，则在迭代中若找不到邻域解时可将其从禁忌表中解禁作为当前解来继续搜索最优解.

(7)终止准则

本文设置最大迭代数作为算法的终止条件.

在对禁忌搜索算法的各参数分析的基础上，设计的具体算法步骤如下：

Step1 将启发式排序规则生成的初始方案作为本算法的初始解，并赋予禁忌表H=Ø；

Step2 对初始解中的旅客列车对到发线的占用分解成若干个小时段，并以每小时段中的列车占用到发线为研究对象；

Step4 判断禁忌表H中的对象是否满足藐视准则，若满足则将此对象加入到候选集中，再从候选集中选出最优解作为当前解，若不满足藐视准则，则在候选集中选出最优解作为当前解，更新禁忌表H；

Step5 迭代次数加1，如果迭代次数为设定的最大迭代次数Tmax或解无法改进时，算法终止，输出此时的最优方案，否则转Step3.

按此算法分别求出对研究时段内的若干个小时段内的旅客列车对到发线的占用最优方案或较优方案，若保证每一小时段内的旅客列车占用为相对最优方案，那么即可得到研究时段内的最优方案或较优方案.最终的优化方案由于是分段求解所得，所以在合并后的解中可能存在相邻时间段内的旅客列车时间上的冲突，故再根据同一到发线的两相邻列车到达或出发的最小间隔时间进行调整，最终得到问题的最优解.

4 算例分析

某客运站站场平面图如图2，其中实线9、8、Ⅶ、5 是接发上行旅客列车的到发线，实线4、3、Ⅱ、1是接发下行旅客列车的到发线，黑色实心圆点表示此处设有客车上水栓，即9条到发线均可满足旅客列车的上水作业.该站共有8个站台，9条到发线，其中编号为Ⅱ和Ⅶ的到发线为正线，编号为6的到发线为机车走行线故不接发旅客列车作业.规定使用靠近同一站台的两到达旅客列车的到达时间应满足的最小间隔时间为10 min、到达旅客列车与出发旅客列车使用靠近同一站台的到发线时应满足的最小间隔时间为10 min、同一到发线相邻两旅客列车的最小间隔作业时间为5 min.

图2 站场平面图

本文以该站5∶00～10∶00到发的29对旅客列车为研究对象编制此时段车站到发线运用计划，其到发时刻表如表1.将运用启发式排序规则得出的5∶00～10∶00时间段的初始解进行分割，分割为5∶00～6∶00，6∶00～7∶00，7∶00～8∶00，8∶00～9∶00，9∶00～10∶00共五个时间段的旅客列车对到发线的使用情况，再运用禁忌搜索算法分别对每一时间段进行求解，在求解过程中针对每一时段的初始解的实际情况具体考虑是否将靠近站舍侧的编号为1的到发线上的旅客列车固定不动，其它旅客列车按算法要求进行计算.其中，禁忌搜索算法参数的设置如下：最大迭代次数Tmax取50，在计算时段内的旅客列车n分别取7，7，4，7，4，则其禁忌长度分别取5，5，2，5，2，由于n较小故候选集取整个邻域解.

表1 5∶00～10∶00时间段旅客列车到发时刻表

基于以上数据，采用MATLAB软件对设计的禁忌搜索算法进行程序的开发，通过对各时段的算例求解并用人机结合的方法对算法求得的方案进行调整，得到最终优化方案如图3所示和图定方案与原方案的旅客列车对到发线的占用的比对图，如表2.

图3 到发线运用计划图

表2 到发线占用

通过对车站作业的大量观测，取准备接车时间和旅客列车进路走行时间即t1及准备发车时间和旅客列车尾部越过到发线上出站信号机的时间之和即t2均为30 s，得到旅客列车占用到发线时间如表3所示.

表3 到发线占用时间

基于图3到发线运用计划图、表2到发线占用和表3到发线占用时间，本文定义到发线利用率为αq，下述表达式(16)中Time(t,q)表示Tq中的列车t占用到发线q的时间，d表示计算时段时间，取5∶00～10∶00即取300 min.

(16)

经计算得到该站在5∶00～10∶00时间段内到发线利用率如表4所示.分析表4得出以下几点，首先到发线2、3、4、5、7、9的利用率分别提高了15.17%、1.17%、16.17%、5.00%、3.00%、17.16%，尤其是到发线2、4、9的利用率有了显著提升.但到发线1和8分别降低了11.66%和35%，其中到发线8下降比较明显，原因为在图定方案中运用到发线8接发的旅客列车Z82占用时间长达185 min，优化方案将其安排在远离站舍侧的到发线9上，这符合旅客服务质量的要求；其次，与图定方案相比，优化方案的到发线利用率更加均衡，避免了图定方案中到发线8和9的突出性，符合到发线均衡运用的原则；最后，从图3到发线运用计划中可知，到发线1上接发的旅客列车均为等级较高的旅客列车，同时远离站舍侧的编号为8和9的到发线接发的旅客列车相对较少，也符合对旅客服务质量的要求.综上，尽管到发线1和到发线8利用率降低了但就总体而言到发线利用率还是有所提高，同时各到发线的利用率更加均衡，并且能够达到旅客服务质量的要求，证明了文章算法的有效性.

表4 到发线利用率

5 结论

本文建立了满足约束条件的铁路客运站到发线运用的0～1整数规划模型，提出了将启发式排序规则和禁忌搜索算法相结合的优化算法求解模型，并以某铁路客运站5∶00～10∶00时间段到发的旅客列车为例对模型和算法进行验证.验证结果优于车站人员凭工作经验编制的到发线运用计划，并且编制时间较短，灵活性较高.但由于算法的分段求解再整合为最终解，故存在相邻时间段列车冲突现象，此时要人为的对其调整，所以下一步将对这一情况进行具体分析，以进一步提高算法的适用性.