胡小兵，袁莉燕，李航，趙宇勃，張勇，李奇軒

(1.中國民航大學(xué)，a.體系安全與智能決策實(shí)驗(yàn)室，b.電子信息與自動(dòng)化學(xué)院，c.中歐航空工程師學(xué)院，天津 300300；2.河北省高速公路京雄籌建處，河北保定 071000)

0 引言

隨著社會(huì)經(jīng)濟(jì)的快速發(fā)展，商場、景點(diǎn)、高鐵站及機(jī)場等大型公共場所的數(shù)量急劇增加，這些場所承載的人員密度極大，當(dāng)火災(zāi)、地震、危險(xiǎn)品爆炸等突發(fā)公共安全事件發(fā)生時(shí)，疏散人員會(huì)盲目選擇當(dāng)下距離出口最近的路線，極易造成路網(wǎng)中的擁堵現(xiàn)象，導(dǎo)致人員疏散不及時(shí)，引發(fā)一系列嚴(yán)重后果。因此，研究路網(wǎng)中疏散路徑優(yōu)化策略，給出一套準(zhǔn)確且高效的應(yīng)急疏散方案對(duì)于提高路網(wǎng)中人群疏散效率，減少人員傷亡和財(cái)產(chǎn)損失具有重要意義。

處理路網(wǎng)中人群應(yīng)急疏散問題的關(guān)鍵在于疏散路徑優(yōu)化，應(yīng)急疏散路徑優(yōu)化問題是一個(gè)典型的NP-hard問題[1]。目前，求解該問題的方法主要分為兩類。

一類是聚焦微觀層面的模擬仿真類方法，該類方法通過建立微觀模型，突出刻畫疏散人員在受到多種因素影響時(shí)產(chǎn)生的個(gè)體行為，以此來確定最優(yōu)疏散路徑。常見微觀模型主要有元胞自動(dòng)機(jī)模型(Cellular Automata,CA)[2]、社會(huì)力模型(Social Force Model,SFM)[3]和格子氣模型(Lattice Gas Model,LGM)[4]。模擬仿真類方法能更細(xì)致地反映疏散人員的狀態(tài)，但同時(shí)也會(huì)增加求解復(fù)雜度，使得求解時(shí)間較長。

另一類方法是聚焦宏觀層面的智能優(yōu)化類方法，該類方法從全局角度為疏散人員分配最優(yōu)路徑，以期提高整體的疏散效率。Zhao等[5]提出一種新的出口評(píng)估策略，結(jié)合人工蜂群算法進(jìn)行疏散路徑優(yōu)化。Huang等[6]在蟻群算法中引入增量流量分配方法(Incremental Flow Assignment,IFA)來實(shí)現(xiàn)路徑優(yōu)化，提高人群疏散效率。Liu等[7]提出一種改進(jìn)的多路線人工魚群算法，解決郵輪上的多路線疏散路徑優(yōu)化問題。劉濤[8]基于改進(jìn)蟻群算法構(gòu)建疏散路徑優(yōu)化策略，處理結(jié)構(gòu)較為復(fù)雜的多層建筑中的人群疏散。這類啟發(fā)式算法參數(shù)較多，在求解時(shí)易陷入局部最優(yōu)，較難保證解的質(zhì)量。羅茂穎[9]對(duì)Dijkstra 算法進(jìn)行了數(shù)據(jù)儲(chǔ)存優(yōu)化和堆優(yōu)化，求解特定節(jié)點(diǎn)到各安全出口的距離最短路徑。Li等[10]使用障礙物的頂點(diǎn)來構(gòu)建路徑節(jié)點(diǎn)，并綜合考慮了節(jié)點(diǎn)的安全性，求解出最短路徑。上述研究都以尋找距離最短路徑為目標(biāo)，頻繁求解得出最短路徑容易造成疏散時(shí)路網(wǎng)中的擁堵，延長疏散時(shí)間。張明空等[11]提出一種協(xié)同進(jìn)化路徑優(yōu)化方法，實(shí)現(xiàn)了動(dòng)態(tài)火災(zāi)情景下應(yīng)急疏散路徑的動(dòng)態(tài)優(yōu)化，有效提高了高層建筑的疏散效果，但該方法只考慮了具有單起點(diǎn)單終點(diǎn)的路網(wǎng)場景。

