基于行程距離最優及容量受限的避難所分配算法研究

李久剛，唐新明，劉正軍，汪匯兵

1.武漢大學資源與環境科學學院，湖北武漢430079；2.國家測繪地理信息局衛星測繪應用中心，北京100830；3.中國測繪科學研究院，北京100830

1 引 言

各種自然災害及事故災難給人類造成了嚴重的人員傷亡和經濟損失，并且大多數災害過程中的人員傷亡是由于受災人員得不到及時的科學疏散所造成的［1］。因此，在突發事件發生前或災害發生過程中，有效地實施應急疏散策略對提高城市災時應急響應能力具有非常重要的意義，應急避難場所科學分配就是策略之一。

應急疏散過程中的避難場所分配實際上也是劃定避難場所空間服務范圍的過程。目前，在劃定設施服務范圍方面，國內外已有學者做過相關研究，如雷達氣象站、消防站以及特快列車車站等［2－5］，這些應用大多都是通過GIS軟件的緩沖分析功能實現［6］。但這樣劃定的設施服務范圍在空間上沒有考慮到排他性，往往會產生重疊。而災區人員（空間單元）針對避難所的分配具有明顯的排他性。文獻［7］采用網絡最短距離分析和最短路徑時間分析構建的Voronoi面域圖，可以模擬出功能中心點輻射影響范圍空間劃分的實際情況，以及Thiessen多邊形被廣泛應用等［8－9］，在這些方法中考慮到服務范圍的排他性，但未考慮設施的容量。并且這些方法都假設潛在需求在空間上是均勻分布的，其難以準確處理不均勻分布的需求。在綜合對比上述方法的基礎上，針對城市重大突發事件人員緊急疏散策略，提出一種基于替換插值機制的城市災害避難所分配算法。該算法充分考慮到避難所的容量限制及城市居民在空間分布上的不均勻性，在保證所有被分配空間單元都能分配到唯一的避難所的基礎上，避免避難所過度擁擠，減少總行程距離，并且盡可能維持單個避難所服務范圍的空間連續，為應急疏散提供輔助決策。

2 避難所分配模型設計原則

首先，為了科學合理的將預計受災人員分配到所有的避難場所去，在這里被分配的最小元素非居民個人，而是聚集了一些居民的居民社區（空間單元），即對居民社區來分配相應的避難所，由于單個居民社區的空間范圍可能較大，可以將其劃分為多個同等面積大小的網格，再將單個社區的人口按網格面積占社區面積比例進行分配，并假設空間單元內部的居民是均勻分布的。總之，被分配的空間單元范圍越小，這種假設越合理。

其次，假設所有的避難所位置都已確定，而且總容量能夠容納所有居民。為了確定每個避難所的服務范圍，必須考慮每個避難所的容量、居民的空間分布以及居民到達指定避難所的行程距離，應急疏散過程中每個空間單元應被指定到盡可能近的避難所。另外，所有避難所服務范圍空間連續性也是必須考慮的因素。這就意味著每個避難所的服務范圍形成一個同質區域，用單個多邊形即可包括，而且這些多邊形覆蓋整個居民區，在空間上具有排他性。所以，為了科學合理地對避難所進行分配，避難所分配模型遵循以下三個設計原則：所有居民到其分配的避難所之間的距離總和盡可能最小；必須保證每個避難所被分配的總人口不能超出其已知最大設計容量；盡可能地使每個避難所分配的空間單元具有空間連續性。單個空間單元（如一個居民區）在算法中作為一個需求點來處理，而每個避難所則代表居住區內的一個點。所以，根據設計原則，定義該模型的目標函數。

2.1 總行程距離最小化

式中，V為總行程距離，即所有分配空間單元中的所有預計受災人員到其所分配的避難所之間的行程距離總和；M為避難所數量；N為空間單元數量；i和j分別為避難所和空間單元編號；rj為空間單元j內居民的數量；tij為從空間單元j到避難所i的行程距離，即空間單元j中心點到避難所i點之間的直線距離，用式來表示，式中tij也稱歐氏距離，xi和yi表示避難所i配的坐標值，當避難所i分配給空間單元j，則xij＝1，否則xij＝0；對于每一個，以確保每個空間單元都能且只能分配到一個避難所。

2.2 各避難所分配總人數不超限

設cmaxi為避難所i的最大容量，容量控制定義如下

