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

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

1.武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北武漢430079；2.國家測繪地理信息局衛(wèi)星測繪應(yīng)用中心，北京100830；3.中國測繪科學(xué)研究院，北京100830

1 引 言

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

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

2 避難所分配模型設(shè)計(jì)原則

首先，為了科學(xué)合理的將預(yù)計(jì)受災(zāi)人員分配到所有的避難場所去，在這里被分配的最小元素非居民個人，而是聚集了一些居民的居民社區(qū)（空間單元），即對居民社區(qū)來分配相應(yīng)的避難所，由于單個居民社區(qū)的空間范圍可能較大，可以將其劃分為多個同等面積大小的網(wǎng)格，再將單個社區(qū)的人口按網(wǎng)格面積占社區(qū)面積比例進(jìn)行分配，并假設(shè)空間單元內(nèi)部的居民是均勻分布的?？傊?，被分配的空間單元范圍越小，這種假設(shè)越合理。

其次，假設(shè)所有的避難所位置都已確定，而且總?cè)萘磕軌蛉菁{所有居民。為了確定每個避難所的服務(wù)范圍，必須考慮每個避難所的容量、居民的空間分布以及居民到達(dá)指定避難所的行程距離，應(yīng)急疏散過程中每個空間單元應(yīng)被指定到盡可能近的避難所。另外，所有避難所服務(wù)范圍空間連續(xù)性也是必須考慮的因素。這就意味著每個避難所的服務(wù)范圍形成一個同質(zhì)區(qū)域，用單個多邊形即可包括，而且這些多邊形覆蓋整個居民區(qū)，在空間上具有排他性。所以，為了科學(xué)合理地對避難所進(jìn)行分配，避難所分配模型遵循以下三個設(shè)計(jì)原則：所有居民到其分配的避難所之間的距離總和盡可能最??；必須保證每個避難所被分配的總?cè)丝诓荒艹銎湟阎畲笤O(shè)計(jì)容量；盡可能地使每個避難所分配的空間單元具有空間連續(xù)性。單個空間單元（如一個居民區(qū)）在算法中作為一個需求點(diǎn)來處理，而每個避難所則代表居住區(qū)內(nèi)的一個點(diǎn)。所以，根據(jù)設(shè)計(jì)原則，定義該模型的目標(biāo)函數(shù)。

2.1 總行程距離最小化

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

2.2 各避難所分配總?cè)藬?shù)不超限

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

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

2.3 保持空間連續(xù)性

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

3 模型核心算法

3.1 構(gòu)建思想

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

3.2 替換插值原理

當(dāng)某一空間單元最近的避難所容納不了該單元內(nèi)的總?cè)丝跁r，則利用空間替換插值機(jī)制為其指定到其他合理避難所。替換插值的過程如圖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(bǔ)分配給S3會妨礙S3的空間連續(xù)性，而且可能增加總行程成本。因此，就應(yīng)該尋找一個稱之為替換單元的空間單元，如圖1（c），這個空間單元必須已經(jīng)分配給S1或S2，且與S3的服務(wù)范圍相鄰，并將之插入到S3。這時，S1或S2中被替換單元占用的容量可以空出并分配給a，如圖1（d）。在這里，直接插入或替換插入必須最大程度地節(jié)約行程成本。根據(jù)這一原則，用式（4）可以計(jì)算在尋找a的替換單元b時節(jié)約的行程成本，并使其最大化來實(shí)現(xiàn)總行程距離最小化

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

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

4 試驗(yàn)及結(jié)果

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

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

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

情況3：應(yīng)用本文算法，用替換插入機(jī)制來調(diào)整已滿員的較近避難所，并以式（4）中SCt最大化尋找替換單元，實(shí)現(xiàn)避難所合理分配。

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

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

5 分析與比較

根據(jù)試驗(yàn)的結(jié)果，考慮到避難所分配時的實(shí)際問題，從三個方面對不同算法結(jié)果進(jìn)行對比分析，以反映各算法的優(yōu)越性。

5.1 避難所容量是否超限

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

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

5.2 避難所服務(wù)范圍是否空間連續(xù)

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

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

5.3 總行程距離比較

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

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

6 結(jié) 論

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

［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.（張子民，李琦.應(yīng)急撤離建模研究的現(xiàn)狀、問題與發(fā)展趨勢［J］.中國安全科學(xué)學(xué)報(bào)，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.（周天穎，簡甫任.緊急避災(zāi)場所區(qū)位決策支持系統(tǒng)建立之研究［J］.水土保持研究，2001，18（1）：17－24.）

［7］ XIE Shunping，F(xiàn)ENG 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（謝順平，馮學(xué)智，魯偉.基于道路網(wǎng)絡(luò)分析的Voronoi面域圖構(gòu)建算法［J］.測繪學(xué)報(bào)，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.（王健，胡曉偉，佟晶晶，等.基于車道建模的區(qū)域應(yīng)急疏散路徑規(guī)劃［J］.交通運(yùn)輸工程學(xué)報(bào)，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.（譚滿春，唐松安，徐建閩.多車道高速公路的動態(tài)離散交通流模型［J］.中國公路學(xué)報(bào)，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空間關(guān)系的基本問題與研究進(jìn)展［J］.測繪學(xué)報(bào)，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.（李剛，馬東輝，蘇經(jīng)宇，等.基于加權(quán)Voronoi圖的城市地震應(yīng)急避難場所責(zé)任區(qū)的劃分［J］.建筑科學(xué)，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.（蘇幼坡，劉瑞興.城市地震避難所的規(guī)劃原則與要點(diǎn)［J］.災(zāi)害學(xué)，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.（楊文斌，韓世文，張敬軍，等.地震應(yīng)急避災(zāi)場所的規(guī)劃建設(shè)與城市防災(zāi)［J］.自然災(zāi)害學(xué)報(bào)，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.（姚清林.關(guān)于優(yōu)選城市地震避災(zāi)場地的某些問題［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.