綜上所述，本文提出一種考慮容量限制的多起點(diǎn)多終點(diǎn)漣漪擴(kuò)散算法(Capacity Constrained Ripple Spreading Algorithm,CCRSA)。該算法綜合考慮路徑容量限制與具有多起點(diǎn)多終點(diǎn)路網(wǎng)的人群流量分配情況，計(jì)算得出各起點(diǎn)的全局疏散時(shí)間最短路徑，動(dòng)態(tài)更新路網(wǎng)中各鏈接在各時(shí)刻的剩余最大通行容量，并根據(jù)路徑尋優(yōu)規(guī)則來確定最優(yōu)疏散路徑，實(shí)行差異化疏散，有效提高路網(wǎng)中人群疏散效率，優(yōu)化應(yīng)急疏散方案。

1 問題描述

在進(jìn)行人群疏散路徑優(yōu)化時(shí)，需要考慮路徑容量限制等一系列約束條件，在保證安全性的前提下，為某一場所內(nèi)分布在不同位置的所有人員合理安排疏散時(shí)間點(diǎn)、優(yōu)化疏散路徑，使得在最短時(shí)間內(nèi)所有人都能夠到達(dá)安全出口。

由于在實(shí)際路網(wǎng)的人群疏散過程中，疏散情況較為復(fù)雜，故本文做如下假設(shè)：

(1) 疏散路網(wǎng)存在多個(gè)起點(diǎn)和多個(gè)安全出口，疏散開始時(shí)，每名待疏散人員隨機(jī)分布于各個(gè)起點(diǎn)；

(2)疏散路網(wǎng)中的鏈接等效于實(shí)際道路，具有一定的單位時(shí)間通行容量上限，且容量上限的大小取決于每條鏈接的寬度；

(3)疏散人員在各條鏈接上具有一定的移動(dòng)速度，即每條鏈接的通行時(shí)間為常數(shù)；

(4)疏散過程中允許疏散人員在路網(wǎng)的節(jié)點(diǎn)處等待。

圖1展示了不同方案路徑選擇對(duì)比，各鏈接的屬性以(x,y)表示，其中，x表示該鏈接的單位時(shí)間最大通行容量，y表示該鏈接的通行時(shí)間，假設(shè)初始時(shí)刻起點(diǎn)5 的待疏散人數(shù)為10 人。若所有人員均選擇起點(diǎn)到終點(diǎn)的距離最短路徑[5,4,3]進(jìn)行疏散，10人全部疏散用時(shí)7 s，產(chǎn)生的等待時(shí)間為4 s；而優(yōu)化后疏散路徑為2 人選擇路徑[5,4,3]，3 人選擇路徑[5,0]，3 人選擇路徑[5,2,3]，2 人等待1 s 后選擇路徑[5,4,3]，則10 人全部疏散只需用時(shí)5 s，產(chǎn)生的等待時(shí)間只有1 s。所使用的符號(hào)和決策變量如表1所示。

表1 使用的變量符號(hào)說明Table 1 Description of variables and symbols

圖1 路徑選擇方案對(duì)比Fig.1 Comparison of path selection schemes

1.1 路網(wǎng)建模