表示每個避難所計劃容量為其最大設計容量與最大空間單元人數之差，這就保證當避難所未達到計劃容量時，任何空間單元都可以直接分配給該避難所，實際情況下，cmaxi和rj通常都是已知的，而cplai可由式（3）來決定。

2.3 保持空間連續性

空間連續性即分配到同一避難所的空間單元是連續的，并位于同一個多邊形空間范圍內。對于每個避難所，由一個單鏈表記錄分配到的空間單元。在該單鏈表中，元素（即分配到的空間單元序號）按照使用該避難所的優先級排列，且避難所的容量應盡可能地充分利用，并且通過鏈表，結合替換插值方法，可以盡可能地保證避難所分配的空間單元保持空間連續性。單鏈表定義如下：① 如果xij＝1，則空間單元j在避難所i的單鏈表里，且在單鏈表中的編號為indexij；②如果xijn＝1，xijm＝1，且tijn＜tijm，則indexijn＜indexijm，這表明空間單元距離避難所越近，越能夠優先分配到避難所；③如果xijn＝1，xijm＝1，tijn＝tijm，且rjn≤rjm，則indexijn＜indexijm，這表明當距離相等時，空間單元人數越少，越能夠優先分配到避難所。

3 模型核心算法

3.1 構建思想

為單個空間單元選擇避難場所時，其原理是當滿足下列插入條件中任何一條時，一個空間單元a可以分配到避難所S，即被插入避難所S的單鏈表中，式中jlast表示避難所S的單鏈表中的最后一個空間單元。三個條件分別為：①cactS≤cplaS；②cactS＞cplaS且tSjlast＞tSa；③cactS＞cplaS，tSjlast＝tSa，rjlast＞ra。條件①表示避難所S有剩余容量，且式（3）確保插入后cacti≤cmaxi，即實際人數小于最大容量。條件②和條件③表示空間單元a比已插入避難所S鏈表中的其他空間單元擁有更高的優先級。對每一個空間單元j，算法在所有避難所i中按照tij的升序尋找滿足一個插入條件的避難所。如果第一最近避難所i1符合條件，則采用直接插入，即直接將j插入到i1的單鏈表中，且xi1j＝1；否則采用替換插入，調整空間單元和避難所之間的關聯關系，減少總行程成本，并保持服務范圍的空間連續性，替換插入的原理后面詳細闡述。

3.2 替換插值原理

當某一空間單元最近的避難所容納不了該單元內的總人口時，則利用空間替換插值機制為其指定到其他合理避難所。替換插值的過程如圖1所示。

圖1 替換差值原理圖Fig.1 Schematic diagram of shift insertion

圖中有3個避難所，S1、S2和S3，每個避難所都被分配了一些空間單元。圖1（a）中黑色的空間單元a尚未分配到任何避難所，且tS1a＜tS2a＜tS3a。如果S1滿足一個插入條件，則a被插入到S1的單鏈表中，即直接插入。否則，如果S1和S2都不滿足任何插入條件，只有S3滿足一個插入條件，則a被分配給S3如圖1（b）。但是，把a分配給S3會妨礙S3的空間連續性，而且可能增加總行程成本。因此，就應該尋找一個稱之為替換單元的空間單元，如圖1（c），這個空間單元必須已經分配給S1或S2，且與S3的服務范圍相鄰，并將之插入到S3。這時，S1或S2中被替換單元占用的容量可以空出并分配給a，如圖1（d）。在這里，直接插入或替換插入必須最大程度地節約行程成本。根據這一原則，用式（4）可以計算在尋找a的替換單元b時節約的行程成本，并使其最大化來實現總行程距離最小化

式中，SCt表示替換插入節約的總行程成本；tSfa＋tSkb是直接插入的行程成本；tSka＋tSfb是替換插入的行程成本。如果最大SCt為負數或零，則算法將按直接把a插入到Sf的單鏈表中。否則，a的替換單元b可行，則進行替換插入。整個替換插入算法總過程如圖2所示。

圖2 避難所分配算法流程圖Fig.2 The flow chart of shelter assignment algorithm

4 試驗及結果

利用Java程序實現上述算法，并以烏魯木齊市中心的部分社區人口統計數據來進行試驗分析，由于實際統計的街道社區單元空間范圍較大，為更好地驗證空間單元對避難所的分配效果，利用行程成本網格制定滿足網絡上和網絡外的火車站服務范圍的思想［10］。試驗中也將所有的街道社區單元進行網格化，網格邊長大小為0.5km，試驗中總人口數為701 044，被分配到1 263個網格單元中，市區20個避難場所均有各自的容量限制。針對已有的劃定服務范圍，結合本文提出的算法，利用已有的數據對以下三種不同情況進行試驗，不同情況下的避難所劃定原則描述如下。

