應急物資儲備庫多級覆蓋選址模型的構建

肖俊華，侯云先

(1.中國農業大學 經濟管理學院，北京100083；2.北京勞動保障職業學院，北京102200)

0 引言

應急物資儲備庫選址問題屬于設施選址問題的范疇。設施選址問題是選址問題中傳統的一個研究領域，有較長的研究歷史，有豐富的研究成果。1963年，Cooper[1]正式提出了設施選址問題，并初步探討了相關求解方法。Hakimi[2]于1964年發表的論文是設施選址問題發展為一個系統、科學理論的里程碑。此后，選址問題被引入一個更寬廣的領域[3-6]。對于應急設施的選址研究，部分文獻的選址模型在供應鏈特征上多為單層覆蓋，且服務種類為單源服務，即一個需求點只由距其最近的一個設施點提供服務[7～9]。但考慮到在重大突發事件下，考慮到需求點因對應急物資的需求量巨大而單個設施往往不能滿足需求而需要多個設施為其服務的情況，Hogan,K.等[10]提出了一個考慮備用覆蓋的最大覆蓋模型，該模型在為需求點提供一個服務設施的同時，又提供了一個相同服務質量的備用設施為需求點提供服務。王文峰等[11]對覆蓋的概念進行擴展，考慮了應急服務的多源服務特性，提出了一個應急服務設施的多級覆蓋選址模型,并運用分布估算法對模型進行求解；葛春景等[12]對重大突發事件應急需求多點同時需求和多次需求的特點，引入最大臨界距離和最小臨界距離的概念，建立了多重數量和質量覆蓋模型，并提出改進的遺傳算法進行求解。Murali P等[13]研究了應對生物恐怖襲擊時，提出了一個需求不確定的容量限制設施選址模型，該模型中，需求點由多個分布在不同覆蓋水平的設施提供服務，運用定位-分配啟發式算法進行求解。

本文擬在借鑒上述模型多源服務思想的基礎上，對備用覆蓋思想進一步延伸，建立應急物資儲備庫多級最大覆蓋選址模型。模型中需求點物資需求由處于不同服務等級的設施點提供，需求點物資的需求量等于各服務等級設施點提供的物資之和；各服務等級由需求點和設施點的距離確定。本文將設計遺傳算法，并運用Matlab7.0對模型進行算法實現和算例分析，驗證模型和算法的有效性，并以北京市房山區應急物資儲備庫選址為例進行實證研究。

1 問題描述與模型建立

1.1 問題描述

本文應急物資儲備庫選址問題涉及兩類站點，一類為需求站點，文中統稱為需求點；另一類為服務站點，即應急物資儲備庫，文中統稱為設施點。設施點為需求點提供服務，本文以距離表示設施點與需求點之間的聯系緊密程度。本文建立應急物資儲備庫多級最大覆蓋選址模型，模型假設如下：

假設1：設施點和需求點均為離散的，且以點狀產生；

假設2：任意設施點和需求點的距離可通過調查或計算產生；

假設3：設施點可以建立在需求點上，也可以獨立于需求點之外，單獨建立；

假設4：設施點可以為多個需求點提供服務，且設施點服務能力無限制；

假設5：待建設施點的數量有限，為p個；

假設6：需求點有k級需求覆蓋水平，且在其每一個需求覆蓋水平上最多由一個設施為其提供服務，即假設一個需求點有3個需求覆蓋水平，則該需求點最多可以有3個設施為其提供服務，如圖1所示；

假設7：需求點在k級需求覆蓋水平上的需求量為該點需求量的fk倍。

圖1 多級覆蓋的示意圖

1.2 模型的構建

2 模型求解算法設計

最大覆蓋選址模型已經被證明為NP-Hard問題[14]，而本文所建多級最大覆蓋選址模型是最大覆蓋模型的擴展，所以也是NP-Hard問題。遺傳算法作為一種實用、高效、魯棒性強的優化技術，發展極為迅速，已引起國內外學者的高度重視[15]。盡管遺傳算法是求解大型組合最優化問題的最具有潛力的方法[16]，并且在許多優化領域都有豐富的文獻資料[17]，但是將其應用到設施選址問題尤其是最大覆蓋選址問題的研究文獻卻相對較少[18]。因此，本文利用遺傳算法對多級最大覆蓋選址模型進行求解，具體實現技術如下：