構(gòu)建人群疏散路網(wǎng)模型。給定一個(gè)路網(wǎng)G(N,E)由節(jié)點(diǎn)集合N和鏈接集合E組成。節(jié)點(diǎn)集合N包含起點(diǎn)即待疏散人員所在節(jié)點(diǎn)集合Ns={sk},k∈{1,2,…,o}，普通中間節(jié)點(diǎn)集合Nu={uk},k∈{1,2,…,q}，終點(diǎn)即安全出口集合Nd={dk},k∈{1,2,…,z} 。鏈接集合E={eij|i∈N,j∈N} 囊括了所有相連節(jié)點(diǎn)間的鏈接，其中，eij為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的鏈接，表示實(shí)際可通行的路徑，則相鄰節(jié)點(diǎn)對(duì)集合可表示為V={(i,j)|eij∈E} 。使用鄰接矩陣A來構(gòu)建實(shí)際路網(wǎng)，即

其中，若lij>0，則表示路網(wǎng)中節(jié)點(diǎn)i與節(jié)點(diǎn)j間的鏈接eij的長度為lij；若lij=0，則表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間不存在鏈接，無實(shí)際通行道路。此外，A(i,i)=0，即任意節(jié)點(diǎn)i與自身不存在相連的鏈接。

疏散人員在鏈接eij上的移動(dòng)速度為vij，則鏈接eij的通行時(shí)間為

使用式(2)計(jì)算得到各鏈接的通行時(shí)間，并構(gòu)成以通行時(shí)間為權(quán)值的鄰接矩陣T，即

路網(wǎng)中的任意鏈接都存在單位時(shí)間內(nèi)允許通行的人數(shù)上限，鏈接eij的最大通行容量為cij，則最大通行容量鄰接矩陣C可表示為

1.2 優(yōu)化目標(biāo)

優(yōu)化目標(biāo)為最小化路網(wǎng)中所有待疏散人員的清空時(shí)間，即最小化路網(wǎng)中最后一位待疏散人員到達(dá)安全出口的時(shí)間。優(yōu)化目標(biāo)可描述為

1.3 約束條件

式(6)表示在初始時(shí)刻路網(wǎng)在各中間節(jié)點(diǎn)和終點(diǎn)的疏散人員數(shù)量為0。式(7)和式(8)分別表示在初始時(shí)刻位于各鏈接、各終點(diǎn)的疏散人員數(shù)量為0。式(9)表示在任意時(shí)刻t各鏈接的疏散人員數(shù)量都不得超過該鏈接當(dāng)前的剩余最大通行容量。式(10)表示通過任意節(jié)點(diǎn)的疏散人員數(shù)量守恒。式(11)表示在任意時(shí)刻t從每個(gè)起點(diǎn)出發(fā)的疏散人員數(shù)量守恒。式(12)表示疏散人員總?cè)藬?shù)守恒，即初始時(shí)刻各起點(diǎn)的疏散人員數(shù)量總和等于疏散結(jié)束時(shí)位于各終點(diǎn)的疏散人員數(shù)量總和。式(13)表示若來自起點(diǎn)sk的疏散人員m在t時(shí)刻位于鏈接(i,j)，則決策變量，否則

2 求解算法

針對(duì)應(yīng)急疏散路徑優(yōu)化問題，設(shè)立人員移動(dòng)規(guī)則、人員等待規(guī)則與路徑尋優(yōu)規(guī)則，提出考慮容量限制的多起點(diǎn)多終點(diǎn)漣漪擴(kuò)散算法(CCRSA)。

2.1 疏散規(guī)則

2.1.1 人員移動(dòng)規(guī)則

疏散人員在鏈接上移動(dòng)時(shí)，遵守先進(jìn)先出(First-in-first-out，F(xiàn)IFO)規(guī)則。如圖2 所示，feva(t,1)和feva(t,2)表示在t時(shí)刻位于鏈接eij上的兩組疏散人員，第1 組疏散人員feva(t,1)經(jīng)過Δt時(shí)間后由位置(2)移動(dòng)到位置(4)，第2 組疏散人員feva(t,2)經(jīng)過Δt時(shí)間后由位置(1)移動(dòng)到位置(3)。在移動(dòng)過程中，第2組疏散人員始終排在第1 組疏散人員的后面。

