基于列车到发时刻不确定的客运站到发线运用优化研究*

李 涛 胡可昊 宋凯文 杨生仁

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

0 引 言

到发线的合理运用是客运车站行车作业的一项重要内容，是车站编制阶段计划的关键工作之一。高效运用到发线不仅可以提高客运站的服务水平，而且还可以提高铁路资源的利用效率。客运车站一般按到发线的固定方案接发列车，但是实际中列车的运行往往受恶劣天气、车辆以及设备故障等不确定因素的影响，造成列车实际到发时刻与图定时刻产生差异，使到发线运用计划与正常情况下有所不同。

鉴于到发线运用计划的重要性，国内外许多学者针对该问题进行了一系列颇有成效的研究。文献[1-3]都建立了客运站到发线运用的0-1规划模型，算法很好的实现了客运站到发线运用计划的自动编制。文献[4-6]把客运站到发线运用优化的目标分成3个子目标进行考虑，采用智能算法进行求解。文献[7-9]采用排序理论，建立车站到发线运用的排序模型。文献[10-11]把到发线运用优化问题描述为有权重的NPP，构造无向图，采用分枝定界法对模型进行求解。文献[12]使用禁忌搜索算法解决列车到发时刻确定条件下列车的最优过站进路。文献[13-14]对晚点下到发线运用问题进行研究，建立了混合整数规划模型。文献[15]以均衡使用到发线、列车到达时刻不确定性等为约束，建立带柔性重叠时间窗的优化模型，采用模拟退火算法求解。文献[16]在列车到发时刻变动的前提下，分析列车进出站时可能会产生的交叉，建立满足列车最小安全时间间隔的优化模型，设计启发式算法求解。文献[17]统计了列车到发时刻不确定的均值和方差，建立满足列车、咽喉以及股道三者耦合关系的模型，采用模拟退火算法求解。

上述文献存在以下问题:如目标中未考虑设备使用的均衡性[1-3]、当问题规模比较大时，算法的实时性无法满足[4，6]、现有研究大多是按图定时刻对客运站到发线进行优化，而对到发线运用方案中列车到发时刻不确定等因素未能充分考虑。本文在总结已有研究结果的基础上，将列车实际到达时刻与计划到达时刻差值描述为不确定变量，建立了客运站到发线运用优化问题的不确定规划模型，借助不确定理论将模型等价转化为确定类模型。为了提高算法的运行效率以及搜索全局最优解的能力，把遗传算法（genetic algorithm，GA）和模拟退火算法（simulated annealing algorithm，SAA）结合起来，同时在模型中引入惩罚因子、改进选择算子和适应度函数，设计ISAGA算法对确定模型进行求解。

1 问题描述

到发线的运用不仅关系着客运站的服务水平，而且还关系到铁路资源的利用效率。到发线的运用要保证客运车站可以不间断地接发列车，最大限度地利用车站每一条线路的能力，同时也要留有一定的余地。

在实际生产过程中，由于大雨、雪天气的影响、车辆和设备的状态等使列车实际到发时刻与图定到发时刻有所差异，从而影响到发线的运用计划，而现场工作人员为了能完成运输任务，往往会不按技术规范去赶点完成作业，从而引发了许多安全事故。针对列车到发时刻的不确定性，由于样本数据缺乏，将其视为不确定变量进行分析是有效的方法。本文借助不确定理论的方法，利用不确定变量表示列车实际到达时刻与计划到达时刻差值的不确定性，以列车占用到发线时间最小和到发线运用的均衡性为优化目标，以差值得到满足而应达到的置信水平、列车占用到发线的唯一性等为约束条件，建立到发线运用的不确定规划模型。

为了便于后续的研究，现对列车到发时刻不确定条件下铁路客运站到发线优化模型做如下假设。

假设1。列车计划到达时刻为一确定的值，不考虑冗余。

假设2。站内的到发线、信号机等设备能正常接发列车，站外的线路等设备使列车能正常运行。

假设3。列车不会大面积晚点甚至停运。

2 模型建立

2.1 不确定理论知识