情況1：每個空間單元都分配到一個最近的避難所，而不考慮各避難所容量限制。

情況2：考慮各避難所容量限制，但都用直接插入來分配給未滿員的避難所。

情況3：應用本文算法，用替換插入機制來調整已滿員的較近避難所，并以式（4）中SCt最大化尋找替換單元，實現避難所合理分配。

通過比較三種情況的運行結果，可以評價替換插入機制和選擇替換單元方法的效果。圖3分別展示在基于網格模式下，用直線距離作為行程距離，三種情況所劃定的服務范圍分布圖。

圖3 三種不同算法劃定避難所服務范圍Fig.3 The shelter assignment chart of cell for three scenarios

5 分析與比較

根據試驗的結果，考慮到避難所分配時的實際問題，從三個方面對不同算法結果進行對比分析，以反映各算法的優越性。

5.1 避難所容量是否超限

從圖3（a）中的結果可以得到，情況1的分配結果中有S14、S15、S16三個避難所嚴重超出其本身容量限制，而避難所S3又存在分配人數不足。其中情況1也為目前大多數服務范圍劃定算法，如文獻［8—9］提到的算法思想，其不考慮容量限制，只尋求最近目標進行分配。圖3（b）、（c）分別為情況2和情況3的試驗結果，這兩種情況均無避難所超限情況。各情況算法結果比較如表1所示。

表1 各算法避難所是否超限比較Tab.1 Comparison of overstep capability of three scenarios

5.2 避難所服務范圍是否空間連續

從圖3（b）中的結果可以看出，情況2的分析結果中有一些避難所明顯具有較多的零散空間單元，如避難所S8所分配的一些空間單元竟然位于S15的下方，這就是說S15下方的一些空間單元要跨越好幾個較近的避難所而去S8避難所，這在實際應急疏散中肯定是不合理的。而情況1和情況3的各避難所分配的所有空間單元均具有很好的空間連續性，都在同一空間范圍內。各算法分配結果比較如表2所示。

表2 各算法空間連續性比較Tab.2 Comparison of keep the spatial service continuity of three scenarios

5.3 總行程距離比較

這里的總距離就是每種情況下的所有避難所與其所分配的空間單元之間的歐式距離總和，即式（1）中的V。圖4中對比說明了三種情況下的總行程距離。從圖中可以看出，情況1總是產生最低的總行程距離，情況2最高，而情況3介于兩者之間。

圖4 不同方法分配避難所行程總和比較Fig.4 Comparison of total travel cost of three scenarios

6 結 論

通過試驗及對結果綜合性分析，基于替換插值機制的避難所分配算法與目前已有的其他同類算法相比具有優越性，其不僅能有效地避免各避難所容量超限與過度擁擠，并能夠很好地保持各避難所服務范圍空間連續，同時做到約束條件下的總行程距離最小化。試驗結果初步驗證了算法的有效性及可行性，并能在城市突發事件人員緊急疏散時起到良好的決策輔助作用。實際情況下，基于街區范圍的分配可能更合理，但其空間范圍的粒度往往太大，在使用大尺度的人口統計資料時，網格單元更為有效。此外，該算法目前旨在初探避難所宏觀分配策略，由于暫時無法獲取到烏魯木齊市區詳細的道路網絡數據，故本次試驗過程中的行程距離采用直線距離而非實際道路網絡距離；同時，試驗過程中目前也暫未考慮到災害應急疏散的緊迫性和動態演化性，計劃在后續研究中結合其他城市詳細的道路網絡數據及通達性進行深入探討分析，同時對算法進行優化和改進，以體現應急疏散的動態演化效果。

［1］ ZHANG Zimin，LI Qi.The Current Situation，Issues and Trends of Evacuation Modeling in Emergency［J］.China Safety Science Journal，2008，18（10）：120－126.（張子民，李琦.應急撤離建模研究的現狀、問題與發展趨勢［J］.中國安全科學學報，2008，18（10）：120－126.）

［2］ MINCIARDI R，SACILE R，SICCARDI F，et al.Optimal Planning of a Weather Radar Network［J］.Journal of Atmospheric and Oceanic Technology，2003，20（9），1251－1263.

［3］ TOREGAS C，SWAIN R，REVELLE C，et al.The Location of Emergency Service Facilities［J］.Operations Research，1971，19（6），1363－1373.