圖2 單條鏈接人員移動(dòng)規(guī)則Fig.2 Movement rule of evacuees on single link

當(dāng)多條鏈接交匯時(shí)，疏散人員的移動(dòng)同樣遵循FIFO 移動(dòng)規(guī)則。如圖3 所示，鏈接es1u3和鏈接es2u3在節(jié)點(diǎn)u3處交匯，并與鏈接eu3d4相連。其中各鏈接中矩陣的列數(shù)表示該鏈接的通行時(shí)間長度，譬如es1u3的矩陣有兩列，表示通過該鏈接需要2 s；矩陣的行數(shù)表示該鏈接的最大通行容量，es1u3的矩陣有一行，則表示其最大單位時(shí)間通行容量為1；矩陣中的元素表示在當(dāng)前時(shí)刻該位置是否有疏散人員，1表示有，0 表示沒有。t=1 時(shí)有1 名疏散人員從鏈接es1u3運(yùn)動(dòng)至鏈接eu3d4，又有兩名疏散人員從鏈接es2u3運(yùn)動(dòng)至鏈接eu3d4，則t=1時(shí)共有3名疏散人員到達(dá)鏈接eu3d4。同理，t=2 時(shí)共有1 名新的疏散人員到達(dá)鏈接eu3d4。

圖3 鏈接交匯人員移動(dòng)規(guī)則Fig.3 Movement rule of evacuees at link crossover

2.1.2 人員等待規(guī)則

Adrian等[12]歸納出，在出現(xiàn)突發(fā)情況時(shí)，人群易激發(fā)自我心理，盲目尋找距出口最近的疏散路線，這樣反而會(huì)導(dǎo)致路網(wǎng)中產(chǎn)生大面積擁堵，延長疏散時(shí)間，出現(xiàn)“快即是慢”的效應(yīng)。因此，為充分利用每條疏散路線，更好地緩解疏散時(shí)的擁堵，為疏散人員在路網(wǎng)中的節(jié)點(diǎn)處增加等待行為，可以有效減少整個(gè)路網(wǎng)中所有疏散人員的清空時(shí)間。

疏散人員在節(jié)點(diǎn)i處的等待時(shí)間ti,wait可以描述為

疏散人員在規(guī)劃好的疏散路徑ps上通行時(shí)，其疏散時(shí)間Hs可描述為

2.1.3 路徑尋優(yōu)規(guī)則

隨著疏散的進(jìn)行，路網(wǎng)中各鏈接各時(shí)刻的剩余最大通行容量不斷更新。通過考慮每條鏈接的通行時(shí)間，以及其在疏散人員到達(dá)該鏈接時(shí)的剩余最大通行容量，來設(shè)置路徑尋優(yōu)規(guī)則，確定優(yōu)先疏散路徑，路徑尋優(yōu)的評(píng)價(jià)標(biāo)準(zhǔn)為

式(16)中分子為疏散人員在路徑ps的疏散時(shí)間Hs，分母為組成路徑ps的各鏈接在疏散人員到達(dá)時(shí)的剩余最大通行容量與起點(diǎn)待疏散人數(shù)中的最小值。該比值最小的路徑為優(yōu)先疏散路徑。

2.2 CCRSA

2.2.1 多對(duì)多RSA

漣漪擴(kuò)散算法(Ripple-spreadingAlgorithm,RSA)的提出是受到自然界中漣漪擴(kuò)散現(xiàn)象的啟發(fā)。其路徑搜索過程是模擬漣漪在水面上向四周以相同速度擴(kuò)散，它總是最先到達(dá)距漣漪中心最近的節(jié)點(diǎn)。當(dāng)漣漪觸碰到障礙物即新的節(jié)點(diǎn)時(shí)，又會(huì)觸發(fā)新的漣漪繼續(xù)擴(kuò)散。因此其路徑搜索過程可以形象地描述為路網(wǎng)中各個(gè)節(jié)點(diǎn)間的漣漪接力賽。

