基于改進Dijkstra算法的人群反饋調(diào)節(jié)疏散①

任少強,汪一鳴

1(蘇州大學,蘇州 215031)

2(合芯科技有限公司,廣州 511365)

1 引言

隨著人民生活水準的提高,休閑廣場等大型公眾區(qū)域成為服務人民休閑娛樂的重要場所,具有服務對象復雜,承載人群密度高等特點[1].我國早已將公共場所突發(fā)情況下的人群疏散管理研究作為重點研究項目,國務院于2006年,發(fā)布《國家中長期科學和技術發(fā)展規(guī)劃綱要》就將“突發(fā)公共事件防范與快速處置”列入其中.即便如此,據(jù)不完全統(tǒng)計,全球每年因人群聚集而引發(fā)踩踏等事故造成人員傷亡的數(shù)量還在急劇增加.例如,2014年12月31日,上海外灘廣場聚集了一大批因跨年活動而自發(fā)到來的人群,由于疏散管理不到位,引發(fā)大規(guī)模人群踩踏事故,造成近百人傷亡.成為近些年來,我國最嚴重的自發(fā)性人群聚集公共安全事故.蘇州市金雞湖城市廣場結(jié)合蘇州中心商場成為蘇州的地標建筑[2],該廣場占地約12 000 m2,2020年國慶期間,瞬時峰值人數(shù)突破120 000 人次,密度峰值超過每百平600 人次,一旦發(fā)生緊急情況,將會對人民的生命安全和財產(chǎn)損失產(chǎn)生巨大的影響.因此,以金雞湖城市廣場為例,研究公眾開放場所對人群疏散的影響具有指導意義.

目前,國內(nèi)外學者對大型公眾場所突發(fā)情況下的人群疏散進行了大量研究.其中,晉良海通過分析建筑空間布局的構(gòu)成要素,構(gòu)建公共建筑疏散空間的拓撲網(wǎng)絡,分析得出疏散路徑的人群負荷加載狀態(tài)對疏散效率的影響[3].Yang 等利用Pathfinder 軟件仿真模擬和分析得出了地鐵站內(nèi)部障礙物對人群疏散的影響[4].Helbing 等將體育場抽象成分層網(wǎng)絡,分析人員疏散由內(nèi)向外,由中心向四周疏散的特點,確定到安全區(qū)域的最佳疏散路線以提高應急疏散效率[5].王海紅等基于分層和強化學習改進路徑搜索算法,通過合理的減小網(wǎng)絡規(guī)模,保證算法求解精度的同時,改進了算法的效率[6].鞏青歌等通過分析已有的元胞自動機理論基礎,改進從眾吸引力算法,簡化復雜空間歐氏距離算法,從而提高危險排斥力和出口吸引力的量化效率[7].內(nèi)蒙古工業(yè)大學的楊文舉等應用元寶自動機和人工智能原理模擬人員的疏散,分析人群密度達到一定閾值時群體運動的規(guī)律,得出分塊劃分與出口“群體運動模擬”可以保證疏散的有效性[8].

以上研究都是改進路徑規(guī)劃算法的求解精度和求解速度,本文將安全出口通行能力因素作為路徑規(guī)劃算法的影響參數(shù),在路徑規(guī)劃初期就將安全出口條件考慮在內(nèi),實時動態(tài)調(diào)節(jié)分配人群到不同的安全出口,并且以所有人員最終撤離危險區(qū)域時間為算法評估參數(shù),從而獲得最優(yōu)的人群疏散解.使用Pathfinder 軟件仿真,對比自然疏散條件和傳統(tǒng)Dijkstra 算法疏散條件的人群疏散結(jié)果,驗證改進算法的有效性.

2 現(xiàn)代化廣場人群疏散問題的描述及分析

2.1 現(xiàn)代化廣場人群疏散問題的描述

現(xiàn)代化廣場成為城市居民和農(nóng)村居民的重要休閑娛樂場所.一般廣場具有占地面積大,出口位置不固定等特點,從而導致廣場中心區(qū)域到安全出口距離大的問題.同時現(xiàn)代化廣場,具有特定時間人群聚集性特點,特定時段人群數(shù)量陡增,成員復雜,人群密度高,因此將現(xiàn)代化廣場作為典型的大型公眾區(qū)域緊急疏散研究對象.

