多出口疏散路線規劃算法的應用與改進

黎欣鑫

（華南師范大學計算機學院，廣州510631）

0 引言

隨著社會經濟的發展，大型的購物商場、博物館和展覽館逐漸增多。但這類建筑的復雜建筑結構給緊急情況下的人員疏散帶來了極大的挑戰。因此，涌現了許多研究嘗試利用理論模型來進行模擬，按照一定的算法來給出高效的疏散方案。

有許多經典的算法能夠對疏散情況進行建模及仿真模擬。蟻群算法能夠模擬實際疏散過程中人員之間的相互影響，因此被很多研究采用來進行疏散路徑設計[1-2]。類似地，元胞自動機模型能夠對個體或群體進行仿真模擬，被應用于室內疏散的模擬[3-4]。然而，這類模型往往針對獨立的個體進行模擬，計劃疏散路線，但在實際應用中缺乏可行性。因為在實際場景中，待疏散人員往往對于具體的建筑結構并不熟悉，需要應急人員的引導。應急人員只能針對某一個區域內的人群做出引導，而不能夠給每一個人都給出具體的疏散路線。

同時還有社會力模型[5]和動態網絡流模型[6]等，也能夠對人群疏散進行仿真模擬并規劃疏散路線。

為了解決現有模擬方法復雜、不便于動態修改適應實際情況，以及難以實際實踐等問題，本文基于多出口疏散算法（MEEA）[7]，提出了更有實際應用潛力的多出口單路線疏散規劃方法（SR-MEEA）。為了更好地模擬具體的建筑結構，從而在算法中考慮到其對人員疏散的影響，SR-MEEA 綜合具體建筑結構的各項數據，建立描述建筑結構的圖模型。如前所述，給每個區域內的人員分配一條具體的疏散路徑是更加可行的方案，因此SR-MEEA 對于從同一區域到達同一出口的不同路徑進行分裂，使得每一區域與每一個出口之間最多有一條單一的路線。最終，通過基礎的MEEA 算法，為每個區域分配一個出口，即確定了唯一的一條疏散路線。

1 建立模型

1.1 任務描述

按照建筑共有e 個應急出口，每一層建筑平面圖將劃分為j 個區域，假設區域j 內需要疏散的人數為pj。算法目標是最小化將建筑內所有的人疏散所用的總時間。

假設每一個出口的疏散時間為ti（即所有被分配到經由這個出口疏散的人員疏散完畢所用的時間），總的疏散時間是ti中的最大值：

1.2 模型定義

邊和結點：圖模型由一組結點及連接結點的無向邊構成。結點分為源結點、出口結點和中間結點；

源結點：源結點用來表示建筑中需要疏散的人員數量和位置，通常為只有一個出口的房間，或者依附在中間結點上來表示該中間結點的人數。源結點的屬性有初始人數（IC）和反應時間（RT）；

出口結點：出口結點代表建筑物的逃生出口，即疏散人群要前往的目標結點。出口結點的屬性為動態容量（DC）；

中間結點：中間結點表示一個具體的區域，例如建筑中的房間、走廊和樓梯等。中間結點由其直接連接的源結點來表示處于這一區域內的人數。中間結點的屬性為容量（V）；

邊：兩個結點直接的邊指明這兩個結點所代表的區域之間是連通的。邊的屬性包含移動時間（TT）和寬度（W）。但是大部分時候，中間結點和源結點之間的邊的屬性都為0，意味著源結點只是用來記錄中間結點表示區域的人數；

初始人數（IC）：代表疏散開始時，處于這一區域內需要疏散的人數；

反應時間（RT）：結點的反應時間代表疏散開始后，該區域內人員真正開始執行疏散計劃所需要的反應時間，因此可以根據實際情況對算法進行調整；

動態容量（DC）：動態容量代表一個人穿過該出口所需的時間；

移動時間（TT）：從一個中間結點到達相鄰的中間結點的平均時間。

1.3 建立模型

