基于改进萤火虫算法的铁路运行调度算法研究

徐虎

(西安铁路职业技术学院 机电工程系， 西安 710016)

0 引言

铁路运输在我国经济发展中发挥了巨大作用，随着经济的发展和社会的进步，对铁路运输提出更多要求，铁路列车的合理调度对提高铁路运输能力、调度能力和组织能力具有重要意义。目前，列车调度是基于列车运行图进行调度和调整的，由于随机因素和不确定因素的影响，铁路列车容易出现时刻偏差的问题，因此对列车进行优化调度和调整，可以实现列车的合理调度，在确保列车安全运行的前提下，使得铁路运行列车上行时间差和下行时间误差的总和最小。

1 改进的萤火虫算法

萤火虫算法[1](Firefly Algorithm，FA)是用萤火虫个体模拟搜索空间的点，利用萤火虫自身的趋光性，将寻优问题转化成为寻找萤火虫群体中亮度最大的萤火虫。每次迭代，找到亮度最大的萤火虫，通过萤火虫之间的吸引和移动实现萤火虫位置的更新。

萤火虫i向亮度更强的萤火虫j移动更新规则如[2]式(1)。

Xi=Xi+β(r)×(Xj-Xi)+αεi

(1)

与其他群智能算法类似，FA算法在算法寻优后期阶段容易在局部最优或者全局最优附近反复振荡，陷入局部最优，为改进局部最优问题，将惯性权重引入FA算法，提出一种改进的萤火虫算法(Improved Firefly Algorithm，IFA)，惯性权重如式(2)[3]。

(2)

其中，wmax、wmin分别表示最大和最小权重；t、Tmax分别表示当前迭代次数和最大迭代次数。IFA算法的位置更新公式如式(3)。

Xi=wXi+β(r)×(Xj-Xi)+αεi

(3)

2 列车运行图

列车运行图是列车运行调度的基础，通过坐标原理描述刻画列车运行的时间和空间关系，通过列车运行图可以直观地显示列车在各个车站通过或者停车的状态，其规定了各次列车运行区间的顺序，列车在区间运行时间，列车在每个车站到达、出发或通过时刻以及列车在车站的停靠时间和列车在折返站折返所需时间等[4]。

列车运行图中如如图1所示。

图1 列车运行图

横坐标、竖直线和纵坐标分别表示时间、时分线和车站距离；横直线和斜线分别表示站名线和列车运行线，前者表示各个车站到发线中心的位置，而后者是运行线和水平线的交点表示列车到站时间、发站时间和停站时间。

3 铁路运行调度模型

铁路运行调度的目的是在确保列车安全运行的前提下，使得铁路运行列车上行时间差和下行时间误差的总和最小。由于铁路列车运行系统的连续性，当某个列车晚点时，为了保证铁路列车的运行安全和降低晚点所产生的不利影响，列车调度中心需要对后续列车进行调度处理。为了将列车晚点产生的不利影响控制在很小的区间范围内，因此列车运行调度优化的区间范围也应该控制在很小的区间范围内[5]。

3.1 编码

为了便于问题的简化和解决，列车运行时间采用整数编码。例如，12:00:00的整数编码结果为43 200。列车运行时间矩阵编码形式如下：到站时间矩阵编码为：[d11d12d13……d1n]，发车时间矩阵编码为：[f11f12f13……f1n]。其中，[d11d12d13……d1n]和[f11f12f13……f1n]分别表示第1辆列车在第1站到第n站的到站时间和发车时间。

3.2 数学模型

为实现列车的合理调度，在确保列车安全运行的前提下，使得铁路运行列车上行时间差和下行时间误差的总和最小，铁路列车调度的数学模型可表示为[6]：

(1) 列车到站和站点发车早晚点时间之差的绝对值之和最小，如式(4)。

(4)

(2) 列车到站和出发早晚点数量之和最小,如式(5)。

(5)

其中式(6)、式(7)。

(6)

(7)

当列车到站和离站时间误差大于10 s时，列车晚点；反之，列车不晚点。

综合上述分析，铁路列车调度的数学模型可表示为[7-8]式(8)。

(8)

其中，λ1、λ2表示权重。

3.3 约束条件

(1) 发车时间：列车计划发车时间不能迟于列车实际发车时间为式(9)。

(9)

(2) 列车停站时间：列车最小停站时间≤实际停站时间为式(10)。

(10)

其中，Tik(min)表示列车最小停站时间。

(3) 列车区间运行时间[9]：所用轨道交通停靠站中相邻两站点之间的轨道交通列车运行时间≥最小运行时间Tmin。如式(11)。

(11)

(4) 列车追踪时间：相邻两列车的运行时间间隔≥规定的运行时间间隔ΔT，从而保证列车的行车安全,如式(12)。

(12)

3.4 算法步骤

基于IFA的铁路运行调度优化流程如下：

Step1：读取列车运行的计划时刻表，包括列车到达时间和发车时间；

Step2：参数编码；

Step3：初始化IFA算法参数：萤火虫数量N、初始吸引度β0、步长因子α、萤火虫初始位置X和最大迭代次数T；

Step4：计算各萤火虫的亮度并进行排序：计算每个萤火虫所对应的适应度f，将适应度f作为对应萤火虫的亮度并排序，得到亮度最大的萤火虫位置；

Step5：判断迭代是否结束：如果算法达到最大迭代次数T，则算法转到Step6，否则转到Step7；

Step6：输出亮度最大的萤火虫位置及其亮度，得到最佳调度时间；

Step7：更新萤火虫位置：根据公式(3)更新萤火虫的位置。

4 实证分析

4.1 数据来源

为验证本文算法的有效性和可靠性，选择某地铁1#线的时刻表为研究对象，共13个站点，以3辆列车上下行6个运行车次进行实证分析[10-11]，列车追踪间隔时间为180 s，运行时刻表如表1所示。

每个站点最小停站时间和计划停站时间分别为[170 25 25 25 35 25 25 25 25 25 25 25 25 110]和[180 30 30 30 40 30 30 30 30 30 30 30 30 120]。时间参数如表2所示。

4.2 结果分析

IFA算法参数设置如下：萤火虫数量N=50、初始吸引度β0=1、步长因子α=0.5和最大迭代次数T=100，其优化结果如图2所示。

将IFA与FA、PSO和GA算法进行对比，其对比结果如图2所示。由图2可知，IFA算法具有更快的收敛速度，效果优于FA、PSO和GA算法，避免陷入局部最优，同时提高收敛速度。优化结果如表3所示。

由表1和表2对比可知，列车上行至第3站时晚点200 s，通过IFA算法优化调整，列车下行至第12站时恢复正点。通过IFA算法优化调整列车调度，在保证列车安全运行的情况下，可以将列车晚点产生的不利影响控制在很小的区间范围内。

表1 列车计划时刻表

表2 时间参数

表3 优化结果

5 总结

为了实现铁路列车的优化调度，将列车晚点产生的不利影响控制在较小的区间范围内，将改进的萤火虫算法引入铁路列车调度优化数学模型，在合理的约束条件上，运用IFA算法进行优化求解。研究结果表明，通过IFA算法优化调整列车调度，在保证列车安全运行的情况下，可以将列车晚点产生的不利影响控制在很小的区间范围内。

(a) IFA

(b) FA

(c) PSO

(d) GA