人群疏散平移矩陣算法

摘 要：建筑物的通行能力研究近年來受到廣泛關注，安全高效地流通人群是專家學者研究的重點。首先，通過一組節點和邊的定義將建筑物表示為網絡，進而利用Dijkstra最短路算法生成最短路徑集合，最后在該集合的基礎上提出平移矩陣算法，利用0-1矩陣的更新模擬人群在建筑路徑上的流動過程。通過設置多組教學樓疏散場景并與Pathfinder軟件的對比來驗證平移矩陣算法的有效性。對比結果顯示，不同密度下兩種方法的總疏散時間差都約為50 s，而運算速度平移矩陣算法比Pathfinder軟件快10～110倍。該算法為人群疏散的快速模擬提供了新思路，為疏散策略的實時生成提供了可能性。

關鍵詞：Dijkstra最短路算法； 建筑網絡模型； 平移矩陣算法； 人群疏散模型； Pathfinder軟件

中圖分類號：TP399 文獻標志碼：A

文章編號：1001-3695（2022）03-033-0836-05

doi：10.19734/j.issn.1001-3695.2021.09.0390

基金項目：國家自然科學基金青年項目（52102414）；上海市揚帆計劃資助項目（21YF1431200）；國家自然科學基金面上項目（72074149）

作者簡介：黃中意（1992-），男，河南信陽人，講師，碩導，博士，主要研究方向為行人疏散動力學；易鑫（1999-），男，四川營山人，本科生，主要研究方向為系統優化；傅田棟（1999-），男，浙江杭州人，研究生，主要研究方向為系統優化；房志明（1986-），男（通信作者），山東武城人，教授，博導，博士，主要研究方向為突發事件下人群安全動力學（zhmfang2015@163.com）.

Translation matrix algorithm for crowd evacuation

Huang Zhongyi¹， Yi Xin¹， Fu Tiandong²， Fang Zhiming^1?

（1.Business School， University of Shanghai for Science amp; Technology， Shanghai 200082， China; 2.School of Securities amp; Futures， Southwes-tern University of Finance amp; Economics， Chengdu 611130， China）

Abstract：In recent years， the study of building capacity has been widely concerned， and how to circulate people safely and efficiently is the one of the main focus of experts and scholars. At first， the building was represented as a network through the definition of a set of nodes and edge， and then the shortest path was generated by using the Dijkstra algorithm. At last， on the basis of the generated set， this paper proposed the translation matrix algorithm， and simulated the flow process of the crowd on the building path by updating a 0-1 matrix. It verified the effectiveness of the translation matrix algorithm by setting multiple groups of teaching building evacuation scenes and comparing with Pathfinder software. The comparison results show that the total evacuation time difference of the two methods under different densities is about 50 s， while the translation matrix algorithm is 10～110 times faster than Pathfinder software. This algorithm provides a new idea for fast simulation of crowd evacuation and a possibility for real-time generation of evacuation strategy.

Key words：Dijkstra shortest path algorithm; network model of building; translation matrix algorithm; crowd evacuation model; Pathfinder software

0 引言

隨著城市的快速發展，同時聚集大量人群的建筑越來越常見，估算大規模人群流通時間關系到建筑的使用效能和安全性能，近年來受到廣泛關注。目前，在人群流通的研究領域已有諸多比較成熟的方法，其中比較主流的方法包括模擬仿真^[1]、實地觀測^[2]和控制實驗^[3]。按照是否考慮個體的運動特征，仿真模型可以分為宏觀模型和微觀模型。

宏觀模型將人群看做一個整體或者部分整體，常見的宏觀模型包括流體模型和網絡模型^[4]。由于流體的某些特征與人群運動相似，有學者采用流體動力學理論模擬人群流通^[5]，即通過密度、流量及速度關系估算人群流通時間。Gwynne等人^[6]通過定義轉換點（transitions）將流體力學模型運用于復雜建筑的求解過程，并廣泛應用于疏散時間的工程計算。網絡模型則是通過節點和邊表示建筑結構間拓撲關系的網絡，進而在網絡的基礎上通過經驗公式等方法計算運動時間^[7]。宏觀模型能夠以足夠小的成本消耗反映大規模人群的整體流動，具有運行效率高的特點。微觀模型則是從個體層面上考慮運動過程中的相互影響，可以分為連續模型和離散模型。其中以社會力模型^[8]為主體的連續模型包括磁力模型^[9]、離心力模型^[10]、CityFlow模型^[11]等諸多模型，其核心思想是用受力驅動的粒子表示人群中個體的運動。離散模型的研究則以元胞自動機^[12]為主，以及由元胞自動機衍生的格子氣模型^[13]、場域模型^[14]等，其核心思想是將空間和時間離散化，利用更新規則模擬運動過程。微觀模型將人群整體流動細化到個體在受到內外部多種因素影響下的個體活動，進一步推知群體運動，具有高精度的特點^[15]。

