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

任少?gòu)?qiáng),汪一鳴

1(蘇州大學(xué),蘇州 215031)

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

1 引言

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

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

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

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

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

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

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

(1)人群與出口距離

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

(2)安全出口通行能力

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

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

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

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

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

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

3.1 人群疏散模型的建立

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

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

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

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

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

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

3.2 疏散路徑時(shí)間:Tfk_v_road

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

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

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

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

Dijkstra 算法原理如下:

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

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

Step 3.重復(fù)上述過程,直到集合V中全部頂點(diǎn)加入集合S中.

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

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

3.3 疏散出口時(shí)間:Tk_exit

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

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

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

3.4 疏散模型總時(shí)長(zhǎng):Tk_total

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

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

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

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

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

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

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

Ajust 算法如下:

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

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

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

Step 2.當(dāng)Mf1

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

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

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

Step 3.當(dāng)Mf1≥Bk1時(shí):

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

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

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

重復(fù)Step 1.

重復(fù)以上3 個(gè)步驟,直到所有人群節(jié)點(diǎn)疏散至出口節(jié)點(diǎn).

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

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

4 案例分析

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

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

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

金雞湖城市廣場(chǎng)共有4 個(gè)出口,分別為南朝向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]

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

圖4 城市廣場(chǎng)實(shí)景圖與Pathfinder 軟件繪制圖

圖5 Pathfinder 軟件模擬疏散過程

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

4.2 人數(shù)動(dòng)態(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.疏散出口時(shí)間Tk_exit差異巨大,由于C 出口沒有人群節(jié)點(diǎn)疏散,造成出口資源浪費(fèi).1,2 人群節(jié)點(diǎn)距離出口A 較近,故疏散至A 出口節(jié)點(diǎn),但是A 出口通行能力較差,造成擁堵,疏散時(shí)間最長(zhǎng).各出口的理論疏散總?cè)藬?shù)為A 出口疏散804 人,B,C 出口各疏散1149 人,D 出口疏散2922 人.

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

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

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

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

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

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

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

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

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

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

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

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 使用改進(jìn)Dijkstra 算法和Ajust 人數(shù)調(diào)節(jié)算法結(jié)合輸出路徑規(guī)劃結(jié)果.

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

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

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

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

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

6 總結(jié)與展望

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