2.2 影響人群疏散的主要因素分析

(1)人群與出口距離

現(xiàn)代化廣場中心游玩區(qū)域距離各出口距離較遠.各游玩區(qū)域距離各個出口的距離不一致,人群與出口的疏散距離成為影響疏散用時的主要因素.游玩區(qū)域和出口區(qū)域的距離直接影響到路徑疏散中人群出口的選擇以及人群奔向出口的耗時.

(2)安全出口通行能力

現(xiàn)代化廣場一般具有多個安全出口,由于各出口的寬度不同,導致其通行能力具有一定差異,一定程度造成出口處的人群聚集問題,直接影響到廣場人群的疏散效率.

傳統(tǒng)Dijkstra 算法以兩節(jié)點間距離為權值參數(shù),利用貪心法則遍歷所有節(jié)點,最終獲取起點和終點的最短距離路徑.本文以傳統(tǒng)Dijkstra 算法為基礎,首先利用距離參數(shù)獲取起點與終點的所有路徑集合并且排序,然后引入安全出口通行能力參數(shù),重新對節(jié)點人群科學合理分配至各出口.最終獲取疏散時間更短的規(guī)劃路徑.

3 基于改進Dijkstra 算法的城市廣場突發(fā)情況下動態(tài)人群疏散模型

改進Dijkstra 算法路徑規(guī)劃流程圖如圖1所示.參考柏柳提出的一種多層域異構(gòu)交通數(shù)據(jù)融合模型來對動態(tài)環(huán)境信息中的人群節(jié)點位置信息和出口密度信息實時獲取[9].首先使用多列卷積神經(jīng)網(wǎng)絡(multi column convolutional neural network,MCNN)進行低空視角的人數(shù)估計,然后設計了一種基于高斯混合模型的密度分級算法,將高空監(jiān)控視頻中的人群密度以關鍵動點間的距離分級顯示[10].如圖2所示,結(jié)合低空監(jiān)控和高空監(jiān)控,將局部信息和全局信息互補融合,更加準確的獲取上述模型建立的參數(shù)信息,并且構(gòu)造成Dijkstra算法的新權值參數(shù).執(zhí)行Dijkstra 輸出人群節(jié)點到出口節(jié)點的最短時間路徑.將輸出結(jié)果帶入自己構(gòu)造的Ajust 算法,用來調(diào)節(jié)各條路徑的疏散人數(shù).最終輸出最優(yōu)的路徑和對應路徑上的行人數(shù)量.

圖1 改進Dijkstra 算法路徑規(guī)劃流程圖

圖2 疏散模型參數(shù)獲取

3.1 人群疏散模型的建立

由于城市廣場人群疏散問題較為復雜,且影響因素較多,為便于問題的研究,在此做以下假定:

(1)以每m人劃分為一個人群節(jié)點.初始設定為f個人群節(jié)點,共計M=m×f人(m>0,f>0);

(2)假定發(fā)生意外時,人群是在同一時間向出口疏散,且疏散速度μ一致(μ>0);

(3)假定廣場有n個出口,且各出口通行速率Hk確定 (n>0,Hk>0);

(4)最后一名人員成功疏散至廣場外,作為疏散完成的判定條件.以各出口最終疏散完成時間Tk_total的長短來判定疏散算法的優(yōu)劣.

城市廣場疏散系統(tǒng)的路網(wǎng)結(jié)構(gòu)用圖結(jié)構(gòu)來表示.G=(V,E),其中V∈ {[1,2,3,…],[A,B,C,…]}是圖G中所有節(jié)點的集合,[1,2,3,…] 共有f個人群節(jié)點集合,[A,B,C…]共有n個出口節(jié)點集合.弧集E={eij:i∈V,j∈V,i≠j}是弧的集合,其中eij表示從節(jié)點i到節(jié)點j的弧,長度用dij來表示.圖中路徑(如r={ei1i2,ei2i3,ein-1in})可用一系列首位相連的弧表示,{ei1i2,ei2i3,ein-1in}表示圖中路徑各條弧的長度.所以路徑長度等于所選路徑中各條弧的長度之和.