不确定理论为解决难以获得精确信息的决策问题提供了数学基础，它已经被用于各个领域，刘宝碇[18]提出了不确定理论。

定义1。记不确定变量为ζ ，它的不确定分布表示为Φ(x)= M{ζ ≤x},x ∈R ，它的逆不确定分布为其反函数[19]，即Φ-1(x)。

在决策过程中，用不确定分布表示不确定变量，首先根据经验或专家意见估计不确定变量所服从的分布[19]，然后求出其逆不确定分布。如果不确定变量ζ 服从下面的正态不确定分布Φ(x) ，则其逆不确定分布为Φ-1(x)。

定理1[20]。设ζ 为一不确定变量，其不确定分布为Φ(x)，Φ(x)∈(0,1)，g(x,ζ)= h(x)- ζ ，当置信水平α ∈(0,1) 时，则有M{g(x,ζ)≤0} ≥α (M{g(x,ζ)≥0}≥α)，当且仅当h(x)≤fζ(α)（h(x)≥fζ(α)）。其中fζ(α)=Φ-1(1 - α)（ fζ(α)= Φ-1(α)）。

2.2 符号及变量定义

设某客运站到发线的集合为D ={1,2,…,j,…,m}，其中j 为第j 条到发线的编号，m 为到发线的总数；计划阶段到达客运站的列车集合L ={1,2,…,i,…,n}，其中，i 为列车i 到达车站的顺序，n 为列车总数；P ={1,2,…,p,…,w}，其中p 为第p 类作业的编号，w 为作业类总数。

Ti为列车的计划到达时刻，即列车运行图规定时刻。

ΔT 为前后2列列车占用同1条股道时的最小安全时间间隔，本文中值取8 min。

cij 为列车i 占用到发线j 的权值，其权值的确定与吕红霞[21]确定方法类似。

xij 为1，列车i 占用到发线j ；0，否则。

2.3 模型建立

目标函数从缩短旅客列车在到发线的停留时间和均衡使用到发线（用每条到发线占用时间总和与各到发线平均占用时间之差的标准差来衡量）2个方面考虑。因列车的出发时刻为列车到达时刻与列车占用到发线总时间的加和，所以可将研究的问题转化为只考虑列车到达时刻不确定性下到发线的运用优化。由于外界因素的无规律变化，使得列车到达时间充满不确定性，本文采用机会约束的思想，将列车到达时刻的波动表示为波动满足的机会达到一定的置信水平，从而得到鲁棒性较高的到发线运用计划，所建模型见式（1）～（11）。

式（1）为目标函数，表示旅客列车在到发线上的停留时间和到发线均衡使用的标准差之和最小。式（2）～（7）为约束条件，其中式（2）～（4）在任何情况下，列车只要占用到发线都必须遵循。式（4）保证同1条到发线上先后接发2列列车时的安全，最小安全时间间隔见图1；式（5）表示列车到达时刻机会约束。列车i 实际到达时刻发生了波动，已不再是一个确定的值，其到达时刻是在一定置信度水平下的置信区间；式（6）表示交叉的疏解；式（7）表示同站台换乘；式（8）～（11）为0-1变量。

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

2.4 确定性等价类模型

因为列车计划到达时刻Ti为确定的值，而实际到达时刻受诸多因素的影响为一不确定的值，本文将的差值记为ζ ，ζ 为1个不确定变量，其不确定分布为Φζ、逆不确定分布为。将约束（5）进行化简，得到式（12）和式（13），利用定义1 和定理1将式（12）和式（13）转化为确定性等价类约束式（14）和式（15）。

通过上述分析，将原来的不确定机会约束规划模型转化为0-1 整数规划的确定性等价类模型。与原来模型式（1）～（11）相比，上述模型只是将约束（5）替换成式（14）和式（15）。为了简化，本文假设ζ服从正态不确定分布，则式（14）和式（15）对应的逆不确定分布见式（16）和式（17）。

3 求解算法