宏觀和微觀模型雖然各有優勢，但缺點同樣明顯。宏觀模型難以體現個體差異（如個體速度、體積、年齡、性別等）、突發狀況（如瓶頸處阻塞、個體跌倒等）和建筑細節差異對疏散過程的影響，而微觀模型計算量大，建模以及模型調整的過程較為復雜，難以應用在實時性要求較高的場合。為在考慮個體運動特征的同時提升運算效率，本文在網絡最短路算法的基礎上構建平移矩陣，通過宏觀與微觀相結合的方式實現對建筑內人員單向流通的快速模擬。然后，通過開展觀測實驗模型參數，并與Pathfinder軟件的模擬結果驗證模型的可行性。該方法將決策層（路徑規劃行為）與運動層緊密結合，有效降低建模和參數設置難度，極大提升了計算效率，為人群流通提供一種具有高精度和高計算效率的新研究方法。

1 建筑物簡介及模型抽象

1.1 建筑物情況簡介

本文以上海理工大學某教學樓為例介紹本模型的構建及仿真過程。該教學樓共有五層，如圖1所示。考慮到該教學樓第五層教室稀少基本不排課，本文僅對該建筑的1～4層進行建模分析。該建筑物呈“n”字型分布（圖2），每層房間分布相同且層左右兩側基本對稱，樓層間以樓梯相連，樓梯口及出口位于建筑物中部和樓主體的兩側，共三個出口（樓梯口），同層樓梯出口與教室門間以樓道連接。教學樓每層有教室20間，可容納數千人同時上課。

1.2 網絡模型構建

在以Dijkstra算法為代表的最短路理論中，以節點、邊和邊的長度構建賦權網絡G（V，E，L）。其中，V表示節點的集合，E表示邊的集合，L表示邊長度的集合。本文利用Dijkstra最短路算法計算網絡中給定源點vs∈V到終點vt∈V的最短路徑。根據算法需 要，對教學樓進行二維抽象建立無向網絡圖，如圖3所示。

該網絡模型中的節點分為三類，分別如圖中的綠色、藍色和紅色圓圈所示（見電子版）。其中：藍色圓圈表示教室出口的節點vsi，也稱為發點；黑色圓圈表示建筑結構交匯處的節點vci，也稱為中間節點；紅色圓圈表示出口的節點vti，也稱為收點。根據上述定義，綠色圓圈和藍色圓圈之間的邊esici表示教室內部至教室門的路徑；藍色圓圈之間的邊表示建筑結構交匯處之間的真實路徑，如ec1c2表示兩個門之間的走廊，ec101c104表示第三層和第四層之間的樓梯；藍色圓圈和紅色圓圈之間的邊表示樓梯口和室外的走廊或大廳。這里的出口節點可以理解為戶外區域，將建筑物的所有出口用一個虛擬出口節點vt1表示。該網絡模型的主要功能是求解教室門與建筑出口間的最短路徑，因此教室內部至門口的邊esici不應參與最短路徑的求解，故令其長度lc1c2取非常小的正數，如0.01 m。

