疏散規劃的一種優化算法

尹大朏，方裕

（1.清華大學地球系統科學中心，北京 100871；2.北京大學遙感應用研究所，北京 100871）

0 引言

隨著全球氣候變化的加劇，大規模極端自然災害的發生頻率越來越高，地震、火山爆發、泥石流、海嘯、臺風、洪水等突發性自然災害直接危害著居民安全；與此同時，人為造成的災難事故如油氣泄漏、火災、恐怖襲擊等對社會經濟的影響也越來越大。這些災害發生突然，影響范圍極大，需要疏散的群眾眾多，如果缺乏有效的疏散策略和最佳的避險路徑，極有可能在逃逸過程中造成不必要的擁堵，甚至造成二次傷害。為此有必要快速生成疏散規劃（Evacuation Planning），盡快為處于危險地點的人群指派合理的路徑，最大限度地利用路網的容量，同時盡可能減少擁堵，使居民盡早抵達安全地點。

疏散規劃不僅需要為每個待疏散者找到快速抵達安全目的地的路徑，還要保證這些路徑不相互沖突。疏散規劃方案的實質在于處理大量疏散人群和有限路網容量之間的矛盾，而疏散算法的難點在于如何盡快地得到合理的疏散規劃方案。因為疏散算法需要從多個源點、多個時間點出發的路徑組合中尋找最優，而且疏散算法允許逃生者在任意節點停留任意時間，這樣問題尋優搜索的空間極大。

前人的探討集中在疏散規劃問題最優解的算法，其主要思路是將疏散規劃問題轉換為時變路網上的線性規劃或者最小代價流問題求解［1，2］，最好的算法其時間復雜度為O（N6（T＋1）6）［3］。由于最優化解法需要在時間片上對路網進行復制，占用大量內存，導致算法很難擴展到大路網上，近年來許多研究者轉向計算速度較快的次優解的研究。目前已知求解速度最快的次優解算法是由Shekhar研究組提出的啟發式算法CCRP（Capacity Constrained Route Planning），其時間復雜度為O（P（E＋N）logN）［4－6］。然而，文獻［7］使用小型城鎮的路網對CCRP進行測試，發現計算時間超過1天，這顯然無法達到應急指揮的要求。為此本文提出一種新型的啟發式算法CCRP＋＋，進一步加速計算。其主要原理是引入一個雙優先隊列（Double Priority Queue），保存歷史迭代計算的中間結果并啟發當次迭代的搜索，以便刪減CCRP中大量不必要的最短路徑計算，達到大幅加速疏散規劃計算的目的。雖然還有不少文獻［8－20］對相關的問題進行了探討，但至今還沒有適用于大規模路網的高效算法。

1 問題定義與假設

在本文的算法探討中，把問題抽象到一個時變的容量受限圖G（N，E，S，D，P，T）中進行討論。其中，N表示圖節點（Node）的集合，E表示邊（Edge）集合，S表示源點（Source）的集合，D 表示目標點（Destination）集合，P 表示疏散者（evacuees）的集合，T表示疏散過程經歷的時間（Time）。每個源點表示危險地點，里面有數量不等的待疏散者，需要將其疏散到若干安全的目標點。路網由邊及節點構成：邊有通過時間（Travel Time）和邊容限（Edge Capacity）兩個屬性，分別表示通過此邊的時間和同時進入某一個邊的最大人數；節點有節點容限（Node Capacity），表示同時刻不能有更多的人進入該節點。在疏散過程中，會有一定的人流（flow）通過特定的路徑從某源點出發到達目標節點。

如圖1的疏散網絡示例中，3個源節點N1、N2、N8分別有10人、5人、15人，需要將這些人通過如下的網絡盡快疏散到N13和N14。對應的疏散方案之一是表1展示的A－I共9組疏散流。以A組為例，在T0時刻從源點N8出發，經過（N8，N10）邊于T3時刻到達N10，不做停留繼續沿（N10，N13）邊于T4到達安全目標點N13。疏散規劃的目的是對網絡中的路徑進行合理配置（表1），分批次將人流疏導到不同目的地。

圖1 疏散網絡示例Fig.1 Evacuation network example

表1 疏散路徑示例Table 1 Example of evacuation route

問題的定義如下：

給定：擁有如下性質的交通路網G（N，E，S，D，P，T），包含：1）1個源點（Sources）集合S，每個源點上有若干待疏散人；2）1個目標點（Destination）集合D；3）每條邊的長度（Length）是其通過時間（Travel time）；4）邊和節點都有其最大容限（Capacity）。