3.2 疏散路徑時間:Tfk_v_road

根據(jù)武漢大學與香港城市大學發(fā)展的SGEM 模型[11],人群的疏散速度與人群密度的關系可以用式(1)表示:

其中,μ表示不同密度下人群的移動速度(m/s),ρ表示人群密度(人/m2).整個廣場的人數(shù)設定為M=m×f(人),廣場移動區(qū)域面積為S(m2),式(2)計算出人群密度ρ.將ρ帶入式(1),即可得到人群的移動速度μ.

基于低空攝像,BIM和GIS 實時獲取人群地理位置信息.可以獲得各個人群節(jié)點與出口節(jié)點的區(qū)域位置和具體距離,從而構(gòu)成以距離為權值的鄰接矩陣G_dis,其中dij表示節(jié)點i到節(jié)點j的距離.

將式(3)鄰接矩陣中的各個參數(shù)dij除以式(1)得出的移動速率μ,整理得出以時間為權值的鄰接矩陣GT_road.

Dijkstra 算法原理如下:

Step 1.設置一個集合S存放已經(jīng)找到的最短路徑頂點,S的初始狀態(tài)只包含源點,對Si∈V-S,假設從源點S到Si的有向邊為最短路徑.

Step 2.以后每求得一條最短路徑d,…,dj,就將集合加入S中,并將路徑d,…,dj,Si與原來假設相比較,取路徑長度最小者為最短路徑.

Step 3.重復上述過程,直到集合V中全部頂點加入集合S中.

對鄰接矩陣GT_road執(zhí)行如上Dijkstra 算法.

其中,vf表示起點,vk表示終點,GT_road表示存儲各節(jié)點權值信息的鄰接矩陣.rvk表示由Dijkstra 算法得到的最短路徑.dij表示該最短路徑上的分支節(jié)點距離.Tfk_v_road表示從人群節(jié)點f到出口節(jié)點k的最短疏散路徑時間.

3.3 疏散出口時間:Tk_exit

疏散出口時間Tk_exit表示人群通過安全出口所花費的時間.參考光海鵬提出的安全出口空間特征對密集人群疏散的影響[12],獲得各安全出口通行能力Hk(人/s).

已知各出口通行能力Hk,由式(6)計算出每個出口理論通行人數(shù)與所有出口通行能力的比值Pk.

由式(7)Pk與疏散總?cè)藬?shù)M的乘積,可獲得各個出口節(jié)點的理論疏散人數(shù)Bk,由式(8)將出口理論疏散人數(shù)Bk除以對應出口疏散能力Hk.獲得該出口的疏散出口時間Tk_exit.

3.4 疏散模型總時長:Tk_total

由式(9)疏散路徑時間Tfk_v_road和疏散出口時間Tk_exit相加構(gòu)成疏散模型總時長Tk_total.表示在突發(fā)情況下,人群從游玩區(qū)域疏散到出口區(qū)域的時長Tfk_v_road,加上在安全出口處排隊疏散至廣場外安全區(qū)域的時間Tk_exit,構(gòu)成整個疏散過程的總時長.將傳統(tǒng)Dijkstra 算法改進成雙目標優(yōu)化算法.

式(10)中,αij? (0,1],代表障礙物等對各路徑疏散速度μ的影響.當無障礙物時,αij=1.當有障礙物時,0 <αij<1.αij與疏散路徑時間Tfk_v_road成反比.

式(11)中,β? (0,1],代表人口從出口疏散的誤差疏散效率.β=1,代表無誤差,疏散人數(shù)等于該出口理論疏散人數(shù)Bk.疏散過程中,前期疏散人數(shù)勢必小于通行能力Hk.故β與疏散出口時間Tk_exit成反比.β受到疏散人數(shù)m和疏散路徑時間Tfk_v_road影響.本文αij,β默認取值為1.

3.5 構(gòu)造人數(shù)調(diào)整Adust 算法

本文構(gòu)造了實時人數(shù)反饋調(diào)節(jié)Ajust 算法.