除此之外的所有邊均與建筑結構一一對應，其中：水平方向的弧表示走廊，其權值為走廊的實際長度；垂直方向的弧表示樓梯，其權值為實際樓梯的長度（即在樓梯斜面上的投影長度和連接平臺長度之和）。值得注意的是，有的教室有前后兩個門，在本文模型中是由兩個節點分別表示的。若采單個節點，在計算最短路時，不是最短路的門會被舍棄，即意味著不會有人通行，這與現實不符。在最短路的基礎上，本文提出了平移矩陣算法求解人員流通時間，在計算的過程中需要教室人數、路徑寬度、路徑上的平均速度等參數。因此，需要增加另外三組邊的權值和一組邊的屬性，形成擴展網絡：G（V，E，L，W，N，S，P），其中：W表示邊的寬度，與建筑結構的實際寬度一致；N表示邊上的人數，在初始時只有教室內部至門口的邊上可出現非零值，表示教室內的人數；S表示邊上的平均流動速度，由下一章節中的觀測實驗獲取；P表示邊的屬性，分為起始邊（pi=0，即與教室節點相連的邊）、中間邊（pi=1，即不與教室節點和出口節點相連的邊）和終結邊（pi=2，即與出口節點相連的邊）。

1.3 觀測實驗與參數取值

為獲取人群流速，本文采取多次實地觀測法獲取門、走廊和樓梯處的平均速度，觀測視頻截圖如圖4所示。選取觀測點時有以下兩點注意：a）選擇視野良好處，無障礙阻擋，以便在學生大量流通時可以通過觀測統計流量數據；b）選擇上下課期間，學生流通量足夠大使得通道達到最大利用率狀態。對觀測數據進行分析計算得到通道各處人群平均流通速度如表1所示。

由表1可知，在人員密度較大時，人員在走廊上的速度遠大于在樓梯上的速度。值得注意的是上述結果是在人群密度較大時測得的，因此在模擬時適用于人數較多的情況。根據表中數據可以獲得完整的擴展網絡參數。在實際存儲該網絡時，以邊為索引依據，其他參數與邊一一對應，最終形成的擴展網絡數據結構如表2所示。

2 最短路和平移矩陣算法

2.1 網絡最短路徑求解

本文將以Dijkstra最短路算法為基礎計算本建筑物無向網絡圖的最短路。關于經典Dijkstra最短路算法本文不再贅述，詳見文獻[16]?；跀U展網絡G（V，E，L，W，N，S，P），首先利用G′（V，E，L）和最短路徑算法，求解每個門至出口節點vt1的最短路徑集合Rmin：

其中：R^*s1={vsi，…，vci，…，vt1}是用節點表示的最短路徑，如果存在從一個節點出發的多條最短路徑，則只保留其中一條。經過Dijkstra最短路算法求出的最短路徑為每個教室的門到出口的最短路徑且存在重復邊，不利于后續的平移矩陣計算。對于Rmin，可以通過重復路徑合并形成整個建筑的最短通路R^*min，具體做法如下：

a）將R^*si中所有的節點按照前后順序生成對應的有向弧集：

b）將所有有向弧集合合并，形成一個包括所有弧的集合：

c）將Ar^*min中所有重復弧刪除，即重復有向弧只保留一個，形成該網絡G′的最短通路Ar^*min（G′）。

經過上述步驟得到的Ar^*min（G′）描述了每個門至出口的唯一最短通路，且路徑上的弧在集合中只出現一次。對上述結論的證明如下：

a）弧的唯一性。由于對重復的弧進行了刪除操作，所以Ar^*min（G′）中的弧是唯一的。

b）通路的存在性。由于只是對重復弧進行刪除，并未減少弧的種類，所以Ar^*si中的弧都能在Ar^*min（G′）中找到，保證了通路的存在性。

c）路徑的唯一性。對任意R^*si={vsi，…，vcj，…，vt1}上的任意節點vcj，該節點之后的路徑{vcj，…，vt1}必是從該點出發至出口vt1的最短路徑R^*′cj。這可以用反證法證明：假設從vcj出發的最短路徑是R^*′cj且與R^*cj不同，則用R^*′cj替代R^*cj中從vcj開始的后半部分得到R^*′cj且有r^*′cjlt;r^*cj（r表示R的路長），這與R^*si是最短路長相矛盾。進一步地，對與vcj相連的門，從該門出發的最短路徑必然與R^*si 公用R^*cj部分，因此對任意一條最短路徑，匯入該路徑的其他路徑均與該路徑“合流”，最終形成類似于河流的支流和干流的網絡。

因此，可以從任意教室出發沿最短通路中的有向弧運動至出口，且該路徑為最短路徑。接下來，本文將在最短通路的基礎上通過平移矩陣算法求解運動時間。

2.2 基于平移矩陣的運動時間求解