輸出：1個“疏散流”集合，每個疏散流包括流量大小、通過的路網節點、從每個路網節點開始的出發時間（Depart Time）和抵達時間（Arrival Time）。

約束：主要的約束有：1）路網的容限限制，即同時進入一條邊的人數不能超過路網的最大容限Capacity；2）先入先出準則FIFO，即進入同一條路段的人流，先進入該路段首節點的人抵達該路段末節點的時間必定不慢于后進入的人。

目標：優化的目標主要取決于：最小化總體逃逸時間（Egress Time）和最小化疏散規劃生成所需的計算時間（Computational Time）。

值得注意的是，兩個目標是對問題兩個方面的優化目標。一般而言，無法同時達到最優，即在縮短的計算時間和求得問題的最優解之間存在一個制衡（Tradeoff）。在解決實際問題中，如果求得最優解的運行時間太長，可以選擇計算速度較快的啟發式算法求得問題的次優解（sub－optimal solution）。

2 疏散問題的CCRP算法

CCRP算法的核心思想是將疏散問題從網絡流問題轉換為迭代最短路徑的計算問題。如圖2所示，它添加一個虛擬的超級源點，每次計算當前系統中的一條“最早抵達路徑”，即所有源點的最短路徑的最小者，并將該路徑上相應時刻的邊容限預留給通過的人流。其主要計算思路可以概括為：如果在任一源節點上還有人，那么循環執行如下步驟：1）計算“最早抵達路徑”（Earliest Arrival Path）；2）確定最早抵達路徑上的流量（flow）；3）預約（Reserve）最短路徑上面的邊，轉步驟1繼續。

圖2 CCRP將疏散問題轉化為最短路徑計算Fig.2 Converting the evacuation to shortest path calculation by CCRP

CCRP算法的時間復雜性：算法需要在每次迭代中為每個源節點計算一次最短路徑，然后進行預留；尋找流量flow和reserve分別需要O（E）的時間，主要的時間消耗在最短路徑搜索上。如果加入一個超級節點S0，可以把多源的最短路徑轉換為從S0出發的單源最短路徑，則采用Dijkstra算法計算單源最短路徑的時間復雜性為O（（E＋N）logN）；而在最壞情況下，每次迭代只能疏散一個人。所有源點的疏散者總和為P，因此CCRP算法的時間復雜性為O（P（E＋N）logN）。

其中，第一步使用Dijkstra算法對所有S個源點分別求解其到任意一個目標點的最短路徑，取其中最短的一條作為“最早抵達路徑”；在實現中，還可以加入一個超級源點（Super Source）來降低搜索的復雜性。第二步確定路徑流量，需要比較最早抵達路徑對應的源點中剩余疏散者人數和路徑中各個路段的最小可用容限（Available Capacity），取較小者作為flow值；第三步預約（Reserve）路徑，對找到的“最早抵達路徑”的每個節點和每條路段的“邊／節點可用容限表”的相應時刻減去flow值。

3 新型算法CCRP＋＋

3.1 CCRP算法的缺陷

CCRP算法的一個主要問題是為了獲得當前的“最短的最短路徑”需要在每次迭代中重復對所有源點求解其最短路徑，計算的時間復雜性為O（P（E＋N）logN）。值得注意的是，CCRP采用了圖2所示的一般圖論模型進行分析，然而它忽略了路網的空間鄰近性和迭代計算間的時間相關性。事實上，道路網絡中的節點，無論是源點、目標點還是中間節點，都有其空間位置屬性。CCRP采用適用于一般網的模型研究路網問題，而沒有考慮路網的空間特性和疏散問題的時間特性。

如果對相鄰兩次迭代間源點的擴張過程進行“空間分析”，就可以更加直觀地發現這些沒有結束的“冗余擴張”較多（S－1個），以至于占據了單次迭代中大部分的運算時間（有用的擴張只有一個）；而且這些沒有完成的擴張還會不斷地重復，直到其中的某一個變成有用的擴張為止。在此把這些看似無用的最短路徑計算稱為“冗余重復”擴張。在圖3所示的網絡中有3個源點S1、S2、S3和3個目的節點D1、D2、D3。第一次迭代中，只有S1－D1（源－目標）節點對完成了擴張，第二次迭代中只有S2－D2完成了擴張。兩次相鄰迭代中，S3的擴張是冗余且重復的。