多對(duì)多漣漪擴(kuò)散算法原理如圖4 所示，t=1時(shí)，起點(diǎn)1和起點(diǎn)5分別產(chǎn)生漣漪R1和R2，在路網(wǎng)中開始擴(kuò)散；t=2 時(shí)，R2到達(dá)節(jié)點(diǎn)4，并在節(jié)點(diǎn)4處激發(fā)新的漣漪R3；t=3 時(shí)，R1到達(dá)終點(diǎn)0，通過回溯找到起點(diǎn)1到達(dá)終點(diǎn)的最短路徑[1,0]，該漣漪消亡；t=4 時(shí)，R3到達(dá)終點(diǎn)3，通過回溯找到起點(diǎn)5到達(dá)終點(diǎn)的最短路徑[5,4,3]，所有漣漪消亡。

圖4 多對(duì)多漣漪擴(kuò)散算法原理Fig.4 Principle of many-to-many RSA

2.2.2 CCRSA求解流程

RSA 在路徑優(yōu)化方面的優(yōu)勢已經(jīng)得到證明[13]。結(jié)合2.1 節(jié)所設(shè)置的疏散規(guī)則，提出CCRSA，動(dòng)態(tài)更新路網(wǎng)中各鏈接在各時(shí)刻的剩余最大通行容量，容量不足時(shí)添加漣漪在節(jié)點(diǎn)的等待行為，將等待時(shí)間考慮在內(nèi)，一次性計(jì)算出多個(gè)起點(diǎn)到多個(gè)終點(diǎn)的疏散時(shí)間最短路徑；并使用路徑尋優(yōu)規(guī)則確定優(yōu)先疏散路徑，分配疏散人員數(shù)量，實(shí)行差異化疏散，提高路網(wǎng)中各鏈接的利用率。

CCRSA 使用的符號(hào)說明如表2 所示，CCRSA偽代碼如表3所示。

表2 CCRSA符號(hào)說明Table 2 Description of symbols in CCRSA

表3 CCRSA求解流程Table 3 Working flow of CCRSA

CCRSA的求解流程如下。

Step 1 初始化路網(wǎng)，給定各起點(diǎn)sk的待疏散人數(shù)(0)、各鏈接的最大通行容量C和各鏈接的通行時(shí)間T。

Step 2 判斷各起點(diǎn)是否存在未疏散人員，若不存在，則算法運(yùn)行終止；若存在，則算法繼續(xù)運(yùn)行，即表3第1行。

Step 3 初始化各漣漪狀態(tài)，設(shè)置漣漪的擴(kuò)散速度，即表3第2～4行。

Step 4 判斷各起點(diǎn)的漣漪是否都通過漣漪接力賽到達(dá)終點(diǎn)，若是，則轉(zhuǎn)至Step 10；否則，轉(zhuǎn)至Step 5，即表3第5行。

Step 5 漣漪狀態(tài)更新，對(duì)處于等待狀態(tài)漣漪，當(dāng)與其中心點(diǎn)相連的某一鏈接當(dāng)前剩余最大容量滿足Xij(t)>0 時(shí)，漣漪在該方向上由等待狀態(tài)變?yōu)榧せ顮顟B(tài)，并記錄等待時(shí)間ti,wait，即表3第7～11行。

Step 6 所有激活狀態(tài)的漣漪以速度v開始擴(kuò)散，即表3第12行。

Step 7 對(duì)于所有處于激活狀態(tài)的漣漪，判斷是否到達(dá)其中心節(jié)點(diǎn)的相鄰節(jié)點(diǎn)。若是，則在相鄰節(jié)點(diǎn)處觸發(fā)新的漣漪，并更新到達(dá)節(jié)點(diǎn)時(shí)間，即表3第13～16行。

Step 8 根據(jù)各鏈接的剩余最大容量，判斷新漣漪在各方向上的狀態(tài)，即表3第17～23行。

Step 9 當(dāng)漣漪已到達(dá)其中心節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)后，漣漪消亡，即表3第24～26行。

