多蚁群双信息素疏散路径规划算法
2020-08-14吴世旺
吴世旺
(上海平可行智能科技有限公司,上海 200235)
0 引 言
对于人员疏散的研究,国内外从研究角度上可以划分为基于网格的微观疏散模型和基于路网的宏观疏散模型。
基于网格的微观疏散模型考虑了疏散细节,将路径规划策略加入到模拟模型中,以微观引导手段来改善疏散效率。吴鹏飞等[1]针对地铁应急疏散场景,在基本ACO算法的基础上对路径选择策略、启发式函数和信息更新策略进行改进,提高正反馈作用和收敛速度,为整个疏散群体求解更优的疏散路径。郭阳勇等[2]结合元胞蚁群算法和卡尔曼滤波提出了一种新的疏散模型PECA,利用元胞蚁群算法和卡尔曼滤波对最短疏散时间的优化模型进行求解。YE等[3]将ACO算法和元胞自动机模型(CA)结合,上层采用ACO算法进行路径选择,底层使用CA模型实现人员在离散空间上的移动和位置冲突的解决。
基于路网的宏观疏散模型忽略人员疏散细节,将疏散环境抽象为动态网络图,通常使用启发式算法进行求解。YUAN等[4]针对复杂环境下的应急疏散,以最小化疏散时间和拥挤度为目标,改进基本ACO算法进行求解;LIU等[5]将疏散场景划分为疏散区域、过渡区域和安全区域,提出改进的量子蚁群疏散路径规划算法。董崇杰等[6]针对人车混合的大型公共场所,使用改进的布谷鸟算法对目标函数进行求解。FANG等[7]为解决体育场的应急疏散路径优化问题,将环境抽象为分层有向网络,提出了HMERP-ACO算法。
如何均衡路段的通行量负载,为疏散个体合理配置路径,提升疏散效率,是综合交通枢纽常规疏散研究的重点。本文结合综合交通枢纽常规疏散特点,基于疏散路网,以最小化网络清空时间、人均疏散时间和累计拥堵系数为疏散目标,提出多蚁群双信息素算法(multi-ant colony double pheromone algorithm,MACDPA)来研究综合枢纽内的常规疏散路径规划问题。
1 综合交通枢纽常规疏散问题描述
1.1 疏散路网
选取综合枢纽内的楼梯、自动扶梯、出入口和乘车点等作为关键节点,将疏散环境抽象为二维网络图:
G=(N,E,R)
(1)
式中:N为疏散节点;E为节点间的连线;R为路段通行属性。
R=(L,W,SC,LC)
(2)
SC=L×W×ρS
(3)
LC=L×W×ρL
(4)
式中:L、W分别为路段长度、宽度;SC为安全容量,当该路段上的人数小于SC时,行人可以按期望速度自由移动;LC为路段极限容量,当该路段上的人数大于等于LC时,拥挤度达到极限,人群缓慢推进或停止移动;ρS为个体不受影响可以按照意愿自由行走的人群密度常量;ρL为人群拥挤度达到极限只能缓慢推进或者完全停止移动的人群密度常量。根据文献[8],令ρS=0.39 人/m2,ρL=3.8 人/m2。
1.2 疏散目标函数及约束
综合交通枢纽常规疏散路径优化的目标函数描述如下:
minf1=max(T1,T2,…,Tk,…Tm)
(5)
(6)
(7)
式中:f1为最小化网络清空时间;f2为最小化累计拥堵系数;f3为最小化人均疏散时间;m为疏散人员总数;Tk为人员的疏散时间;Cij(t)为t时刻路段(i,j)上的拥堵系数。
模型约束如下所示。
(8)
(9)
(10)
(11)
(12)
2 多蚁群双信息素算法
本文结合具体研究对象及优化目标,提出MACDPA算法,将疏散人员当作蚂蚁,根据乘车意向划分为多个种群,改进ACO算法中启发式信息和信息素函数,考虑人员在实际疏散过程中,偏向于选择较短路径,且有意避免路段过度拥挤,引入种群信息素和部落信息素的概念。利用种群信息素的正反馈作用来引导同一种群的蚂蚁进行最短疏散路径寻优,利用部落信息素的负反馈作用来避免路段过度拥挤,实现路径资源均衡分配的同时,提高疏散效率。
2.1 算法设计
1) 启发式信息搜索策略
(13)
(14)
2) 信息素更新策略
引入种群信息素和部落信息素,借助于二者的综合作用,避免算法收敛于局部最优,均衡路段负载,改善疏散效率。
种群信息素:同一种群的蚂蚁产生的信息素,该信息素作为种群内部通信的媒介,正反馈机制引导同种群的蚂蚁选择较短的路径。更新策略为:
τij(n+1)=(1-ρ1)τij(n)+ρ1Δτij(n)
(15)
(16)
(17)
部落信息素:所有蚂蚁产生的信息素,该信息素作为所有蚂蚁共享的通信媒介,负反馈机制避免过多蚂蚁聚集在同一路段。更新策略为:
φij(n+1)=(1-ρ2)φij(n)+ρ2Δφij(n)
(18)
(19)
(20)
3) 状态转移概率
(21)
式中:α为信息素因子;β为启发函数因子;NextLINK_set为蚂蚁k从节点i转移到下个节点j的可选节点集。
2.2 算法实现步骤
MACDPA算法求解综合交通枢纽内的常规疏散问题的过程描述如下:
Step1:初始化模型参数
初始化模型参数,设置最大迭代次数NCmax,迭代计数器NC=1,初始化种群信息素τij(0)=c,部落信息素φij(0)=c。
Step2:选择路径
将蚂蚁放在起始节点上,在节点i上的个体k根据Pij来选择下一个节点j,重复这个过程,直到k到达目标节点,当所有疏散个体获得相应的疏散路径后,完成一次迭代。
Step3:更新Pareto解集
完成步骤2中的一次迭代,每一个疏散个体建立了疏散路径,所有的疏散路径构成一个可行解sn。计算目标函数值,如果sn是非支配解,将sn加入到Pareto解集中,并移除被sn支配的解。
Step4:更新信息素
用φij(t+1)更新每条边上的部落信息素。若本次迭代产生的解是pareto解,则使用新的τij(t+1)更新每条边上的种群信息素,否则,不更新种群信息素。
Step5: 终止条件
令NC=NC+1,若NC 以某综合交通枢纽为试验对象,路网图如图1所示,其中:节点1为火车出口;节点59为火车入口;节点4、5为轻轨乘车点;节点10为长途客运乘车点;节点17为出租乘车点;节点18为公交乘车点。 相应的参数设置如表1所示。初始时,将人群分布在起始节点1上,试验选择三种算法进行比较:ACO算法、HMERP-ACO算法和本文提出的MACDPA算法。 表1 算法参数设置 试验结果如图2~图5所示。图2~图5分别为三种算法的网络清空时间、累计拥挤度、人均疏散时间和人均疏散长度。可以看出,相比其他两种算法,MACDPA算法通过适当地使部分人“舍近求远”,有效地均衡了路径负载,提高了疏散效果。 表2为三种算法得到的Pareto解对应的目标函数值,图6为三种算法得到的目标函数值的分布。由表2可知,MACDPA得到的Pareto解无论在质量还是数量上都优于其他两种算法。 表2 三种算法的Pareto解 图7是三种算法对应的疏散曲线。在前200 s,三种算法的疏散人数基本相同;在200 s~350 s,MACDPA算法相比其他两种算法,疏散人数较少;350 s后,MACDPA算法的疏散人数明显多于其他两种算法。 试验结果表明,本文提出的MACDPA算法,相比其他两种算法能够提供更优的疏散路径规划方案。 城市综合交通枢纽作为一个为市民提供公共换乘服务的公共场所,在保证正常运营的前提下,均衡利用交通枢纽内的现有资源,尽量降低人员拥挤度,改善疏散人员体验度,提高路径资源利用率及枢纽运营效率,具有重要意义。本文针对相应的疏散目标,基于蚁群算法,改进启发式函数,引入种群信息素和部落信息素的概念,提出多蚁群双信息素MACDPA算法,并将其与ACO和HMERP-ACO算法进行对比。试验结果表明,本文提出的算法能够为综合交通枢纽的常规疏散提供更优的疏散路径规划方案。3 试验结果及分析
4 结束语