（1）編碼方案

對所有的備選設施按1至n進行賦值，每個代碼表示一個基因。每個染色體代表模型的一個可行解，染色體的每一個基因代表選擇的備選設施，每一染色體中的基因長度和限定的設施數量相同，假設需選擇的設施數為p個，則每個染色體的長度為p。

（2）初始種群的產生

種群的規模和群體的初始化是影響算法收斂性的兩個重要因素。Alander[19]的試驗結果表明種群規模在染色體長度的一倍到兩倍之間是較好的選擇，綜合考慮種群的多樣性要求和計算效率，本文使用染色體長度的2倍，也就是待建設施個數的2倍為種群規模。初始種群中的每個染色體通過隨機的方法生成。

（3）適應值計算及評價

染色體的適應度評估由目標函數式（1）來計算。具體計算過程如下：

步驟1：選擇第一個需求點，計算其到染色體中每一個基因的距離，對距離進行升序排序，選擇前k個距離dk，k∈｛1,2,…,k｝；

步驟2：判斷距離dk與各覆蓋等級最大距離Dk的關系，若dk小于Dk，則表示需求點可以獲得第K級需求覆蓋水平的物資量，求出需求點獲得的總物資量；

步驟3：重復步驟1-2，遍歷全部需求點，得到全部需求點獲得的總物資量。

（4）選擇、交叉和變異操作

父代的選擇采用從群體中隨機選擇的方式，以保證每個個體都有同樣的機會進行交叉；兩個父代個體采用傳統的單點交叉的方式進行繁殖，生成新的子個體，每對父個體交叉只產生一個子個體。例如：用P1和P2分別表示兩個父個體，用C1表示子個體，隨機產生交叉點，兩個父個體P1：（1 4 6 13 14）和P2：（2 7 8 10 16），設交叉點為3，則生成的子個體為C1：（1 4 8 10 16）；變異操作可以避免算法陷入局部最優解，通常變異率的值較低，本文將變異率設為0.1。

（5）終止條件

遺傳算法是一種反復迭代的隨機搜索方法，在每次迭代中，記下適應值最大的染色體，直到已經達到了算法規定的最大迭代次數或在規定的連續迭代次數內最好的染色體不再發生變化時算法終止。當算法終止時，最好的染色體即是該選址問題的最優解。

（6）遺傳算法具體操作流程

步驟1：對數據進行實數編碼，構造備選設施點與需求點之間的距離矩陣Cm×n；定義遺傳算法參數（群體規模N、最大遺傳代數Maxgen、交叉概率pc、變異概率pm）；

步驟2：用隨機的方法生成初始化種群P(0)，令t=1，P(t)=P(0)；

步驟3：計算種群P(t)的適應值；

步驟4：用隨機選擇策略選擇兩個父個體P1和P1，進行交叉、變異、重插入等操作得到子種群Q(t)；

步驟5：將P(t)和Q(t)合并，得到新的種群R(t)；

步驟6：對新種群R(t)進行優劣排序，得到P(t+1)；步驟7：t=t+1，判斷是否滿足結束條件，如果否，轉步驟3；否則結束，輸出結果(見圖 2)。

圖2 遺傳算法流程圖

3 算例分析

為驗證算法的可行性和分析算法的效果，本文應用Matlab7.0編程，并在DELL N4040筆記本電腦上（雙核酷睿i3 CPU，主頻2.53G，2G內存）進行了計算實驗。假設需求點分別為50、100和200，候選設施點分別為15、20、30，待建設施分別為5、8、10、12。需求點和設施點的位置在一個[0,100]的平面上均勻分布；需求點與設施點的距離為歐式距離。

本文模型為三級水平覆蓋，各覆蓋等級的覆蓋半徑由式Dk=δ*max{}dij確定，其中maxdij為需求點和備選設施點的最大距離，m分別為0.2、0.4和0.6；需求點對各覆蓋等級的需求百分比分別為60%、30%和10%，為了簡化計算，此處假設各需求覆蓋水平的權重均為1。表1為各個選址方案的遺傳算法運算結果分析。

表1 遺傳算法運算結果分析