圖3 兩次相鄰迭代 “冗余重復”擴張Fig.3 The redundant expansion in adjacent iterations

倘若能夠消除這些冗余重復擴張，將大大提升算法效率，但是難點在于：雖然在所有的S個源點的最短路徑搜索擴張中，有用的擴張只有一個，可是如果不對所有的源點進行最短路徑計算，則無法知道哪一個是有用的擴張。雖然無法在每次迭代中不經過計算就確定當前迭代的有效擴張源點，但是通過觀察多次迭代的擴張過程，可以獲得一部分各源點距離其較近的目標節點的路徑長度信息，利用這些歷史迭代累計信息有望減少未來迭代中冗余擴張的次數。

3.2 CCRP＋＋ 算法

根據以上觀察和分析，本文給出一種新的啟發式算法CCRP＋＋。算法的核心思想與CCRP略有不同，使用歷史上計算的最短路徑長度啟發搜索當前迭代中有可能是“最短的最短路徑”的源點。為了保存歷史上的最短路徑信息，算法采用一種排序數據結構——優先隊列（Priority Queue），保存每個源節點已經預留的路徑長度，即從該源點到達最近目標點的最早抵達時間Earliest Arrival Time（縮寫為EA）。每次迭代，只需提取優先隊列最頂端的源點并進行最短路徑計算，然后再放回隊列中。

在實現中，首先對所有源點進行最短路徑計算，以＜源點號，路徑長度＞作為優先隊列的＜Key，Value＞。為了保證每個源點在放入優先隊列之前，不會因為其他節點的路徑預訂使得自身的最短路徑失效，算法采用了雙優先隊列（Double Queue）設計，設置PreRQ（Pre－enter Reserved Queue）和 RQ（Reserved Queue）兩個隊列，將尚未進入正式預訂隊列RQ的源點，依照其“可用”路徑的長度置于PreRQ中。每次迭代中，算法同時取出PreRQ和RQ的頂端源點，比較其路徑長度。如果PreRQ頂端源點的路徑長度較小，說明此時其為“最短的最短路徑”，將其路徑“預留”并置入RQ中；若RQ頂端源點的路徑長度較小，則說明其為當前“最短的最短路徑”，對其路徑進行“Update”更新操作，將更新后的路徑重新置入RQ中。這種通過取PreRQ和RQ的頂端元素進行比較的方法，可以迅速找到需要進行單源最短路徑計算的源點，避免了每次迭代進行冗余重復的最短路徑計算，大大提高了運算速度。算法的偽代碼如下：

3.3 算法的復雜性分析

相對于CCRP，CCRP＋＋算法每次迭代只進行一次最短路徑計算，但是多了兩個從PreRQ和RQ取頂端源點和放回的操作，其復雜性分別為O（1）和O（logS），所以CCRP＋＋的復雜性為O（P（E＋N）logNlogS）。由于一般路網為稀疏圖，E是N 的常數，復雜性可以簡化為O（PNlogNlogS）?？紤]到實際路網上從單個源點出發的最短路徑的擴張是圍繞源點的小網絡，CCRP＋＋ 單次迭代的時間遠小于CCRP。假設源點均勻分布在網絡中，每個源點周圍有N／S個節點，則CCRP的復雜性為O（PS（N／S）log（N／S）），即O（PNlog（N／S）），而 CCRP＋＋的復雜性為O（P（N／S）log（N／S）log（S）），即理論上CCRP＋＋是CCRP運算時間的log（S）／S。

4 實驗分析

對算法CCRP＋＋和CCRP使用不同規模的路網數據進行測試。實驗平臺操作系統使用Windows XP 32bit SP3，配置CPU：Intel Core Duo T5500＠1.66GHz，內存1.5GB，編程語言使用C?。實驗采用了3組規模不同的路網數據：第一組是由CCRP項目參與者Dr.Sangho Kim提供的CCRP實驗數據SM，第二、三組數據是USGS發布的兩個城市Oldenburg（OL）和San Joaquin（TG）的路網數據。根據網絡規模，隨機生成了疏散者人數、源點和目標點數。測試數據的屬性如表2。

表2 不同網絡下的測試數據Table 2 Test data in different network

