铁路客运站到发线运用优化研究

李 涛，韩建鹏

LI Tao, HAN Jianpeng

（兰州交通大学 交通运输学院，甘肃 兰州 730070）

0 引言

为了更好地完成运输任务，客运站必须严格按照本站的作业计划进行作业，而阶段计划是车站作业计划的核心，是对班计划的分阶段部署，也是编制调车作业计划的主要依据[1]。到发线的合理运用是客运站行车作业的一项重要内容，是车站编制阶段计划的关键工作之一。因此，建立铁路客运站到发线运用优化模型并且设计相应的算法进行求解，对客运站编制到发线运用计划有非常重要的 意义。

为了高效、合理地运用到发线，保证接发车作业的安全，许多学者对到发线的运用优化进行了研究。吕红霞等[2]根据客运站作业的特点建立了客运站到发线运用的0-1 规划模型，基于最小最大蚂蚁的思想，设计蚁群算法对问题求解。高建[3]结合旅客列车在客运站的作业特点，以出发旅客列车正点为目标，同时考虑到发线的固定使用方案及高等级列车优先，建立了客运站到发线运用的混合0-1 整数规划模型，运用模拟退火算法进行求解。何林等[4]以均衡、合理运用到发线为原则，建立了高速铁路客运站到发线运用的0-1 规划模型，采用遗传算法求解。谢楚农等[5]通过分析客运站旅客列车到发技术作业，把研究问题分为方便旅客乘降、保证行车作业安全、有效使用车站既有设备3 个子目标，建立到发线运用优化模型，采用分枝定界算法对模型进行求解。林志安等[6]以行车交叉干扰最小、方便旅客乘降、均衡使用到发线为优化目标，建立到发线运用优化的整数规划模型，设计了基于捕食策略的禁忌搜索算法对问题进行求解。吴鹏等[7]以到发线的固定使用、均衡使用到发线、旅客走行距离最短为优化目标，建立多目标0-1 规划模型，利用功效系数法将多目标同一量纲转化为单目标函数，利用LINGO 软件进行求解。青学江等[8]建立了区段站到发线运用优化模型，采用遗传算法进行求解。虽然模型考虑了多个方面，但是算法运行时间为25min，不能满足算法实时性的要求。张英贵等[9]引入时间窗、权重、有限度3 个参数和柔性理论，建立车站到发线运用的柔性模型，求解采用解改进策略和人—机交互式算法。Kroon 等[10]在已知车站布局和列车到发时间的前提下，从安全角度出发，将问题看成是节点装箱问题，建立整数规划模型，运用特定的预处理规划减小可行性问题的实例大小，采用动态规划的方法进行求解。目前，上述研究大部分是针对技术站到发线的运用研究，而对客运站到发线运用的研究相对较少，考虑在吕红霞等[2]、高建[3]、何林等[4]研究到发线固定使用方案的基础上兼顾到发线的均衡使用，同时引入惩罚因子并改进适应度函数来提高运行效率、加快模型收敛的速度。为了更好地实现车站作业智能化和算法的实时性，在谢楚农等[5]、吴鹏等[7]、青学江等[8]研究的基础上采用模拟退火遗传算法对问题进行求解。

1铁路客运站到发线运用优化模型构建

1.1 问题描述

随着列车运行速度和列车等级的提高，列车运行图不断调整，列车开行密度增加，并且在车站的技术作业时间减少，为了按时按点的接发旅客列车，必须编制良好的作业计划，而到发线的运用又是客运站行车作业的一项重要内容。到发线的运用优化问题是一个具有时间和空间二维特性的组合优化问题[11]，其合理运用不仅关系车站的正常运输生产和运行图的实现，还关系到铁路行车安全和列车运行的经济效益。对一个客运站来说，到发线运用计划是规定车站在某一阶段内到发场线路的具体使用计划，为了方便车站值班员接发列车，到发线一般固定使用。到发线的运用要保证客运站可以不间断地接发列车，最大限度地利用车站每一条线路的能力，同时也得留有一定的余地，避免高峰时段由于一列列车晚点而不能为其后列车安排进路，使其后列车在进站信号机外停车等线。如果某一时段列车到达强度超过车站的接发车能力或出现早晚点情况，这时将不能再按固定方案使用到发线，应该按到发线的备用方案接发列车，将等级相对较高的列车和早点的列车接入满足时间安全间隔的线路。尽量按照《车站行车工作细则》规定的固定方案接发列车，减少行调作业交叉。所有占用到发线的列车都应遵循以下条件。