基于網絡最短路算法只能求得互不交叉的最短路徑，并不能直接計算出運動時間?，F有模型中常使用連續模型（包括社會力模型、優化速度模型等）或離散模型（如元胞自動機模型、格子氣模型等）求解運動時間。然而上述方法存在三個方面的問題：

a）需要建筑物的完整結構，建模過程繁瑣。

b）模型規則復雜，運算時間長。

c）調整人員分布和建筑結構困難，難以應用于疏散路徑的實時優化。

考慮到教學樓通常較為規整，結構簡單，本文提出一種矩陣平移算法求解人員流通時間。該算法可以看做是網絡模型與元胞自動機的結合，利用網絡模型表征建筑結構路徑間的拓撲關系，然后用二維矩陣描述人員在路徑上的流動。與現有模型相比，該模型具有人員分布配置靈活、建筑物構建簡便、運算效率較高等特點。接下來將從更新規則和更新次序兩個方面介紹平移矩陣模型。

2.2.1 平移矩陣的更新規則

如圖5所示本文用一個二維矩陣Ai：Wi×Li表示最短通路上任一弧ei上的人員分布情況，矩陣的列數Wi=wiri，行數Li=liri，其中：wi為邊對應建筑結構的寬度;li為邊對應建筑結構的長度;ri為人員半徑;[]為向下取整操作。每個元素為0時表示此處無人，為1時表示此處有人。

更新時以節點為核心，更新與該節點相連的流入弧和流出弧。根據1.2節中的定義，節點共分為三類，分別是發點、中間節點和收點。其中發點只有流出弧沒有流入弧，每個流出弧由全是1的二維矩陣組成，表示教室內初始狀態的人數。通過調整矩陣的長度L控制總人數：

其中：ni為擬從該門出發的總人數。由于與發點相連的弧一定與中間節點相連，所以僅需對其初始化，更新由中間節點完成。

中間節點與一個或多個流入弧及流出弧相連，更新時主要考察流出弧矩陣的第一行與流入弧的最后一行。對于圖6（a）中的中間節點v₃，其流入弧矩陣（A₁₂，A₂₃）和流出弧矩陣（A₃₄）的更新過程如圖6（b）所示：首先提取所有流入弧的最后一行并進行組合，形成一維數組R，并統計R中1的個數，記為N（R）；其次，提取所有流出弧的第一行并進行組合，形成一維數組C并統計C中1的個數，記為N（C）。當N（R）≥N（C），說明當前時刻在節點v₃處，流出人員數大于或等于流入位置數，更新策略是從R中隨機挑選N（C）個1流入C，R中被選中的1置0，C中的0全部置1。流動完成后將R分離成與A₁₂：W₁₂×L₁₂和A₂₃：W₂₃×L₂₃列數相同的兩個數組R₁：W₁₂×1和R₂：W₂₃×1，然后分別將R₁和R₂重新放回A₁₂和A₂₃，并將流入弧中1置0的列全部下移一行（第一行補0），流動后的結果如圖6（c）所示。當N（R）lt;N（C）時，說明當前時刻在節點3處，流入人員數小于流入位置數，更新策略是將R中的1全部置0，然后在C中隨機挑選N（R）個0置1。流動完成后將所有流入弧向下平移1行（流入弧首行補0），C分離并放回流出弧。

收點與一個或多個流入弧相連，無流出弧。由于收點相當于建筑物的出口，與之相連的是外界空間，所以可構造一個有無限容量的虛擬流出弧與收點相連。此時N（C）=∞，按照中間節點N（R）lt;N（C）的情況更新即可。

2.2.2 平移矩陣的更新時序

在人員實際流通過程中，總是離出口近的人員向出口運動，空出空間后離出口遠的人員逐漸補上。也就是說，運動是從離出口近的人員向離出口遠的人員逐步傳導的。因此，在平移矩陣模型中更新是從收點開始，沿著最短路徑將節點劃分成不同的更新層次，同一層次的同時更新，不同層次的依次更新。以圖7中的最短路網絡為例，其更新次序如表3所示。

考慮到人員在教室、走廊和樓梯上的運行速度并不一致，本文通過引入動態更新時機機制實現對運動速度的控制。在該機制下，為每一個弧矩陣賦予一個更新閾值A.H，其值為