到发线的运用优化已被证明属于NP完全问题[9]，对该类问题的求解多采用智能算法。虽然本文考虑了列车到发时刻的不确定性，但是其占用到发线的过程仍和列车到发时刻固定时是一致的，所以仍可采用智能算法进行求解。本文考虑到SA 较强的鲁棒性和局部搜索能力，将其与GA相结合，能更好的避免GA 的缺点，在此基础上对选择算子和适应度函数等做了进一步的改进，使设计的ISAGA算法能更好的提高运行效率和求解的质量。

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

3.1.1 适应度函数的选取

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

式（18）和式（19）中符号的含义与取值同文献[22]。

3.1.2 改进选择算子

常用赌轮选择法作为选择算子，虽然赌轮选择法容易用程序实现，但是这种方法在计算过程中会产生过早收敛或过慢结束的现象。本文首先创建了2个种群大小均为N的空间，并把二者按其适应度的大小分别进行排序；然后把父代种群中1/4的最优个体和子代种群中1/2 的最优个体组合成一个新的种群，对新种群进行退火选择[23]；最后从中间选取N 个个体组成新的父代，再进行后面的交叉和变异操作[23]。如果个体的适应度大小为f (i)，则个体i 被选中的概率为

式中，tk为当前状态的退火温度。

3.1.3 交叉算子自适应调整

遗传算法中交叉概率pc 的取值对算法的收敛性和搜索速度有很大影响，大小选取不当会使算法进化缓慢，破坏种群的多样性，使算法陷入局部最优。因此，对交叉概率进行非线性的指数形式调整。

式中:K1=0.5，K2=0.9；favg为每代种群适应度的平均值；f ' 为当前要交叉的2 个个体中适应度较小的一个个体；fmin为每代种群中最小的适应度。

模拟退火遗传算法的具体流程见图2。

4 算 例

4.1 算例求解

为了验证本文提出的算法和建立模型的准确性，从某客运站验证的数据中选取某天08:00—12:00时的数据为例进行验证。选取阶段中到发的列车共46 列，该站共2 条正线，5 条到发线，其中3，5，7号到发线固定接发下行列车；4，6号到发线固定接发上行列车；正线I，II分别用于下、上行列车的不停站通过。为了验证假设的分布，本文借助IBM SPSS Statistics 23 对该站7 月、8 月、9 月共3 个月（天气影响和旅客周期性波动较大）进行统计分析，结果见图3～4。

由图3 可见，除了1 列车的时间波动外，其余列车到达时刻的波动是近似服从正态分布的。根据列车到达时刻波动的正态Q-Q图可以看出数据与对角线基本重合，Q-Q图提示该组数据服从正态分布，而且单样本K-S 检验数据摘要中显著性概率P = 0.177 ＞0.04 ,提示假设正态分布成立，且该分布的均值为0.78，标准差为5.723。

图2 算法流程图Fig. 2 Algorithm flowchart

图3 列车到达时刻波动统计Fig. 3 Fluctuation statistics of train arrival time

本文中i,j,n,m,p 等变量的取值均为正整数。参数取值:种群大小 popsize =30；变异概率pm = 0.01 ；最大迭代次数U = 500 ；初始温度t0= 100 ℃，当温度低于10 ℃时，采用等步长下降，步长取1；λ = 0.9 ，ε = 3 × 10-4；α = 10，β = 0.04 。

图4 列车到达时刻波动的正态Q-Q图Fig. 4 Normal Q-Q diagram of train arrival time fluctuations

分别用常规GA和ISAGA 算法给08:00—12:00到达的46 列列车分配到发线，运用MatlabR 2018a在Intel（R）Core（TM）i5-4210H CPU 2.90G Hz，内存4G 的计算机上进行求解，最后GA所得目标函数值稳定为58 843 min，迭代过程见图5，ISAGA所得目标函数值稳定为48 781 min，迭代过程见图6。通过整理迭代所得数据，得到到发线运用方案，见表1～2。

图5 GA优化收敛趋势图Fig. 5 Convergence trend diagram of GA optimization

图6 ISAGA优化收敛趋势图Fig. 6 Convergence trend diagram of ISAGA optimization

