基于PSO算法的城市轨道交通运行调度优化研究

刘欣昊

中南大学 交通运输工程学院,湖南 长沙 410083

随着经济的发展和社会的进步，城市轨道交通作为新型的交通工具得到广泛重视和发展，其具有方便、安全、快捷、准时、节能和污染较小的优点[1]。由于城市轨道交通的快速发展，列车自动控制系统在轨道交通列车控制中得到广泛应用，该系统不但可以协助列车调度人员进行列车调度管理，同时进行列车的实时运行监控，确保行车安全，有效提高列车调度效率和降低列车运行成本和管理成本。列车调度主要是基于列车运行图行驶的，由于存在的随机因素和不确定性的影响，在实际运行过程中，列车会经常出现偏离列车时刻表的情况，因此需进行列车运行自动调整，实现列车的正点运行和调度。

1 粒子群算法（Particle Swarm Algorithm，PSO）

粒子群算法是受鸟群觅食行为启发而提出的群搜索算法，其位置xid和速度Vid更新公式如公式（1）和公式（2）所示[2]：

其中，w表示惯性权值；c1、c2表示学习因子，一般取c1=c2=2；r1、r2表示(0，1)之间的随机数；pid、pgd分别表示个体最优位置和全局最优位置；Vi为每个粒子的移动速度，Vi∈[-Vmax,Vmax]，Vmax为常数。

2 列车运行图

列车运行图是指运用坐标原理描述列车在轨道线路运行的时间、空间关系，直观地显示出在各车站停车或通过、在各区间运行状态的一种图解形式[3]。列车运行图是轨道交通列车运行的基础，其规定了每个轨道交通列车车次所占用区间的顺序相关信息，主要包括轨道交通列车在各个站点的到站时间、离站时间和停站时间以及列车上行和下行所需的时间。

3 轨道交通运行调度模型

3.1 建立模型

城市轨道交通运行调度的目的是在保证轨道交通列车运行安全的情况下，保证轨道交通列车上行和下行的时间误差总和最小。由于城市轨道列车运行系统具有连续性，为了保证列车的行驶安全，因此当某个列车的晚点时，列车调度中心将对后续的列车进行运行调度，确保运行安全，同时减小因列车晚点所带来的不利影响。为了将列车晚点所带来的不利影响限制在较小的范围内，因此列车运行调度优化的区间范围也应限制在较小的范围内[4]。

3.2 编码

为了方便问题解决，本文采用整数编码方式对列车运行时间进行编码。例如12:00:00的整数编码结果为43200。矩阵编码形式如下：

到站时间编码结果：[d11d12d13…d1n]

发车时间编码结果：[f11f12f13…f1n]

其中，[d11d12d13…d1n]表示第1辆列车在第1站到第n站的到站时间；[f11f12f13…f1n]表示第1辆列车在第1站到第n站的发车时间。

3.3 数学模型

为实现列车的合理调度，在保证轨道交通列车运行安全的情况下，保证轨道交通列车上行和下行的时间误差总和最小，本文轨道交通调度数学模型的目标函数选择如下[5]：

（1）列车到站早晚点时间和站点发车早晚点时间之差的二者绝对值之和最小。

其中，n1、n2分别表示上行列车数和下行列车数；d´i;k、di;k分别表示列车实际到站时间和计划到站时间；f´i;k、fi;k分别表示列车实际离站时间和计划离站时间。

（2）列车到站早晚点数量和出发早晚点数量之和最小。

公式（5）和公式（6）中，当列车到站和离站时间误差＜10 s时，列车不晚点；反之，列车晚点。

通过综合分析，轨道交通列车调度的数学模型可表示为[6]：

公式（7）中，λ1、λ2表示权重。

3.4 约束条件

（1）列车停站时间约束：列车最小停站时间应小于等于实际停站时间。

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

（2）列车追踪时间约束：相邻两列车的运行时间间隔应大于等于规定的运行时间间隔ΔT，从而保证列车的行车安全。

（3）发车时间约束：列车实际发车时间不能早于列车计划发车时间。

（4）列车区间运行时间约束：所用轨道交通停靠站中相邻两站点之间的轨道交通列车运行时间应大于等于最小运行时间Tmin。