其中：r為人員半徑，即矩陣中每個格點表示的實際空間尺寸;A.S該弧上人員的平均移動速度。因此A.H是在平均速度下，人員走完一個格點所需的時間。另為每個弧分配一個時間參數A.T，在每個更新周期Δt結束時，A.T累加一次：

A.T=A.T+Δt

當節點vi的任一流出弧矩陣A.T≥A.H時，該節點vi按照2.2.1節中所述規則更新。應當注意的是，此時參與更新的流出弧是所有滿足A.T≥A.H的弧，A.Tlt;A.H的弧在更新時忽略?；谏鲜龈聲r序，可以實現在設定速度下的弧矩陣平移。

3 結果與討論

通過最短路計算確定的相關參數，代入平移矩陣進行流通時間求解。為驗證模型的準確性，本文設計了四組實驗，通過對比平移矩陣算法和Pathfinder的結果驗證模型是否準確。本文為教學樓設計了四種不同的排課形式形成不同的人群分布結構：

場景a 教學樓四層的每個教室排課，人數全滿，約為3 500人；

場景b 教學樓四層的每個教室排課，人數為場景a中的3/4，約為2 700人；

場景c 教學樓四層的每個教室排課，人數為場景a中的1/2，約為1 800人；

場景d 教學樓四層的每個教室排課，人數為場景a中的1/4，約900人。

Pathfinder是一套由美國的Thunderhead Engineering公司研發的直觀、易用的新型的智能人員緊急疏散逃生評估系統。其采用的Agent-base模型人員智能化程度高，個體能反饋環境刺激，規避障礙物，人群個體行為與現實情況較為相符，建模如圖8所示。

平移矩陣的參數包括兩個部分，分別是網絡參數和屬性參數。其中：網絡參數是按照1.2節中方法生成的建筑物無向圖的鄰接矩陣表示；屬性參數是如表2所示的邊的長度、寬度、人數、運動速度和屬性，以及人員半徑ri=0.5 m。分別用Pathfinder和平移矩陣算法計算教學樓人群疏散過程，疏散總時間和運算過程耗時如表4所示。

由表4可以看出，在四種場景中平移矩陣的計算結果都比Pathfinder的計算結果短50 s左右，偏小且相對固定的偏差出現的可能原因包括：

a）平移矩陣模型沒有考慮人群速度隨人流密度的變化。

b）平移矩陣法沒有考慮人在轉彎處匯流時人群流通速度的衰減。

c）平移矩陣法沒有考慮瓶頸處人員運動的沖突。

原因a）可以從疏散模擬過程的圖示看出，如圖9所示四種場景中兩種模型剩余人數隨時間的變化曲線存在交叉點，且在交叉點上方Pathfinder曲線的斜率大，而交叉點下方平移矩陣算法的斜率大。即初始階段走廊和樓梯上密度較低時平移矩陣算法的人群平均速度偏小，而密度大時平移矩陣算法的密度偏大。這種偏差主要是采用了固定的運動速率導致，在未來的改進中將考慮利用基本圖將運動速度設為密度的函數;原因b）的校準則需要開展實驗進行細致分析;而原因c）則是由于平移矩陣算法的簡化導致，只能通過補償的形式予以校準。受篇幅所限，上述校準工作在本文中不作討論。

雖然存在上述偏差，但從定性的角度上看，平移矩陣算法可以體現不同場景疏散時間的優劣，且運算速率比Pathfinder軟件快10～110倍。此外，在網絡模型上很容易對建筑的結構、不同節點的配流比例、不同教室的人數進行調整。綜合以上優點，該算法為人群疏散的快速模擬提供可行方法，為疏散策略的實時優化提供了可能性。

4 結束語

本文不同于以往學者們立足宏觀、微觀建立的模型的研究方法，提出一種人群疏散平移矩陣算法。該算法將宏觀層面的路徑選擇行為與微觀層面的個體運動行為以網絡為紐帶緊密結合，通過對0-1矩陣的更新模擬人群沿建筑通道，即網絡的邊流通、匯集的過程。由于該算法的最小更新元素是表示一條邊的0-1矩陣，所以可以在考慮個體運動的同時大大加快運算速率。與Pathfinder的對比結果顯示，該算法的總疏散時間在不同密度下均偏快50 s左右。但考慮到該算法具有在定性上的準確性，且運算速率高、調整場景便利，使其有潛力成為疏散策略的實時優化工具。然而，該算法當前并未考慮速度隨密度的變化、匯流處速度的衰減、瓶頸處可能出現的沖突等因素。因此在未來的工作中，一方面會通過實驗與仿真對該算法在定量層面的可靠性進行進一步校準，另一方面會基于該算法發展復雜建筑內疏散的實時優化策略。