實驗主要檢測兩種算法的效率和隨網絡規模的可擴展性。以整體運算時間和單次迭代運算時間進行測算。在整體運算時間上，CCRP＋＋相對于CCRP分別取得了2、28、100倍的加速（圖4）；對比兩種算法的單次迭代運算時間，CCRP的運算時間隨網絡規模增大、源節點數量的增多而明顯增加，而CCRP＋＋的單次迭代運算時間幾乎沒有增長（圖5）。這是因為無論有多少源點，每次都只進行一個源點的最短路徑計算，少許的增量來自于進出兩個優先隊列PreRQ和RQ的代價，大小為O（logS）（S為源點數量）。實驗表明CCRP＋＋在效率和可擴展性方面都優于CCRP。

5 結語

針對傳統疏散算法CCRP的不足，提出了一種新型的啟發式疏散算法CCRP＋＋，采用雙優先隊列結構，每次只更新一個源點的最短路徑樹，避免了CCRP每次迭代時進行所有源點的最短路徑樹更新，顯著降低了算法的時間復雜度。真實路網的模擬實驗表明，CCRP＋＋ 相比CCRP在算法效率和可擴展性上都有明顯提升，這一改進有助于疏散算法在實際應急指揮系統的應用。

［1］ BAUMANN N，SKUTELLA M.Solving evacuation problems efficiently－earliest arrival flows with multiple sources［A］.47th Annual IEEE Symposium on Foundations of Computer Science［C］.2006.FOCS＇06.399－410.

［2］ HAMACHER H W，TJANDRA S A.Mathematical Modeling of E－vacuation Problems：A State of the Art［R］.Reports of the Fraunhofer Institute for Technological and Industrial Mathe－matics（ITWM Report），2002，24，227－266.

［3］ HPPPE B，TARDOS E.Polynomial time algorithms for some evacuation problems［A］.5th Annual ACM－SIAM Symposium on Discrete Algorithms［C］.Arlington，VA，1994.433－441.

［4］ LU Q，HUANG Y，SHEKHAR S.Evacuation planning：A capacity constrained routing approach［J］.Intelligence and Security Informatics，2003，2665：111－125.

［5］ LU Q，GEORGY B，SHEKHAR S.Capacity constrained routing algorithms for evacuation planning：A summary of results［A］.Proc.of 9th International Symposium on Spatial and Temporal Databases［C］.2005.291－307.

［6］ SANGHO K，GEORGE B，SHEKHAR S.Evacuation route planning：Scalable heuristics［A］.15th ACM International Symposium on Advances in Geographic Information Systems［C］.Seattle，WA，2007.1－8.

［7］ AHUJA R K，MAGNANTI T L，ORLIN J B.Network Flows：Theory，Algorithms，and Applications［M］.Prentice Hall，1993.

［8］ CAI X，KLOKS T，WONG C K.Time－varying shortest path problems with constraints［J］.Networks，1997，29（3）：141－149.

［9］ CHABINI I.Discrete dynamic shortest path problems in transportation applications：Complexity and algorithms with optimal run time［J］.Transportation Research Record，1998，1645（1）：170－175.

［10］ CHALMET L，FRANCIS R，SAUNDERS P.Network models for building evacuation［J］.Fire Technology，1982，18：90－113.

［11］ CHEN Y.Evacuation model and algorithms for emergency management system［A］.International Conference on Transportation Engineering［C］.2007.3171－3177.

［12］ KISKO T，FRANCIS R.Evacnet＋：A computer program to determine optimal building evacuation plans［J］.Fire Safety，1985，9（2）：211－222.

［13］ 尹大朏，方裕.應用于大規模災害發生時進行人員疏散的快速疏散方法［P］.專利授權號ZL 2010 1 0279504.3.

［14］ 方裕，周成虎，景貴飛，等.第四代GIS軟件研究［J］.中國圖象圖形學報，2001（6）：817－823.

［15］ 姜云昭，朱萬紅，邱國慶.地震次生災害影響條件下人員疏散問題的研究［J］.中國安全生產科學技術，2008（1）：38－41.

［16］ 孔祥春.考慮交叉口延誤的交通緊急疏散研究［D］.天津大學，2007.

［17］ 潘忠.基于幾何的人員疏散仿真研究［D］.同濟大學，2007.

［18］ 謝旭陽，任愛珠，周心權.高層建筑火災最佳疏散路線的確定［J］.自然災害學報，2003，12（3）：75－80.

［19］ 張江華，曹悅，朱道立，等.危險化學品事故應急疏散決策系統設計［J］.科技導報，2005，25（7）：47－51.

［20］ 何淑華，馮敏，陳偉玲.城市地震應急疏散規劃編制研究——以《淄博市中心區地震應急疏散規劃》為例［J］.城市規劃，2008（11）：1－4.