由表1可知，運用遺傳算法分別對50、100和200三種不同規模的需求點的選址方案進行計算，當選擇建立12個設施點時，需求點的滿意度可達100%，即完全覆蓋需求點。實驗中各種組合方案的遺傳算法運算時間均小于5秒鐘，說明遺傳算法在求解多級最大覆蓋選址模型時具有較好的計算能力。

4 結論

在分析重大突發事件下，傳統的最大覆蓋選址模型不能滿足實際需要的情況下，提出基于備用覆蓋和部分覆蓋的應急物資儲備庫的多級覆蓋選址模型，考慮了不同覆蓋距離提供不同覆蓋水平服務的問題。然后基于Matlab7.0設計遺傳算法對多級覆蓋選址模型進行了求解；并用一個算例驗證了模型和算法的可行性和有效性。算例結果顯示，本文設計的遺傳算法在求解多級覆蓋選址模型時具有較高的運算速度和較好的收斂性。

本文在進行應急物資儲備庫選址時，僅考慮了距離對應急物資儲備庫選址的影響，且假設設施的服務能力是無限的。在現實中，影響應急物資儲備庫選址的因素是多方面的，如需求點的災害風險程度、實際人口密度、設施服務能力等都會對設施選址生影響，同時設施點本身的地質條件、交通條件、建設成本等也會影響設施的選址結果。因此考慮多影響因素，將系統工程理論中多準則決策分析方法和運籌學的組合優化選址模型結合進行應急物資儲備庫選址將是本文的一個拓展方向。

[1]Cooper L.Location-allocation Problems[J].Operation Research,1963,11.

[2]Hakimi S.L.Optimum Locations of Switching Centers and the Abso?lute Centers and Medians of a Graph[J].Operations Research,1964,12(3).

[3]Wang F,Xu Y,Li Y X.A Review of the Discrete Facility Location Problem[J].International Journal of Plant Engineering and Manage?ment,2006,11(1).

[4]Brandeau M L,Chui S S.An Overview of Representative Problems in Location Research[J].Management Science,1989,35(6).

[5]Hamacher H W,Nickel S.Classification of Location Models[J].Loca?tion Science,1998,6(1).

[6]Klose A,Drexl A.Facility Location Models for Distribution System Design[J].European Journal of Operational Research,2004,162(1).

[7]陸相林,侯云先.基于設施選址理論的中國國家級應急物資儲備庫配置[J].經濟地理,2010,30(7).

[8]陸相林，侯云先，林文，申強.基于設施選址理論的小城鎮應急醫療服務中心功能優化——以山東省滕州市為例[J].經濟地理,2011,31(7).

[9]陸相林,侯云先,林文,申強.基于選址理論的小城鎮應急物資儲備庫優化配置——以北京房山區為例[J].地理研究,2011,30(6).

[10]Hogan K,C.S.ReVelle.Concepts and Applications of Backup Cover?age[J].Management Science,1986,32(22).

[11]王文峰,郭波,劉新亮.多級覆蓋設施選址問題建模及求解方法研究[J].中國管理科學,2007,15(z1).

[12]葛春景,王霞,關賢軍.重大突發事件應急設施多重覆蓋選址模型及算法[J].運籌與管理，2011,20(5).

[13]Murali P,et al.Facility Location under Demand Uncertainty：Re?sponse to a Large-scale Bio-terror Attack[J].Socio-Economic Plan?ning Sciences,2012,46(1).

[14]Kariv O,Hakimi S.An Agorithm Aproach to Ntwork Location Prob?lem[J].SIAM Journal of Applied Mathematics,1979,37.

[15]雷英杰,善文等.MATLAB遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社,2005.

[16]王小平,曹立明.遺傳算法——理論、應用與軟件實現[M].西安：西安交通大學出版社,2003.

[17]趙冬玲,孔志周,官東.基于改進遺傳算法的物流配送中心選址研究[J].統計與決策,2008,(11).

[18]Jorge H J,Joy B,Rajan B.On the Use of Genetic Algorithms to Solve Location Problems[J].Computers&Operations Research,2002,29.

[19]Alander J T.On Optimal Population Size of Genetic Algorithms.Pro?ceedings of CompEuro,1992.