表1 GA 所得到发线运用方案Tab. 1 Application scheme of GA's arrival and departure lines

表2 ISAGA 所得到发线运用方案Tab. 2 Application scheme of ISAGA's arrival and departure lines

4.2 算例分析

4.2.1 均衡性

从算例结果可以看出，本文所设计的模型和算法可以满足列车在车站的作业需要，可以使上行列车分布在4，6 股道，下行列车分布在3,5,7 股道；而车站值班员的方案没能实现到发线分方向接发列车。根据本文对均衡性评价的定义分别计算车站值班员所用方案、常规GA 所得方案以及本文设计的ISAGA算法优化所得方案的均衡度，见表3。

进一步计算，得

根据计算结果可知，运用常规GA 得到的到发线运用方案与车站值班员方案相比，到发线运用的均衡度提高了26.32%；运用本文设计的ISAGA 算法得到的到发线运用方案与车站值班员方案相比，均衡度提高了75.47%，与常规GA 得到方案相比，均衡度提高了49.15%。从最后目标值可以看出，ISAGA 所得的目标值比运用常规GA 所得的更优；从优化收敛趋势图可以看出，本文设计的ISAGA算法能够有效的避免GA 陷入局部最优解的缺陷，而且得到的解更接近最优解。

表3 均衡度统计Tab. 3 Balance statistics min

4.2.2 平均误差

为了进一步验证算法和模型的准确性，尽量避免奇异数据对研究问题的影响，随机在这3 个月中选取15 d 的数据进行统计分析。通过对得到的数据进行处理后，运用常规GA和设计的ISAGA算法对选取的15 d的数据进行到发线的分配，分别分析所得方案目标函数值和到发线运用均衡性的均值以及用这2 种算法进行求解得到优化方案的均值，见表4。

表4 平均值统计Tab. 4 Average statistics

根据统计结果可知，运用ISAGA算法求得方案的目标值、均衡性依然是优于运用常规GA 求得的方案。因此，算例中选取的数据可以验证模型和算法的准确性，所选数据不具有特殊性。

4.2.3 α取值

根据文中数据分析所得标准差的值，结合约束（14）～（15），对约束中α的取值进行分析，其中α取0～10 之间的整数。通过计算发现当α取0～7 之间的整数时，能保证约束发挥作用；而取大于7的整数时，约束将不会成立。而文中给参数赋值时，α取5，刚好落入成立的区间，所以得到的结果是可行且有效的。

5 结 论

1） 针对列车到发时刻不确定下客运站到发线运用优化问题，建立了带有机会约束的整数规划模型。以最小化列车占用到发线的时间和到发线运用的均衡性为优化目标，并且借助软件IBM SPSS Statistics 23 验证了样本数据的特征与前文中假设分布的一致性，可以较好的描述实际问题。

2） 借助改进适应度函数、选择算子、交叉算子的模拟退火遗传算法，有效的求解了模型。通过算例分析表明，该算法在解决列车到发时刻不确定条件下客运站到发线分配问题上是可行的，优化所得的方案优于现场方案和运用常规GA 所得方案，均衡性分别提高了75.47%和49.15%。运用设计的ISAGA算法求得的方案，在应对列车到发时刻不确定方面有较好的鲁棒性，车站可以按照所得方案安排生产，从而保证车站作业的安全性。因为算法的改进，使得算法收敛速度较快，能够满足车站编制计划实时性的要求，对车站作业智能化具有一定的意义。

3） 通过平均误差分析结果看出，算例所选数据不是个例，能够验证模型和算法的准确性。运用设计的ISAGA算法所求方案的目标函数值、均衡性以及求解效果确实优于常规GA 所求方案。通过α取值分析看出，计算时给参数的赋值是合理的。

4） 在建立到发线分配模型时，对问题进行了简化，未考虑列车大面积晚点、列车停运，及不确定变量服从其他分布的情况。在后续可对列车晚点且密集到达后接发车进路的调整以及不确定变量服从其他分布的情况进行研究。