首先，為了給建筑中每個區域分配一條疏散路線，以便于應急人員進行指揮，我們按照建筑物的平面圖將建筑物劃分為多個不同的區域。簡單來說，就是將建筑物中較為獨立的區域分離開，作為圖模型中的一個結點。

具體而言，對于圖1 這樣的建筑結構，我們構建出圖2 的圖模型。

圖1 建筑平面圖

圖2 圖模型

由于要給每個結點分配單一的一條路徑，而像結點14 到達出口2 有兩條不同的路徑，即：14-12-11-9-7-6 和14-18-16-11-9-7-6。對于這樣的結點，我們對這兩條路徑進行拆分。

圖3 拆分后的圖模型

拆分結果如圖3。具體地，當一個結點到達出口結點存在k 條不同路徑時，對于這些路徑中重復的部分，按照重復的次數進行平均拆分。例如，在14-12-11-9-7-6 和14-18-16-11-9-7-6 中重復的路徑為11-9-7-6，則將這部分拆分為兩條不同的路徑，并且各自的屬性為原來結點的二分之一。

1.4 算法描述

由文獻[7]提出的多出口疏散算法（MEEA）給每一個結點分配一個對應的出口結點，使整體的疏散時間最短。與其他方法[8-9]不同的是，MEEA 更加高效，能夠根據實際情況實時計算出疏散方案。

每一個出口的疏散時間ti取決于最后一個經過該出口撤離的人員的撤離時間。同時，對于到達出口的人員，我們假設先到達的先通過出口出去，而后到達的需要等前面的先出去才能通過出口。

算法給每個中間結點和源結點都分配一個出口結點。對于分配到同一個出口結點的源結點集合x，按照其離該出口結點的距離進行排序，其中最后一個結點nj的疏散時間為fj。因此，對應的出口結點的疏散時間f(x)如公式（2）所示：

設結點ni的IC 和TT 分別為ai和bi，出口結點的DC 為d，每一點的疏散時間fi由公式（3）計算：

1.5 算法偽代碼

符號定義

表1

算法MEEA

2 討論

本文提出的對復雜建筑結構轉換為圖模型的方法使MEEA 能夠運用到更加復雜的場景中。MEEA 可以進行實時計算的特點，使得其根據緊急情況下的具體建筑結構做出疏散安排。具體而言，當某條路徑遭到破壞時，只需要在其對應的圖模型中刪除對應的邊，而不需要對模型其他部分和算法做出修改。這不同于以往的模擬算法。以往的算法一般都是按照一個固定的結構進行建模，從而給出疏散方案的規劃。但這樣在實際應用中往往會遇到意外情況，不能夠很好地組織疏散。

MEEA 算法為每個結點分配一個出口結點。也就是說，建筑中的每個區域得到的疏散方案僅為該區域應該前往的疏散出口。為了得出唯一確定的疏散路徑，在應用于復雜建筑中時，本文在應用算法前先對有交叉的路徑進行了拆分。然而，對路徑進行拆分的方法會大大增加模型的復雜度。因此，在將來的工作中，還需要進一步改進這一方法。

同時，目前的算法未充分地考慮到可能由于人群擁擠出現的瓶頸問題。本文描述了對具體建筑結構進行建模時考慮到的相關屬性，進而更加真實地對實際情況進行模擬。在此基礎上，將來可以進一步添加結點屬性，并在算法中考慮相關因素的影響，來量化分析可能的瓶頸問題。

3 結語

本文基于MEEA 多出口疏散算法提出了多出口單路線疏散規劃方法。該方法有更大的應用潛力，能夠對復雜建筑物中每個區域給出具體的疏散路線規劃，并實時根據現場情況進行調整，從而使總的疏散時間最短。本文給出了具體的例子來說明該方法的應用，即根據建筑結構建立模型、對圖模型進行調整，并給出了具體算法。此外，還對該方法的優點和不足之處做出討論，并對將來的工作做出展望。