參考文獻：

[1]馬劍，王翔，肖修昆.基于有限理性路徑決策的人員疏散雙層模型[J].系統工程理論與實踐，2020，40（10）：2698-2706.（Ma Jian， Wang Xiang， Xiao Xiukun. Bi-level evacuation modeling considering boundedly rational route choice behavior[J].Systems Engineering-Theory amp; Practice，2020，40（10）：2698-2706.）

[2]Lam W H， Cheung C-Y. Pedestrian speed/flow relationships for walking facilities in Hong Kong[J].Journal of transportation engineering，2000，126（4）：343-349.

[3]Zhang Jun， Klingsch W， Schadschneider A， et al. Ordering in bidirectional pedestrian flows and its influence on the fundamental diagram[EB/OL].（2012-01-20）.http：//doi.org/10.1088/1742-5468/2012/00/p00000.

[4]呂偉，穆治國，劉丹.大型購物中心人員疏散引導模擬優化研究[J].中國安全生產科學技術，2019，15（5）：136-141.（Lyu Wei， Mu Zhiguo， Liu Dan. Study on optimal simulation of pedestrian evac-uation guidance in large shopping mall[J].Journal of Safety Science and Technology，2019，15（5）：136-141.）

[5]姜雨青.面向室內空間人群疏散宏觀網絡模型的場景建模方法研究[D].南京：南京師范大學，2016.（Jiang Yuqing. Research on the modeling of macro network model for indoor crowd evacuation scene[D].Nanjing：Nanjing Normal University，2016.）

[6]Gwynne S M， Rosenbaum E R. Employing the hydraulic model in assessing emergency movement[M]//SFPE Handbook of Fire Protection Engineering.New York：Springer，2016：2115-2151.

[7]Chalmet L G， Francis R L， Saunders P B. Network models for buil-ding evacuation[J].Management Science，1982，28（1）：86-105.

[8]Cornes F， Frank G， Dorso C. Microscopic dynamics of the evacuation phenomena in the context of the Social Force Model[J].Physica A：Statistical Mechanics and its Applications，2021，568：125744.

[9]Khamis N， Selamat H， Yusof R， et al. Magnetic force model approach with path finding feature for an Improved crowd movement simu-lation[C]//Proc of Asian Simulation Conference.Berlin：Springer，2017：157-168.

[10]彭威.基于社會力的橢圓行人動力學模型[D].南京：南京大學，2016.（Peng Wei. Elliptical pedestrian model based on social force[D].Nanjing：Nanjing University，2016.）

[11]Wang Weili， Lo S， Liu S， et al. On the use of a pedestrian simulation model with natural behavior representation in metro stations[J].Procedia Computer Science，2015，52：137-144.

[12]江雨燕，劉軍.基于元胞自動機的普通超市火災疏散模型的構建[J].計算機應用研究，2019，36（11）：3330-3333.（Jiang Yuyan， Liu Jun. Construction of fire evacuation model for ordinary supermarket based on cellular automata[J].Application Research of Computers，2019，36（11）：3330-3333.）

[13]Marconi S， Chopard B. A multiparticle lattice gas automata model for a crowd[C]//Proc of International Conference on Cellular Automata.Berlin：Springer，2002：231-238.

[14]Yanagisawa D， Nishinari K. Mean-field theory for pedestrian outflow through an exit[J].Physical review E，2007，76（6）：061117.

[15]鄭美容.人群疏散行為建模與仿真研究[J].洛陽師范學院學報，2015，34（11）：19-23.（Zheng Meirong. Modeling and simulation of evacuation behaviour of crowd[J].Journal of Luoyang Normal University，2015，34（11）：19-23.）

[16]王志和，凌云.Dijkstra最短路徑算法的優化及其實現[J].微計算機信息，2007（33）：275-277.（Wang Zhihe， Ling Yun. The optimization and implementation of the shortest path Dijkstra algorithm[J].Microcomputer Information，2007（33）：275-277.）