基于模拟退火改进人工鱼群算法的交通信号配时优化

许佳佳,李雪梅

(安徽三联学院 1 交通工程学院,2 电子电气工程学院,安徽 合肥,230601)

交通信号配时优化对于减小交叉口的车均延误和提升其通行能力有着重要的作用。基于此,相关学者对交叉口信号配时做了诸多研究和改进。如:运用传统的信号周期配时方法进行交叉信号配时优化及通过软件进行仿真评价[1～3];通过建立动优化控制模型对交叉口的信号方案进行动态控制研究[4,5];基于交叉口平均延误最小化目标运用遗传算法进行交叉口信号配时方案的求解与运行效果评价[6～8];以及运用荧火虫算法、蜜蜂算法和粒子群算法等智能算法进行信号配时优化[9～11]。由于传统的信号配时方法无法适用过饱和流量的交叉口优化[12],而单一智能算法在求解信号配时在解决实际问题时因自身的不足影响计算结果和工作效率,如遗传算法存在编码不规范和粒子群算法易于陷入局部最优解等问题[6,7]。为此,笔者综合考虑周期时长和绿灯时间及饱和度等约束条件,以交叉口车均延误最小为目标函数构建信号配时优化模型,选择收敛精度高的模拟退火算法和初值鲁棒性强的人工鱼群算法组合构建模拟退火改进人工鱼群算法,对信号配时优化模型进行求解,并对现状方案和3种不同智能算法求解方案情况下的交叉口整体车均延误进行对比,验证模拟退火改进人工鱼群算法的可行性与适用性。

1 模拟退火改进人工鱼群算法

模拟退火(Simulated Annealing,SA)算法是根据物理知识中固体退火原理所开发的应用于求解最优化模型的一种通用的仿自然优化算法,SA算法中将物质的能量达到最低状态的设定模拟成目标函数并根据固体物质的退火过程包括加温、等温和冷却等3个过程进行求解[13]。SA算法由于在等温过程中采用了Metropolis准则,能够有一定的概率去接受恶化解,使其能够跳出局部最优而有着较好的全局搜索能力。

人工鱼群(Artificial Fish-Swarm,AF)算法是基于鱼的觅食、聚群、追尾、随机活动等行为所提出的一种应用于求解最优化模型的群智能优化算法,在迭代优化的过程中人工鱼个体的最优状态会被进行跟踪和记录,并且人工鱼往往会在极值点特别是全局极值点进行聚集从而找到最优解[14～16],AF算法相较于传统的求解方法具有分布处理的能力及参数和初值鲁棒性强等特点。

AF算法虽然有着较好的全局收敛性,但由于感知能力和步长参数是固定的,参数设置过大会导致在接近最优解的附近来回振荡而影响最终求解的精度,参数设置过小会导致在局部最优解中无法跳出即未达到最优值区域结束算法运算,因此可尝试利用SA算法初值鲁棒性和局部收敛精度高的特点对AF算法进行改进,构建模拟退火改进人工鱼群(SAAF)算法。首先,通过AF算法对每一代人工鱼中的全局最优个体进行搜索,再对其运用SA算法进行退火模拟运算以避免AF算法陷入局部最优解的情况,并将SA算法的寻优结果适应度与AF算法进行对比以更新人工鱼群进行迭代。SAAF算法的运算逻辑过程见图1。

2 交叉口信号配时优化模型