［4］ PLANE D R，HENDRICK T E.Mathematical Programming and the Location of Fire Companies for the Denver Fire Department［J］.Operations Research，1977，25（4），563－578.

［5］ GLEASON J M.A Set Covering Approach to Bus Stop Location［J］.Omega，1975，3（5），605－608.

［6］ ZHOU Tianying，JIAN Furen.Study on Establishing the Supporting System for Location of the Urgent Refuge［J］.Research of Soil and Water Conservation，2001，18（1）：17－24.（周天穎，簡甫任.緊急避災場所區位決策支持系統建立之研究［J］.水土保持研究，2001，18（1）：17－24.）

［7］ XIE Shunping，FENG Xuezhi，LU Wei.Algorithm for Constructing Voronoi Area Diagram Based on Road Network Analysis［J］.Acta Geodaetica et Cartographica Sinica，2010，39（1）：88－94（謝順平，馮學智，魯偉.基于道路網絡分析的Voronoi面域圖構建算法［J］.測繪學報，2010，39（1）：88－94.）

［8］ HUANG B，LIU N.Bi－level Programming Approach to Optimizing a Logistic Distribution Network with Balancing Requirements［J］.Transportation Research Record：Journal of the Transportation Research Board，2004，18（9），188－197.

［9］ UPCHURCH C，KUBY M，ZOLDAK M，et al.Using GIS to Generate Mutually Exclusive Service Areas Linking Travel on and off a Network［J］.Journal of Transport Geography，2004，12（1），23－33.

［10］ BOYLE P J，DUNN C E.Redefinition of Enumeration District Cancroids：A Test of Their Accuracy Using Thiessen Polygons［J］.Environmental Planning A，1991，23（8）：1111－1119.

［11］ WANG Jian，HU Xiaowei，TONG Jingjing，et al.Route Planning of Regional Emergency Evacuation Based on Lane Modeling［J］.Journal of Traffic and Transportation Engineering，2010，10（2）：82－87.（王健，胡曉偉，佟晶晶，等.基于車道建模的區域應急疏散路徑規劃［J］.交通運輸工程學報，2010，10（2）：82－87.）

［12］ TAN Manchun，TANG Songan，XU Jianmin.Dynamic Discrete Traffic Model of Freeway with Multiple Lanes［J］.China Journal of Highway and Transport，2002，15（2）：91－94.（譚滿春，唐松安，徐建閩.多車道高速公路的動態離散交通流模型［J］.中國公路學報，2002，15（2）：91－94.）

［13］ CHEN Jun，ZHAO Renliang.Spatial Relations in GIS：A Survey on Its Key Issues and Research Progress［J］.Acta Geodaetica et Cartographica Sinica，1999，28（2）：97－102.（陳軍，趙仁亮.GIS空間關系的基本問題與研究進展［J］.測繪學報，1999，28（2）：97－102.）

［14］ LI Gang，MA Donghui，SU Jingyu，et al.Multiplicatively Weighted Voronoi Diagrams for Responsibility Space Regionalization of Urban Earthquake Emergency Shelters［J］.Building Science，2006，22（3）：55－59.（李剛，馬東輝，蘇經宇，等.基于加權Voronoi圖的城市地震應急避難場所責任區的劃分［J］.建筑科學，2006，22（3）：55－59.）

［15］ SU Youpo，LIU Ruixing.Planning Principles and Outlines of Urban Earthquake Shelters［J］.Journal of Catastrophology，2004，19（1）：87－92.（蘇幼坡，劉瑞興.城市地震避難所的規劃原則與要點［J］.災害學，2004，19（l）：87－92.）

［16］ YANG Wenbin，HAN Shiwen，ZHANG Jingjun，et al.Planning Construction of Earthquake Emergency Shelters and Urban Disaster Reduction［J］.Journal of Natural Disasters，2004，13（1）：126－132.（楊文斌，韓世文，張敬軍，等.地震應急避災場所的規劃建設與城市防災［J］.自然災害學報，2004，13（l）：126－132.）

［17］ YAO Qinglin.On Some Questions of Optimally Selecting Refuges for Large Earthquake［J］.Journal of Seismological Research，1997，19（3）：244－248.（姚清林.關于優選城市地震避災場地的某些問題［J］.地震研究，1997，19（3）：244－248.）

［18］ AURENHAMMER F.Voronoi Diagrams——a Survey of a Fundamental Geometric Data Structure［J］.ACM Computing Survey，1991，23（3）：345－405.