輸入?yún)?shù):各人群節(jié)點到各出口節(jié)點最短路徑rfk,,路徑rfk對應最短疏散時間Tfk_v_road,路徑rfk對應人群節(jié)點人數(shù)Mf及對應出口節(jié)點理論疏散人數(shù)Bk.

輸出參數(shù)為最優(yōu)路徑及對應疏散人數(shù).

Ajust 算法如下:

將4 個輸入?yún)?shù)構(gòu)造成Python 語法中“字典”變量類型.共計f×k條“字典”.執(zhí)行如下Adust 算法.

Adust [‘rfk’,Tfk_v_road,Mf,Bk]

Step 1.以Tfk_v_road由小到大對f×k條“字典”(‘rfk’,Tfk_v_road,Mf,Bk)排序.

Step 2.當Mf1

該人群節(jié)點人數(shù)小于該出口理論疏散人數(shù):

則刪除人群節(jié)點為f1的所有“字典”.

更新出口節(jié)點k1剩余疏散人數(shù)為Bk1—Mf1.重復Step 1.

Step 3.當Mf1≥Bk1時:

該人群節(jié)點人數(shù)大于該出口理論疏散人數(shù):

則刪除出口節(jié)點為k1的所有“字典”.

更新人群節(jié)點f1剩余人數(shù)為Mf1—Bk1.

重復Step 1.

重復以上3 個步驟,直到所有人群節(jié)點疏散至出口節(jié)點.

Adust [‘rfk’,Tfk_v_road,Mf,Bk]=fk_num

fk_num表示各人群節(jié)點疏散至各出口節(jié)點具體人數(shù).

4 案例分析

4.1 地理環(huán)境概況

蘇州市金雞湖城市廣場占地12 000 m2,以每1 200 人為一個人群節(jié)點,共設定5 個人群節(jié)點,人群總數(shù)為6 000 人,導入式(1)中,獲得人群行動速度μ為1.4 m/s.如圖3(a)表示由人群節(jié)點Vf{1,2,3,4,5},出口節(jié)點Vk{A,B,C,D}構(gòu)成的路網(wǎng)關系圖.由低空攝像,BIM和GIS 獲得各人群節(jié)點和出口節(jié)點位置距離(單位:m),同時用鄰接矩陣G_dis構(gòu)成各節(jié)點的距離關系.導入式(4),更新為以疏散路徑時間為權值的鄰接矩陣GT_road.

圖3 廣場節(jié)點路網(wǎng)結(jié)構(gòu)圖

金雞湖城市廣場共有4 個出口,分別為南朝向A 出口(寬度1.5 m),西朝向B 出口(寬度2 m)和C(出口寬度2 m),北朝向D 出口(寬度4 m).表1為不同寬度安全出口通行能力表.由表1獲取A 出口通行能力為5.231 人/s.出口B和出口C 通行能力為7.487 人/s.出口D 通行能力為19.031 人/s.

表1 不同寬度安全出口通行能力表[12]

運行Dijkstra 算法[13],獲得各個人群節(jié)點疏散至各個出口節(jié)點結(jié)果.人群節(jié)點1,2 均奔向出口A,人群節(jié)點3 奔向出口B,人群節(jié)點4,5 奔向出口D.同時,將廣場疏散總?cè)藬?shù)M=6000 人,帶入式(7),獲取各出口理論逃生人數(shù)Bk.數(shù)據(jù)整理如表2.如圖3所示,以金雞湖城市廣場為基礎構(gòu)建疏散路網(wǎng)結(jié)構(gòu)圖,圖4參考實際環(huán)境,在仿真軟件1:1 繪制廣場疏散環(huán)境模型.圖5則展示了Pathfinder 軟件模擬疏散過程.

圖4 城市廣場實景圖與Pathfinder 軟件繪制圖

圖5 Pathfinder 軟件模擬疏散過程

表2 多種情況疏散結(jié)果表 (單位:s)

4.2 人數(shù)動態(tài)調(diào)整