根据美国通行能力手册中对于交叉口车辆延误的定义,现有交叉口各进口各个方向车道的车均延误由均匀延误和随机延误两部分组成,其中均匀延误是指进口道车辆均匀到达所产生的均匀延误,随机延误是指进口道车辆随机到达并引起超饱和周期所产生的延误,本次研究假设各交叉口各进口车道各个方向的车辆到达类型随机,对应的各个方向内不同车道的车均延误是相同的。针对现状大部分十字型平面交叉口均采用的典型四相位配时方案,本次研究用di表示第i个相位的综合车均信控延误(i=1,2,3,4,分别代表东西直行、东西左转、南北直行、南北左转相位),单位为s/pcu;di j表示第i个相位中第j个进口方向对应车道的综合车均信控延误(i=1,2,3,4;j=1,2)(d11,d12,d21,d22,d31,d32,d41,d42), 单位s/pcu;di j z表示第i个相位中第j个进口方向中第z种单项车均延误(i=1,2,3,4;j=1,2;z=1,2;其中z=1代表均匀延误,z=2代表随机延误),单位s/pcu;gi表示第i个相位的显示绿灯时间(i=1,2,3,4),单位s;Si j表示第i个相位第j个进口方向对应的平均单一车道的饱和流率,单位pcu/h;yi表示第i个相位的黄灯时间(i=1,2,3,4),单位s;li表示第i个相位的车辆启动损失时间(i=1,2,3,4),单位s;t表示分析时段的持续时长,单位h,取0.25 h;e表示单个交叉口信号控制类型校正系数,定时信号取e=0.5。下面以第1个相位中第1个进口方向中的综合车均延误d11的均匀延误d111和随机延误d112为例说明延误计算式,具体见式(1)(2)(3),其它相位和进口方向车道的均匀延误和随机延误可同理计算。

d11=d111+d112

(1)

(2)

(3)

交叉口整体的车均延误数值越小代表交叉口的运行效果越好,即车辆在经过交叉口时平均延误的时间越短越好,因此设定交叉口整体车均延误最小化目标函数。交叉口的信号周期的时长需要设置合理。周期时长过短会直接影响到车辆是否安全通过和行人能否安全通过;而周期时长过长虽然能够提升交叉口的通行能力,但提升的效率不明显并会使通行延误急速增长。因此,在设置周期时长时需要考虑下限和上限的约束,一般将周期时长的范围限定在40～180 s之间。同理,对于各个相位的绿灯时间也需要进行上限和下限的约束设置。本次研究将各个相位绿灯时间的上限设置为100 s,下限的设置需要考虑车辆和行人通过交叉口的最短时间,用wimax表示为第i个相位中两个对向方向车辆或行人通过交叉口需要经过的最大距离,vc表示车辆通过的区间速度,vp表示行人通过的区间速度。因大部分情况下通过交叉口的损失时间与黄灯时间相近,此处对各相位最短绿灯时间进行简化处理,对应的直行相位因为要考虑行人通行,其绿灯时长的下限为wimax/vp,而对于只需考虑车辆通行的左转相位绿灯时长下限为wimax/vc。为了克服经典Webster方法只适用于非饱和流量的情况,此处考虑将整个交叉口的饱和度作为约束条件进入模型,根据交叉口优化效果的经验将饱和度设置在0.7～0.9的闭区间范围内。基于上述目标函数和约束条件,结合前述延误计算理论中的定义构建交叉口信号配时优化模型,具体见式(4)。

(4)

式中:z为交叉口整体的车均延误,单位s/pcu;qi j为第i个相位中第j个进口方向的交通量,单位pcu;di j为第i个相位中第j个进口方向的车均延误,单位s/pcu;gi为第i个相位的显示绿灯时间,单位为s;yi为第i个相位的黄灯时间,单位s;wimax为第i个相位中两个对向方向车辆或行人通过交叉口需要经过最大的距离,单位m;vc表示车辆通过交叉口的区间速度,单位m/s;vp表示行人通过交叉口人行横道的区间速度,单位m/s;yi表示第i个相位的黄灯时间,单位s;li为第i个相位的车辆启动损失时间,单位s。

3 实例分析

以安徽省合肥市紫云路与金寨路相交的典型四相位十字型平面交叉口(以下简称“紫金路口”)的交通流量数据为例,相位1对应东西直行,相位2对应东西左转,相位3对应南北直行,相位4对应南北左转,右转不设专用相位(即车辆右转不受信号控制),车道宽度>3 m,道路无纵坡,无自行车影响,大车比例很小不作特别分析,因此不考虑对饱和流率的影响与修正,确定一条直行车道的标准饱和流量为1 650 pch/h,一条直行车道的标准饱和流量为1 550 pch/h。该交叉口各方向流量与配时基础数据见表1。

表1 安徽省合肥市紫云路与金寨路平面交叉路口各方向流量与配时数据