（1）同一时间内一条到发线只可以接或发一列列车或不接列车。

（2）一条到发线一旦被某一列列车占用，直到出发，该列车中途不得转到另一条到发线上。

（3）先后占用同一条到发线的2 列列车，必须满足接发列车的最小安全时间间隔要求。

1.2 模型构建

设某客运站到发线的集合为D= {1，2，…，j，…，m}，其中j为第j条到发线的编号，m为到发线的总数；计划阶段到达客运站的列车集合L= {1，2，…，i，…，n}，其中i为第i列列车到达车站的顺序，n为列车总数。目标函数从缩短旅客列车在到发线的停留时间和均衡使用到发线2 个方面考虑(用每条到发线占用时间总和与各到发线平均占用时间之差的方差来衡量)。

式中：xij为0-1 变量，xij= 1 表示列车i占用到发线j，否则xij= 0；tki为列车i开始占用到发线的时间；tei为列车i完全离开到发线的时间；为第i列列车占用到发线的总时间为信号员或值班员为第i列列车排列进路以及列车完全停靠在到发线上所耗费的时间[5]；为列车从完全停靠在到发线起至出发时刻止，列车在到发线上所耗费的时间；为列车从出发时刻起至该列车完全离开该径路止所耗费的时间[5]。根据车站作业标准，和均取2min，由列车的到达时刻和出发时刻确定)；cij为列车i占用到发线j的权值大小，其权值的确定与吕红霞[11]确定方法类似。

模型的约束条件如下。

（1）同一时间内一条到发线只可以接或发一列列车或不接发列车。

（2）一条到发线一旦被某一列列车占用，直到出发，该列车中途不得转到其他到发线上。

（3）同一条到发线上接发相邻列车时须满足最小安全时间间隔的要求[11]，最小安全时间间隔如图1 所示。

图1 最小安全时间间隔Fig.1 Minimum safe interval

具体约束如下。

式中：T为前后两列列车占用同一条到发线时，后续列车i+ 1 接车时刻与前车i完全离开该股道的最小安全时间间隔，文中T值取10 min。

（4）交叉的疏解[12]。在同一个时间片[2]内，接发列车的进路不能有冲突(如列车的接发与机车出入段的交叉)，应多组织平行作业来减少交叉干扰，具体约束如下。

式中：当列车i占用到发线j时与作业p产生交叉干扰时hijp= 1，否则取hijp= 0。

（5）如果存在换乘的列车，应尽可能将其安排在相邻的站台上[13]，具体约束如下。

式中：为0-1 变量，= 1 表示到发线j与到发线j′相邻，共用一个站台，反之则在不同站台[13]；为0-1 变量，= 1 表示列车i与列车i′存在换乘关系，反之则不存在[13]。

（6）行包作业量大的列车应接入靠近有行包通道的站台。

式中：Hi,B= 1 为列车有行包、邮政作业，反之Hi,B= 0；Sj,B= 1 为到发线靠近行包、邮政通道，反之，Sj,B= 0；M取值为10。

2案例求解算法

在实际生产中，出于对车站生产指挥的需要，因而对算法的实时性要求较高。而到发线的运用优化已被证明属于NP 完全问题[14]，对该类问题的求解目前还没有确认的多项式时间算法，因而增加了求解的难度，故此类问题多采用启发式算法求解。虽然遗传算法拥有强大的全局最优解搜索能力，但局部搜索能力差，容易造成早熟，不能保证算法快速收敛；模拟退火算法具有较强的鲁棒性，其以一种概率的方式进行搜索，局部搜索能力强，但把握搜索过程的能力不强，过程中还会遗失最优解，从而使模拟退火算法的能力不高，因而采用模拟退火遗传算法来提高运行效率和求解质量。

2.1 模拟退火遗传算法的关键步骤

（1）染色体编码。染色体的长度由车站到发线的数量确定，对车站在编制计划阶段到达的旅客列车按时间先后进行排序，用空格表示列车，空格对应的下标为相应列车的编号，空格中的数字表示所占股道。

（2）适应度函数的选取。适应度函数求取的是极大值，并且适应度函数要非负。根据实际问题来考虑目标函数的取值，并且在目标函数中加入惩罚系数，然后把处理后的目标函数作为该算法的适应度函数，使求解过程中2 列及以上列车在一个时间片内占用同一到发线的个体以较小的机会生存 下来。