Step 10 根據(jù)路徑尋優(yōu)規(guī)則，確定優(yōu)先疏散路徑ps，并確定本次疏散人員數(shù)量fs，即表3 第28行。

Step 11 根據(jù)本次疏散人員數(shù)量和到達(dá)各節(jié)點(diǎn)的時(shí)間，更新各鏈接在對(duì)應(yīng)時(shí)刻的剩余最大容量和起點(diǎn)待疏散人數(shù)，即表3第30行。

Step 12 本次疏散結(jié)束，開啟下一輪疏散時(shí)間最優(yōu)路徑搜索，直至各起點(diǎn)所有人員都被疏散至終點(diǎn)，輸出Pfin,Ffin,Hend。

3 實(shí)驗(yàn)分析

本節(jié)使用大量的隨機(jī)生成路網(wǎng)對(duì)算法進(jìn)行測試，并將CCRSA 的實(shí)驗(yàn)結(jié)果與多路徑容量約束規(guī)劃算法(Multiple-Route Capacity Constrained Planner,MRCCP)、遺傳算法(Genetic Algorithms,GA)的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析。此外，使用一個(gè)實(shí)際案例來證明CCRSA 的應(yīng)用價(jià)值。所有算法和測試均使用Python3.9 編程實(shí)現(xiàn)，并以配置 為Windows10，Intel(R) Core(TM) i7-9700CPU，3 GHz，16.0 GB RAM 的計(jì)算機(jī)作為實(shí)驗(yàn)平臺(tái)，開展對(duì)比實(shí)驗(yàn)。

設(shè)置3 個(gè)評(píng)價(jià)指標(biāo)ET、RT、Std。ET 表示路網(wǎng)中所有待疏散人員全部到達(dá)安全出口所需的時(shí)間，即清空時(shí)間(s)；RT 表示程序運(yùn)行時(shí)間(s)；Std 表示每名疏散人員到達(dá)出口的實(shí)際時(shí)間與理想時(shí)間的標(biāo)準(zhǔn)差。每名疏散人員都希望在最短時(shí)間內(nèi)到達(dá)安全出口，故將其理想疏散時(shí)間設(shè)置為在不考慮等待時(shí)間的情況下所在起點(diǎn)到終點(diǎn)的最短路徑通行時(shí)間。標(biāo)準(zhǔn)差計(jì)算公式為

式中：m為第m個(gè)待疏散人員；tm,act為疏散人員m到達(dá)終點(diǎn)的實(shí)際時(shí)間；tm,ide為疏散人員m到達(dá)終點(diǎn)的理想時(shí)間。標(biāo)準(zhǔn)差Std 越小，表明疏散時(shí)間越符合疏散人員的心理預(yù)期。

在進(jìn)行每次對(duì)比實(shí)驗(yàn)時(shí)，為了保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，對(duì)于每一個(gè)算例，都將GA 運(yùn)行300 次，從300次實(shí)驗(yàn)結(jié)果中取出ET、RT與Std的最小值記為對(duì)于本算例GA的最優(yōu)解，即GA_Best。

3.1 隨機(jī)路網(wǎng)對(duì)比實(shí)驗(yàn)

使用NetworkX 生成4 組具有不同節(jié)點(diǎn)數(shù)量的路網(wǎng)，其中每組路網(wǎng)共包括10 個(gè)節(jié)點(diǎn)數(shù)量相同的隨機(jī)路網(wǎng)，每組路網(wǎng)中各鏈接的長度與最大通行容量都具有相同數(shù)量級(jí)。對(duì)每個(gè)路網(wǎng)都分配4 次不同數(shù)量的疏散人員進(jìn)行實(shí)驗(yàn)，每次實(shí)驗(yàn)的待疏散人員數(shù)量以節(jié)點(diǎn)數(shù)量的整數(shù)倍形式依次遞增。具體路網(wǎng)參數(shù)設(shè)置如表4 所示。對(duì)每組路網(wǎng)中10 個(gè)算例的實(shí)驗(yàn)結(jié)果取平均值，對(duì)比實(shí)驗(yàn)結(jié)果如表5所示。