基于交叉口的现状交通流量和配时数据,考虑交叉口各个相位的启动损失时间为3 s,计算结果显示,整体交叉口的车均延误为202.81 s/pcu,表明车辆通过该交叉口时的拥堵情况较为严重。下面试验用SA算法和AF算法及SAAF算法进行交叉口的信号配时优化。

(1)SA算法的相关参数设置:随机生成初始解,初始温度T0=1 000,终止温度Tend=0.001, 每次退火温度下的迭代次数L=500,降温速率q=0.9, 最大迭代次数count=100。

(2)AF算法的相关参数设置:人工鱼的数量fishnum=100, 最大迭代次数MAXGEN=100,觅食行为中的最多试探次数try_number=30, 模拟鱼感知半径的感知距离visual=35, 拥挤度因子(模拟鱼群的拥挤程度的拥挤度因子)delta=0.618, 最大移动步长step=4.5。

(3)交叉口延误计算的其他相关参数设置:针对于交叉口信号配时的约束优化模型中的约束条件要求,行人过街步行速度vp取1.5 m/s, 车辆通过交叉口的速度vc为3 m/s, 4个相位中两个对向方向车辆或行人通过交叉口需要经过最大的距离依次取40,50,30,50 m,各相位的绿灯损失时间均取3 s, 各相位的黄灯时间也设置为3 s。

基于交叉口的流量数据和相关的交叉口形式、交通流和信号配时的默认设置参数,代入上述交叉口信号配时的约束优化模型从而实现模型的实例化,先分别运用SA算法和AF算法对其进行启发式求解和计算延误,再将两种方法基于前述模拟退火改进人工鱼群算法的思路进行组合并进行实例模型的求解,最终得到单一智能算法和组合改进算法的信号配时方案解及对应的延误数据,具体的交叉口信号配时现状与优化方案及其运行效果评价数据见表2。

表2 安徽省合肥市紫云路与金寨路平面交叉路口信号配时现状与优化方案运行效果

试验结果表明,SA算法、AF算法和SAAF算法所得的信时配时方案中的时间数据之间较为接近,但相对于现状信号配时方案有着较大变化,3种算法求解的信号配时方案对应的交叉口整体的车均延误分别为98.94,97.88,96.66 s/pcu,相较于现状交叉口车均延误均减小了50%以上,说明通过智能算法进行交叉口信号配时优化的效果较为明显,并且其中SAAF算法所得方案的车均延误要更优于单一的SA算法和AF算法(图2)。

图2 交通信号配时优化3种算法迭代优化过程

计算结果表明,3种不同的算法的迭代过程变化情况有着较大的差异(图2)。SA算法因为其全局搜索能力表现出迭代初期过程波动程度较大,而AF算法基于其较强的搜索能力使得其初期解的结果较优并且下降过程较为稳定。而SAAF算法结合了两种方法的优点,在迭代的初期即非常接近最优解,在后续迭代过程中也表现非常稳定的持续下降趋势,并且改进后的算法历代迭代所得到的信号配时方案对应的交叉口整体车均延误均优于另两种算法,表现出SAAF算法求解约束优化模型的良好效果。

4 结论与讨论

本次研究以交叉口车均延误最小为目标函数和周期时长及绿灯时间等为约束条件构建信号配时优化模型,并基于SA算法对AF算法进行改进后对模型进行求解与分析交叉口的通行效果改进情况,得出以下结论:(1)AF算法由于其感知能力和步长参数是固定的,会使其容易跳过最优解和陷入局部最优解,利用SA算法初值鲁棒性和局部收敛精度高的特点进行改进可以提升其搜索全局最优解的能力;(2)SA算法、AF算法和SAAF算法求解所得的信时配时方案中的时间数据之间较为接近,相对于现状信号配时方案有着较大的优化效果,并且SAAF算法的效果要优于单一算法。(3)SA算法在迭代运算的初期过程波动程度较大,而AF算法初期解的结果较优并且下降过程较为稳定,SAAF算法在迭代的初期便能非常接近最优解和稳定下降趋势表现出快速寻优的能力。本次研究主要针对典型的平面单点十字交叉道口,对于其它类型的交叉口信号配时点控和多个交叉口的线控还有待进一步论证和研究。