式中：fm(x)是当前输入空间的个体最大值；E[f(x)]是目标函数的均值；这里用fm(x)和E[f(x)]之差的欧式范数再加上E[f(x)]作为Cmax的取值；C为惩罚系数，当有2 列及以上列车在一个时间片内占用同一到发线时，C= 1，否则C= 1 / 1 000。

（3）初始温度的选取 。生成初始种群pop(0)后，设该种群中最大的目标函数值为fmax，最小目标函数值为fmin。初始温度t0由t0= -Δf/ lnnc确定，其中-Δf=fmax－fmin，nc为初始接受概率，0 ＜nc＜ 1，如nc= 0.8，nc= 0.9 等。

（4）温度下降方法 。用tk+1=λtk来控制整个算法的终止，其中tk是前一状态的温度。模拟退火遗传算法的最终温度为1 且最大迭代次数超过给定的次数U。给定一个比较小的ε和U，当温度tk≤ε且l＞U时，算法终止。

2.2 算法流程

步骤1：给定种群大小popsize，k= 0；初始温度tk=t0，随机产生群体pop(k)并检验解的可行性；求各解的适应度F(s)，并找出最优适应度F(s*)，最优解s*=s。

步骤2：进行选择、交叉、变异操作，并检查解的可行性。

步骤3：计算最优适应度F(s*)与新解所对应适应度的差ΔF，然后根Metropolic 准则判断是否接受新解，如果ΔF≥0，则接受s作为新的解；如果ΔF≤0，以概率接受s作为新的解。判断l≤U是否满足，如果满足，转步骤2；如果不满足，转步骤4。

步骤4：tk＜ε是否满足，如果满足，转步骤6；如果不满足，转步骤5。

步骤5：tk+1=λtk，k=k+ 1，转步骤2。

步骤6：输出最优结果。

2.3 算例求解

为了验证文中提出的算法和建立模型的准确性，算例选取客运站8 : 00—12 : 00 的数据进行验证。选取阶段中到发的列车共46 列，该站共2 条正线，5 条到发线，其中 3，5，7 号到发线固定接发下行列车；4，6 号到发线固定接发上行列车；正线I、II 分别用于下、上行列车的不停站通过。文中i，j，n，m，p等变量的取值均为正整数。参数取值：种群规模popsize= 30；交叉概率pc= 0.75；变异概率pm= 0.01；最大迭代次数U= 500；初始温度t0= 100，当温度低于10 时，采用等步长下 降[15]，步 长 取1；nc= 0.8，λ= 0.9，ε= 3×10-6。运用MatlabR 2018a 进行求解，最后目标函数值稳定为31 018 min，通过整理迭代所得数据，得到到发线运用计划，到发线运用方案如表1 所示。

从算例结果可以看出，文中所设计的模型和算法可以满足列车在车站的作业需要，使上行列车分布在4，6 股道，下行列车分布在3，5，7 股道；而车站值班员的方案中将一列上行始发的列车接入了3 道，没实现分方向接发列车。根据上文对均衡性评价的定义，均衡度为然后分别计算车站值班员的方案和优化所得方案的均衡度，均衡度统计如表2 所示。

表1 到发线运用方案Tab.1 Operation plan for arrival and departure tracks

表2 均衡度统计Tab.2 Balance degree statistics

3研究结论

通过对铁路客运站到发线运用优化进行研究，较全面地考虑了到发线分配的影响因素，建立了到发线运用优化模型，并根据模型特点设计模拟退火遗传算法进行求解，最后通过算例对模型和算法进行验证，得到以下研究结论。

（1）考虑到发线固定使用方案的同时，兼顾到发线运用的均衡性，所得方案不仅可以保证行车安全，而且可以使列车均衡的占用到发线，从而提高车站设备的利用效率。

（2）综合考虑模拟退火算法和遗传算法的优点和不足，设计模拟退火遗传算法对问题进行求解，并且在适应度函数中加入惩罚因子，有效地求解了模型。算例表明，该算法在解决到发线运用优化问题上是可行的，收敛速度较快，能够满足车站编制计划实时性的要求，这对车站作业智能化具有一定意义。

（3）按图定到发时刻对到发线运用优化进行研究，由于各种不确定因素使得列车到发时刻与图定时刻有所差异，因而在后续研究中可对列车到发时刻不确定的情况进行研究。