表4 路網(wǎng)參數(shù)設(shè)置Table 4 Setting of road network parameters

表5 對(duì)比實(shí)驗(yàn)結(jié)果Table 5 Result of comparative experiments

由表5實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析可得以下結(jié)論：

(1)從4組實(shí)驗(yàn)結(jié)果整體來看，在具有相同節(jié)點(diǎn)數(shù)量的路網(wǎng)中，對(duì)于不同數(shù)量的待疏散人員，CCRSA 的疏散時(shí)間ET 均為3 種算法中的最小值。且相較于MRCCP和GA，CCRSA在疏散時(shí)間ET方面性能的提升隨著路網(wǎng)節(jié)點(diǎn)數(shù)量的不斷增多而逐漸增大。如表6 所示，分別與MRCCP 和GA_Best相比，在路網(wǎng)節(jié)點(diǎn)數(shù)量分別多于25與50時(shí)，CCRSA在減少疏散時(shí)間方面性能的提升可超過10%。由此可見，隨著待疏散人員增多與路網(wǎng)規(guī)模增大，CCRSA在減少疏散時(shí)間方面的效果愈發(fā)明顯。

表6 CCRSA對(duì)ET的提升效果Table 6 Improvement effect of CCRSA on ET

(2)4 種不同規(guī)模的路網(wǎng)中對(duì)于不同數(shù)量的待疏散人員，實(shí)驗(yàn)結(jié)果中CCRSA 的標(biāo)準(zhǔn)差Std 均為3 種算法中的最小值。且標(biāo)準(zhǔn)差值較為穩(wěn)定，并未隨著路網(wǎng)節(jié)點(diǎn)數(shù)量的增加而明顯上升，故表明使用CCRSA優(yōu)化得到的疏散路徑更加符合待疏散人員的心理預(yù)期，可以較好地滿足各疏散人員在期望時(shí)間內(nèi)快速疏散至安全出口的實(shí)際需求。

(3)當(dāng)路網(wǎng)節(jié)點(diǎn)數(shù)量大于25 時(shí)，相較于其他兩種算法，CCRSA 具有更短的程序運(yùn)行時(shí)間RT。且CCRSA 相對(duì)于其他兩種算法運(yùn)行效率的提升，隨著待疏散人數(shù)的增多與路網(wǎng)節(jié)點(diǎn)數(shù)量的增加而逐漸增大。以第4 組具有100 個(gè)節(jié)點(diǎn)的路網(wǎng)、1900 名待疏散人員的實(shí)驗(yàn)結(jié)果為例，相較于MRCCP 與GA_BEST，CCRSA的運(yùn)行效率分別提升88.21%與92.77%。原因在于RSA與大多數(shù)確定性自上而下的集中式路徑優(yōu)化方法(如Dijkstra算法)不同，RSA是一種自下而上的基于微觀智體的算法，在尋路過程中不需要計(jì)算比較從起點(diǎn)到中間節(jié)點(diǎn)的路徑時(shí)間長度，而是模擬漣漪在路網(wǎng)中傳播和在節(jié)點(diǎn)處激活新漣漪的行為，因此在處理大規(guī)模路網(wǎng)的人群疏散問題時(shí)，在計(jì)算效率方面具有更明顯的優(yōu)勢。

3.2 實(shí)際路網(wǎng)對(duì)比實(shí)驗(yàn)

