基于元胞自動機和圖論的博物館緊急疏散路線規劃

王潔瓊

（山西農業大學軟件學院 山西省晉中市 030801）

發生緊急情況時，為使在最短的時間內疏散最多的游客，需要以最合理的方式安排人員疏散。近年來，在行人流的仿真研究中，元胞自動機仿真技術已廣泛應用于交叉路口的行人流，在行人流和疏散行人流的仿真研究中，其應用已較為成熟，岳昊等[1]基于元胞自動機仿真研究了行人疏散流中疏散人數、安全出口等因素對疏散時間的影響，元胞自動機模擬或定義系統中簡單個體的微觀行為特征，并在個體之間相互作用的條件下，實現系統整體宏觀行為特征的模擬和研究。本文采用局部模擬的方法，估算出在疏散不同游客量時，不同通道類型（例如寬過道，窄過道和樓梯）所花費的時間，并且估計出場地內游客的整體疏散時間。

根據模擬的游客疏散結果生成緊急疏散計劃。以游客的疏散時間分布和博物館的疏散通道，展館布局等數據為依據，建立圖模型，估算每條路徑的成本，以此規劃游客的疏散路線。計算表明，明智地安排游客選擇不同的路徑比告訴他們每個人的最短路徑更為重要，科學合理的規劃逃生疏散路線為應對突發事件提供了必要的保障。

1 基于元胞自動機仿真模擬游客疏散情況

1.1 研究思路

為了獲得最大的疏散人數，需要估計出每個疏散通道的疏散能力，并根據疏散能力的不同對游客進行疏散。本節首先使用元胞自動機模擬展廳中一定數量不同年齡比例的游客的疏散情況，獲取相關數據。由于不同疏散通道的參數不同，因此修改元胞自動機模擬的疏散通道的參數，能夠得到各種疏散通道的疏散情況的參數。根據元胞自動機多次模擬獲得的數據對游客進行有效疏散。

1.2 研究方法

在X×Y 的二維離散網格系統中建立游客疏散的仿真模型。將移動區域劃分為N 個相等的離散元胞空間。障礙物占據系統邊界的元胞以形成房間的墻壁，而在墻上留下元胞空間作為房間的安全出口。在該系統中，每個空間位置只能容納一位游客。游客疏散的模擬過程也被離散為多個相等時間步長。在一個時間步長中，游客只能移動一個或多個元胞，在本節仿真過程中，將殘疾人，孕婦和老年游客的疏散速度定為1 格/秒，女性/中年游客的疏散速度定為2 格/秒，成人游客的疏散速度定為3 格/秒。游客不能穿過墻壁，只能從房間出口離開系統，仿真模型如圖1所示。

模型在每個時間步長上的演化，游客可以等待或向八個方向移動如圖2。當選擇下一個移動位置時，游客將對可選位置做出預期得分（如公式1），選擇最大預期得分的位置作為目標位置。

預期得分描述了下一個可選位置與游客目標位置的接近程度。通過游客間的排斥力和該位置對游客逃生的吸引力這兩個參數相加得出。

圖1：游客疏散仿真模型圖

圖2：8 個可移動的方向

游客疏散的目的地是安全出口。在游客疏散過程中，盡可能多的選擇出口附近的位置作為其下一個時間步長的目標位置。對于展廳內的游客，距離安全出口越近的位置對其吸引力就越大。在計算預期得分時，首先要計算游客當前位置與安全出口之間的歐氏距離（如公式2）。當游客在一個有多個安全出口的展廳內疏散時，將距離安全出口的最近的距離值作為當前位置與安全出口之間的最短距離。

由此得出結論，時間成本與人數成線性增長如圖3所示。

2 基于圖論安排緊急疏散計劃

2.1 研究思路

基于圖論建立盧浮宮的圖模型。具體是將房間設置為節點，將通道設置為圖中的邊，并將各個通道的最大疏散人口設置為該邊的屬性。然后，根據概率論估算每個房間的初始游客數。再將緊急疏散問題轉化為控制房間人數的線性規劃問題，解決該問題以獲得最佳的緊急疏散計劃。

2.2 研究方法

本節將盧浮宮的引導圖轉換成圖模型。將每個房間都設置為該圖中的一個節點，當有如圖4所示的連接房間時，本節會將它們視為同一節點。

根據通過元胞自動機建立的模型估算出不同過道或樓梯的時間成本。具體來說，需要分別多次模擬寬過道，窄過道和樓梯的時間成本，再取其平均值。將這些平均值用于計算每個過道和樓梯的最大容量，最大容量則是該圖模型上邊的屬性。

建立該圖的鄰接矩陣如表1所示。

在緊急情況下幾乎不可能要求每個人都認真耐心地聽從撤離安排，為了疏散全部人口，直接告訴游客走哪條路是更加高效的，這意味著控制離開和進入房間的人數更為重要。

具體來說，假設該圖中有N 個節點，并且用x_i^t 表示在時間t 時第i 個房間的人數，并估計x_i^0 的初始值。游客可以通過連接房間的任何通道離開或進入該房間。因此，如果用Δx_ij^t 表示由于游客在第i 個房間和第j 個房間相連的通道中移動而引起的人數差異，則：

上式表示從第i 個房間離開到第j 個房間的人數等于從第j 個房間離開到第i 個房間的人數。對于當前時刻，該房間中的總人數由以下公式確定：

同時，為了疏散所有人，還需要計算在時刻t 分布在所有房間中的所有人的總和，即

為避免發生只疏散了靠近出口節點人員的情況，不能直接將上述計算出的總數最小化，而是為了鼓勵遠處展廳中的人移動到最終的出口節點，反復最小化以下總和來控制房間人口數量，以此達到疏散游客的目的，規劃出博物館游客的緊急疏散路線。

步驟2：查找除存儲在出口節點列表外的其余節點，并將它們存儲在另一個列表Nk中。

步驟3：對于出口節點列表中的所有節點，找到直接連接的節點并將其存儲在出口節點列表中。

步驟4：返回步驟1，在步驟3 中生成出口節點列表，直到出口節點列表包括所有節點時停止遞歸。

3 結束語

本文采用元胞自動機模型對游客疏散進行大規模仿真，估算出各個通道時間成本。又通過圖論建立游客疏散的圖模型，最后通過目標函數優化為游客提供緊急疏散規劃。此疏散路線規劃模型可推廣到其他大型人流密集場所，只需要根據該場所的具體信息，改變節點，邊及其權值等具體數據，重新模擬運算，便可得到最佳的緊急疏散路線規劃方案。

表1：此圖的鄰接矩陣的一部分

圖3：時間成本與人數的關系

圖4：盧浮宮局部導覽圖及對應圖模型