表3可以得出傳統(tǒng)Dijkstra 算法路徑規(guī)劃結(jié)果為TA_exit=458 s,TB_exit=160 s,TC_exit=0 sTD_exit=126 s.疏散出口時間Tk_exit差異巨大,由于C 出口沒有人群節(jié)點疏散,造成出口資源浪費.1,2 人群節(jié)點距離出口A 較近,故疏散至A 出口節(jié)點,但是A 出口通行能力較差,造成擁堵,疏散時間最長.各出口的理論疏散總?cè)藬?shù)為A 出口疏散804 人,B,C 出口各疏散1149 人,D 出口疏散2922 人.

表3 人群節(jié)點疏散至出口節(jié)點表

執(zhí)行Dijkstra 算法,輸出結(jié)果如表4,使用Adust算法合理分配人數(shù)至各出口,疏散結(jié)果如表5所示.

表4 人群動態(tài)調(diào)整至出口表

表5 動態(tài)人群出口分配表

人群節(jié)點1 轉(zhuǎn)移678 人至出口C,轉(zhuǎn)移522 至出口D.

人群節(jié)點2 轉(zhuǎn)移804 人至出口A,轉(zhuǎn)移396 人至出口C.

人群節(jié)點3 轉(zhuǎn)移1 149 人至出口B,轉(zhuǎn)移51 人至出口C.

人群節(jié)點4 轉(zhuǎn)移1 200 人至出口D,人群節(jié)點5 轉(zhuǎn)移1 200 人至出口D.式(5)可得疏散路徑時間Tfk_v_road:

T2A_v_road=29 s,T3B_v_road=35 s,T3C_v_road=41 s,T5D_v_road=28 s.

由式(8)得出疏散出口時間:Tk_exit=151 s.

由式(9)得出疏散模型總時間:

TA_total=T2A_v_road+TA_exit=180 s,TB_total=T3B_v_road+TB_exit=189 s,TC_total=T3C_v_road+TC_exit=192 s,TD_total=T5D_v_road+TD_exit=179 s.

5 軟件仿真

使用Pathfinder 軟件仿真模擬3 種情況下的人群疏散結(jié)果[14].情況1:Pathfinder 軟件自然疏散.情況2 使用傳統(tǒng)Dijkstra 算法路徑規(guī)劃.情況3 使用改進Dijkstra 算法和Ajust 人數(shù)調(diào)節(jié)算法結(jié)合輸出路徑規(guī)劃結(jié)果.

情況1 Pathfinder 自然仿真結(jié)果如圖6(a)所示,最早完成疏散出口為156 s.最晚完成疏散為A 出口209 s.

圖6 3 種疏散算法仿真對比結(jié)果

情況2 如圖6(b)所示,使用傳統(tǒng)Dijkstra 算法,以最短路徑為算法的主要參數(shù).由于C 出口無人疏散,導致模型疏散總時間差異巨大.最早完成疏散出口為D 出口,用時143 s.最晚完成疏散出口為A 出口,用時472 s.相差329 s.

情況3 如圖6(c)所示,改進Dijkstra 算法結(jié)合人群合理分配出口結(jié)果.最早完成疏散為C 出口172 s,最晚完成疏散為D 出口185 s.相差12.9 s,用時最短,對比3 種算法,最早完成疏散任務.

改進的Dijkstra 算法通過合理的分配人群到各個出口,完成人群疏散的結(jié)果最佳,比Pathfinder 軟件模擬自然疏散提升了10 s.傳統(tǒng)Dijkstra 算法只考慮最短路徑為權值,沒有考慮安全出口的疏散能力,導致人群大量擁堵在疏散能力差的出口,浪費了大量時間,疏散結(jié)果最差.

6 總結(jié)與展望

本文對蘇州市金雞湖城市廣場的人群疏散路徑規(guī)劃進行了研究.改進傳統(tǒng)Dijkstra 最短路徑權值為最短時間權值,同時加入人群人數(shù)反饋調(diào)節(jié)Ajust 算法,合理分配人群至不同出口,從而減少人群疏散時間.通過Pathfinder 軟件仿真,對比3 種條件下疏散結(jié)果,發(fā)現(xiàn)最大化利用所有出口資源對路徑規(guī)劃疏散效率有顯著提高.