疏散規(guī)劃的一種優(yōu)化算法

尹大朏，方裕

（1.清華大學(xué)地球系統(tǒng)科學(xué)中心，北京 100871；2.北京大學(xué)遙感應(yīng)用研究所，北京 100871）

0 引言

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

疏散規(guī)劃不僅需要為每個待疏散者找到快速抵達(dá)安全目的地的路徑，還要保證這些路徑不相互沖突。疏散規(guī)劃方案的實(shí)質(zhì)在于處理大量疏散人群和有限路網(wǎng)容量之間的矛盾，而疏散算法的難點(diǎn)在于如何盡快地得到合理的疏散規(guī)劃方案。因?yàn)槭枭⑺惴ㄐ枰獜亩鄠€源點(diǎn)、多個時間點(diǎn)出發(fā)的路徑組合中尋找最優(yōu)，而且疏散算法允許逃生者在任意節(jié)點(diǎn)停留任意時間，這樣問題尋優(yōu)搜索的空間極大。

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

1 問題定義與假設(shè)

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

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

圖1 疏散網(wǎng)絡(luò)示例Fig.1 Evacuation network example

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

問題的定義如下：

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

輸出：1個“疏散流”集合，每個疏散流包括流量大小、通過的路網(wǎng)節(jié)點(diǎn)、從每個路網(wǎng)節(jié)點(diǎn)開始的出發(fā)時間（Depart Time）和抵達(dá)時間（Arrival Time）。

約束：主要的約束有：1）路網(wǎng)的容限限制，即同時進(jìn)入一條邊的人數(shù)不能超過路網(wǎng)的最大容限Capacity；2）先入先出準(zhǔn)則FIFO，即進(jìn)入同一條路段的人流，先進(jìn)入該路段首節(jié)點(diǎn)的人抵達(dá)該路段末節(jié)點(diǎn)的時間必定不慢于后進(jìn)入的人。

目標(biāo)：優(yōu)化的目標(biāo)主要取決于：最小化總體逃逸時間（Egress Time）和最小化疏散規(guī)劃生成所需的計(jì)算時間（Computational Time）。

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

2 疏散問題的CCRP算法

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

圖2 CCRP將疏散問題轉(zhuǎn)化為最短路徑計(jì)算Fig.2 Converting the evacuation to shortest path calculation by CCRP

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

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

3 新型算法CCRP＋＋

3.1 CCRP算法的缺陷

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

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

圖3 兩次相鄰迭代 “冗余重復(fù)”擴(kuò)張F(tuán)ig.3 The redundant expansion in adjacent iterations

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

3.2 CCRP＋＋ 算法

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

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

3.3 算法的復(fù)雜性分析

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

4 實(shí)驗(yàn)分析

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

表2 不同網(wǎng)絡(luò)下的測試數(shù)據(jù)Table 2 Test data in different network

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

5 結(jié)語

針對傳統(tǒng)疏散算法CCRP的不足，提出了一種新型的啟發(fā)式疏散算法CCRP＋＋，采用雙優(yōu)先隊(duì)列結(jié)構(gòu)，每次只更新一個源點(diǎn)的最短路徑樹，避免了CCRP每次迭代時進(jìn)行所有源點(diǎn)的最短路徑樹更新，顯著降低了算法的時間復(fù)雜度。真實(shí)路網(wǎng)的模擬實(shí)驗(yàn)表明，CCRP＋＋ 相比CCRP在算法效率和可擴(kuò)展性上都有明顯提升，這一改進(jìn)有助于疏散算法在實(shí)際應(yīng)急指揮系統(tǒng)的應(yīng)用。

［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，F(xiàn)RANCIS 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，F(xiàn)RANCIS R.Evacnet＋：A computer program to determine optimal building evacuation plans［J］.Fire Safety，1985，9（2）：211－222.

［13］ 尹大朏，方裕.應(yīng)用于大規(guī)模災(zāi)害發(fā)生時進(jìn)行人員疏散的快速疏散方法［P］.專利授權(quán)號ZL 2010 1 0279504.3.

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

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

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

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

［18］ 謝旭陽，任愛珠，周心權(quán).高層建筑火災(zāi)最佳疏散路線的確定［J］.自然災(zāi)害學(xué)報(bào)，2003，12（3）：75－80.

［19］ 張江華，曹悅，朱道立，等.危險(xiǎn)化學(xué)品事故應(yīng)急疏散決策系統(tǒng)設(shè)計(jì)［J］.科技導(dǎo)報(bào)，2005，25（7）：47－51.

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