3.5 算法步骤

基于PSO的城市轨道交通运行调度优化的算法步骤如下：

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

Step 2：参数编码；

Step 3：设定PSO算法的种群大小popsize，最大迭代次数Iteration，学习因子c1，c2，根据优化变量的取值范围，随机生成初始化种群；

Step 4：根据轨道交通列车调度的数学模型公式（7）计算粒子个体的适应度，计算出局部最优粒子和全局最优粒子的位置和最优值；

Step 5：更新粒子速度和位置；

Step 6：计算适应度，并进行位置更新和速度更新；

Step 7：若gen＞Iteration，保存最优解；反之gen=gen+1，转到Step 4。

4 实证分析

为验证本文算法的有效性，以某地铁2#线的时刻表为研究对象，设置有13个站点，以3辆列车上下行6个运行车次进行仿真实验[7,8]，列车追踪间隔时间为180 s，其运行时刻表如表1所示。该地铁运行线路的非工作日和工作日不同时间段进站客流分布图分别如图1和图2所示。每个站点计划停站时间分别为[180 30 30 30 40 30 30 30 30 30 30 30 30 120]，最小停站时间分别为[170 25 25 25 35 25 25 25 25 25 25 25 25 110]。

图1 不同时间段进站人数分布图Fig.1 Distribution of checkin population at different periods

表1 列车计划时刻表Table 1 Train schedule timetable

表2 时间参数Table 2 Time parameters

4.1 优化结果分析

PSO算法[9]的种群大小为20，最大迭代次数为100，学习因子c1=c2=2，其优化结果如表3所示：

表3 优化结果Table 3 Optimization results

通过表1和表2对比分析可知，轨道交通列车上行到第3站时晚点200 s，经过PSO算法的优化调整，列车下行至第12站时恢复正点。通过PSO算法优化调度，可以保证列车的正常运行，同时可以进行实时调整，确保列车晚点时间在较小的范围内。

4.2 收敛速度分析

为验证PSO算法的收敛速度，将其与GWO、SCA、MFO、ALO、MVO、WOA、GA和DE算法进行对比，其收敛结果对比如图2所示，通过对比可知，PSO算法收敛速度最快。

图2 收敛速度对比图Fig.2 Comparison of convergence speeds

5 结论

针对轨道交通列车运行存在运行早晚点的问题，在保证轨道交通列车运行安全的情况下，确保轨道交通列车上行和下行的时间误差总和最小，将PSO算法引入轨道交通运行调度，在构建数学模型和约束条件的基础上，运用PSO算法优化求解。研究结果表明，通过PSO算法优化调度，可以保证列车的正常运行，同时可以进行实时调整，确保列车晚点时间在较小的范围内。

[1]雷 敏,杨万里,彭晓波,等.基于改进简化粒子群算法的含DG的配电网无功优化[J].华北电力大学学报:自然科学版,2015,42(1):39-44

[2]李 锦,王联国.基于细菌觅食优化算法的城市轨道交通调度优化[J].计算机工程与科学,2017,39(3):586-592

[3]季一木,柴博周,杨罗坤,等.基于TD-LTE的轨道交通集群调度系统[J].计算机工程,2017,43(6):296-300

[4]蒋 琦.城市轨道交通CBTC系统列车调度策略优化研究[D].北京:北京交通大学,2012

[5]肖 枫.基于模糊神经网络的城市轨道交通行车间隔时间优化研究[D].重庆:重庆交通大学,2013

[6]邢 雪.基于粒子群算法的城市接驳公交网络优化调度方法[J].北京工业大学学报,2016,42(9):1385-1391

[7]李 轩,张 鑫.基于地铁公司和乘客满意度最大化的轨道交通列车开行优化方案[J].交通科技与经济,2015,17(1):69-72

[8]娄建峰,高岳林,李 飞,等.基于改进粒子群算法的云计算任务调度算法[J].微电子学与计算机,2016,33(8):112-116

[9]周丽娟,王春影.基于粒子群优化算法的云计算资源调度策略研究[J].计算机科学,2015,42(6):279-281