選取北京市著名旅游景點(diǎn)頤和園作為實(shí)際案例驗(yàn)證算法的實(shí)際應(yīng)用價(jià)值。頤和園作為大型公共場所，人員分布較為密集，亟需制定應(yīng)對(duì)突發(fā)情況的人群應(yīng)急疏散方案。2023年4月12日，頤和園10:00 實(shí)時(shí)在園人數(shù)達(dá)15000 人，15:00 實(shí)時(shí)在園人數(shù)達(dá)到35000 人。圖5(a)為頤和園全景路網(wǎng)圖，圖5(b)為頤和園的四大部洲及萬壽山景區(qū)附近，地形較為復(fù)雜，該部分路網(wǎng)共包含65 個(gè)節(jié)點(diǎn)。根據(jù)實(shí)時(shí)在園人數(shù)數(shù)據(jù)，設(shè)置5 組實(shí)驗(yàn)，待疏散人數(shù)分別為700，900，1100，1300，1500 人，待疏散人員隨機(jī)分布在26 個(gè)起點(diǎn)，并設(shè)置4 個(gè)終點(diǎn)即安全出口，測試路網(wǎng)及人員分布如圖5(b)所示。對(duì)CCRSA、MRCCP、GA 開展對(duì)比實(shí)驗(yàn)，分析結(jié)果。實(shí)驗(yàn)結(jié)果如圖6所示。

圖5 實(shí)際案例分析路網(wǎng)圖Fig.5 Road network of case study

圖6 實(shí)際案例對(duì)比實(shí)驗(yàn)結(jié)果Fig.6 Result of comparative experiments on case study

圖6(a)為3種算法疏散時(shí)間的對(duì)比情況，可以看出，對(duì)于不同數(shù)量的待疏散人員，使用CCRSA均可獲得更短的疏散時(shí)間。針對(duì)5組不同數(shù)量待疏散人員的分布情況，相較于MRCCP，CCRSA分別減少了11.81%、11.21%、11.36%、14.38%、15.52%的疏散時(shí)間，相較于GA_BEST，CCRSA分別減少了20.49%、24.26%、26.41%、27.62%、28.29%的疏散時(shí)間。

圖6(b)對(duì)比了3種算法的標(biāo)準(zhǔn)差。針對(duì)5組不同數(shù)量待疏散人員的分布情況，CCRSA 的標(biāo)準(zhǔn)差均為3種算法中的最小值，CCRSA求解得出的疏散方案更加貼合各疏散人員的期望。

圖6(c)對(duì)比了3 種算法的程序運(yùn)行時(shí)間。5 組實(shí)驗(yàn)中，CCRSA的運(yùn)行效率較高，且在其他兩種算法的程序運(yùn)行時(shí)間隨人數(shù)增加而快速增長的情況下，CCRSA 運(yùn)行時(shí)間的增長幅度較小，為3 種算法中的最小值，較為穩(wěn)定。

通過對(duì)此實(shí)際案例的分析，證明了CCRSA 在實(shí)際路網(wǎng)環(huán)境中具有一定的實(shí)際應(yīng)用價(jià)值。

4 結(jié)論

本文得到的主要結(jié)論如下：

(1) CCRSA 為路網(wǎng)中的人群提供疏散路徑優(yōu)化策略，提高了路網(wǎng)中各鏈接的利用率，實(shí)現(xiàn)了差異化疏散，可以有效減少人群疏散時(shí)間。與傳統(tǒng)算法相比，CCRSA 平均可減少13.07%的人群疏散時(shí)間，且所得疏散方案中各疏散人員的實(shí)際疏散時(shí)間更為貼近其自身的期望值。

(2) 隨機(jī)實(shí)驗(yàn)和頤和園實(shí)際案例分析表明，CCRSA 的運(yùn)行效率較高且較為穩(wěn)定，其程序運(yùn)行時(shí)間不會(huì)隨著疏散人員的增多與路網(wǎng)規(guī)模的擴(kuò)大而顯著增長，并且CCRSA 在運(yùn)行效率方面的優(yōu)勢會(huì)隨著路網(wǎng)規(guī)模的增大、疏散人員的增多而更加明顯。CCRSA較適用于大規(guī)模路網(wǎng)的應(yīng)急疏散路徑優(yōu)化。