基于圖論的盧浮宮博物館人員疏散模型的構(gòu)建與分析

陳銘錕

摘要：近年來，大型博物館緊急事故頻發(fā)，如何以一種合理、快速的疏散計劃來應(yīng)對顯得極為重要。因此，本文以盧浮宮博物館為模型，根據(jù)其各通道路線的信息，以及人在逃離時的平均安全速度，基于圖論構(gòu)建了最短路徑網(wǎng)絡(luò)流模型。做出適當(dāng)假設(shè)，根據(jù)Ford-Fulkerson算法以及最大流最小割定理，求解出逃離盧浮宮的最大人流量和具體最佳逃生路線，并建立最大流量網(wǎng)絡(luò)流模型。根據(jù)通道優(yōu)先級評估該模型，并在最后提出了將該模型推廣到其他大型建筑的方法。

關(guān)鍵詞：Ford-Fulkerson算法;最大流最小割定理;最佳逃生路線;最大流網(wǎng)絡(luò)模型

中圖分類號：TP391 文獻標(biāo)識碼：A

文章編號：1009-3044（2020）01-0172-02

1問題提出

以盧浮宮博物館為代表的大型人流密集場所，具有規(guī)模大、訪問量大、建筑結(jié)構(gòu)擁堵等。因此，如何構(gòu)建一種可行的，能應(yīng)對多種情況的具體逃生模型是首要問題。同時，該模型還需要滿足能在最短時間逃生，能提前預(yù)測不同突發(fā)情況并實時調(diào)整逃生路線。

2問題分析

為簡化問題，本文分成以下五個部分來分析：

1）基于建筑圖，做出合理假設(shè)，構(gòu)建最優(yōu)逃生路徑的數(shù)學(xué)模型;

2）計算出全部游客撤離所需的時間;

3）如何選擇能達到最大人流量的逃生路徑;

4）提出如何實施模型以及如何推廣到其他大型的擁擠結(jié)構(gòu)。

3模型建立與求解

3.1最優(yōu)逃生路徑的數(shù)學(xué)模型

本文將盧浮宮的逃生路徑的定義為集合G（M，L），其中N為所有節(jié)點的集合，A為路徑的集合，o為逃生出口節(jié)點，每一條路徑（i，j）∈L消耗的逃生時間為tO，F(xiàn)S（i）為從節(jié)點i出發(fā)的所有路徑的集合，IS（i）為到達節(jié)點i的所有路徑的集合，如果路徑（i，j）∈L，則xij=1，否則xij=0。最優(yōu)逃生路徑的數(shù)學(xué)模型可以表達為：

最優(yōu)逃生路徑的選擇可分為路徑最短尋優(yōu)和時間最短尋優(yōu)，對后者用Ford-Fulkerson算法以及最大流最小割定理求得最佳疏散時間，提出疏散方案，開發(fā)緊急疏散模型。為了得到合理的路網(wǎng)權(quán)值，可通過盧浮宮建筑圖構(gòu)造CAD模型，實地采集道路信息，分析建筑中的人群密度、道路結(jié)構(gòu)分布并記錄每條道路的各種信息。

3.2模型的分析和結(jié)論

將CAD圖轉(zhuǎn)化為最大流網(wǎng)絡(luò)圖，通過相應(yīng)算法可得單位時間人流量，同時將每一段人流量轉(zhuǎn)換成其對應(yīng)的疏散時間。疏散時間最短是衡量應(yīng)急疏散最優(yōu)路徑的指標(biāo)之一，每條路線的權(quán)值即為通過該路線的所需時間tij。當(dāng)疏散人數(shù)較多時，人在集結(jié)點（即網(wǎng)絡(luò)圖中的源點）的等待時間會比較長，因此下面考慮人在源點的等待時間（此處假設(shè)源點為A，匯點為a，b，c）：

3.3 Ford-Fullkers伽算法求解最大流的數(shù)學(xué)模型

主要思想即在流量守恒的約束下尋找增廣鏈，當(dāng)無法獲得增廣鏈時算法終止，其正確性依賴于這個定理：當(dāng)殘存網(wǎng)絡(luò)中不存在一條從s到t的增廣路徑，那么該圖已經(jīng)達到最大流。本文通過Matlab計算每個節(jié)點與盧浮宮疏散的最終出口f即節(jié)點16）得出盧浮宮疏散模型中不至于超過逃跑道路能容納的人流量，即最大流。

3.4結(jié)果

運行程序后，可得對應(yīng)的最大流路徑：

4結(jié)論

本模型充分考慮了人員安全疏散時的突發(fā)情況，并對可能出現(xiàn)的突發(fā)情況對模型提出了方便的優(yōu)化的辦法。當(dāng)緊急通道的優(yōu)先級大于通往公共出口的通道優(yōu)先級時，開啟緊急通道并將緊急通道的疏散路線納入原本的疏散模型中，重新運行算法即可。

此疏散通道的評估體系可以推廣到其他大型場所：只需根據(jù)建筑物具體的信息，通過修改源點、弧和權(quán)值的具體數(shù)量和數(shù)值，以及通道和出口的數(shù)據(jù)，重新運行算法，便可得到最佳的逃亡路線。