基于二型模糊集理論的應急設施選址方法

楊 廣 映，門 金 坤，蔣 鵬*，鄭 松，孔 亞 廣，沈 剛，趙 燁，蘇 楠

( 1.臺州學院 電子與信息工程學院(大數據學院)， 浙江 臺州 318000；2.杭州電子科技大學 自動化學院， 浙江 杭州 310000；3.浙江中天氟硅材料有限公司， 浙江 衢州 324000；4.衢州市特種設備檢驗中心， 浙江 衢州 324000；5.杭州市西湖區保障性住房管理服務中心， 浙江 杭州 310000 )

0 引 言

應急設施作為突發事件應急管理系統的基礎組成部分，其布局直接影響事故的預防、準備、響應和善后工作.合理的應急設施選址決策一方面可以提高應急管理的效率和有效性，另一方面可以降低建立這些設施和開展應急救援行動的固定成本和可變成本.研究應急設施選址方法，對于提升突發事件應急管理水平意義重大.

應急設施選址問題(emergency facility location problem，EFLP)本質上是一種設施選址問題(facility location problem，FLP)，也稱為選址分析[1].最初的FLP被稱為韋伯問題(Weber problem，WP)，其目的是為了確定單個倉庫的位置，從而最小化倉庫與客戶之間的總距離.此后，對選址問題的研究產生了許多經典框架來解決各種FLP[2-7].優化目標是區分選址模型的重要依據.根據模型的優化目標，EFLP的相關研究可分為3類[8]：p-中值問題(p-median problem)[9]、p-中心問題(p-center problem)[10]和覆蓋問題(covering problem，CP)[11].

Hakimi[12]首次提出了p-中值問題的概念，定義為：規劃p個設施的位置，以最小化受災點和設施點之間的平均(總)距離.Carbone[13]針對醫療中心的選址問題，提出了一個確定性p-中值模型，目的是使多個用戶到醫療中心的距離最小化.由于每個需求節點上的用戶數量是不確定的，進一步將確定性p-中值模型擴展到機會約束模型，該模型尋求最大化閾值，同時確保總行程距離低于閾值的概率小于指定置信度水平α.Abareshi等[14]研究了一個雙層模型來探索最小信息方法下的p-中值問題，在滿足客戶需求的同時，確定最可能的分配方案，采用了拉格朗日對偶方法將帶負載約束的雙層p-中值模型簡化為單層問題，并引入了混合整數線性規劃方法來提升問題求解效率.Herrán等[15]提出了求解漢密爾頓p-中值問題的VNS元啟發式方法.Herda[16]為近似求解帶負載約束的p-中值問題，提出了一種基于高性能計算集群的遺傳算法.與專注于優化應急系統整體性能的p-中值問題相反，p-中心問題試圖最小化每個需求點與其最近設施之間的最大距離，因此p-中心問題也被稱為Minimax模型.p-中心問題認為需求點總是由其最近的設施提供服務，從而實現了對需求點的全覆蓋，因此p-中心問題特別關注最差的服務情況.在過去的幾十年里，p-中心問題及其擴展[8，17-18]已經被廣泛應用于應急中心、醫院、消防站和其他公共設施的選址規劃中.Du等[19]針對EFLP構建了兩階段魯棒優化框架下的可靠性p-中心模型，關注每個客戶的可靠性，提出了本構方程的求解方法，包括雙切削平面法和約束生成法.Mladenovi等[20]在無三角不等式的情況下提出了基于變鄰域搜索和兩個禁忌搜索啟發式的p-中心問題求解方法，展示了如何更有效地利用鄰域結構求解p-中心問題.針對大規模自然災害事故，Xi等[4]提出了一個改進的p-中值問題，該問題在訪問需求點所需最長時間的約束下，使總距離和應急設施的數量都最小化.CP是EFLP最常見的形式之一[21]，其目標是為需求點提供覆蓋，此類問題易于理解，模型構造簡單，因此在現實生活的適用性很強，如派出所、圖書館、醫院和廢物處理站等設施的選址問題都可以表述為CP.一般來說，只有在設施可在預定義的距離限制內服務某需求點時，才認為設施可為該需求點提供有效覆蓋，此預定義的距離限制被稱為覆蓋距離或覆蓋半徑.Li等[22]提出了設施服務能力與服務距離之間的衰減關系函數.針對災難性連鎖化工事故，Men等[23]提出了一種基于多米諾效應風險的應急設施選址多目標優化方法.Zhang等[24]針對不確定性條件下的EFLP，構建了基于不確定理論的LSCP模型，利用逆不確定性分布，將不確定環境下的LSCP模型轉化為等價的確定性位置模型進行求解.

鑒于EFLP的地理性質，大多數研究將時間和距離視為應急設施選址決策的關鍵因素.目標函數通常側重于滿足預定義的受災地點(需求點).傳統的空間優化模型[5，25-29]通常并不會對這些預定義的需求點加以區分.然而，不同需求點對應急資源的需求程度往往與區域內人口密度密切相關[30].選址準則不僅應考慮應急設施的空間特征，還應考慮選址區域內的人口分布.此外，由于人口的流動性，實際應用中通常難以獲得精確的人口密度數據.在確定性環境下所得的應急設施選址決策可能難以滿足突發事件風險管理的實際需求.

綜上，本文分析選址決策的人口因素和地理因素，建立一個選址集最大覆蓋模型，以區域人口密度量化每個需求點對應急資源的需求程度，期望在資源有限的情況下尋求給定數量應急設施的最大覆蓋程度，并且盡可能側重于滿足人口密度較高區域的應急需求.由于人口的流動性，將人口密度定義為一個梯形區間二型模糊變量.根據梯形區間二型模糊變量的上/下邊界隸屬度函數，結合置信度理論與機會約束規劃方法將原模糊模型轉化為其等價確定性模型.為了處理模型中大規模復雜高維的空間地理數據，采用一種基于網格空間表示法的矩陣編碼策略與遺傳算法耦合進行模型求解，以避免維數災難，提升EFLP的求解效率，并通過仿真對比試驗驗證方法的有效性.

1 模糊集理論

模糊集理論建立了自然語言與定量描述之間的橋梁和紐帶，是分析定性和定量之間相互轉化的認知模型，模糊集理論作為非概率性不確定性信息描述工具被廣泛應用于解決不確定性決策的相關問題[31].

1.1 模糊集定義

實際生活中的許多事件本身是無法采用精確定義來描述的.為了彌補確定性理論在描述事件復雜性和可能性上的不足，Zadeh[32]提出了模糊集(fuzzy set，FS)的概念.論域U上的FS可由其隸屬度函數定義，式(1)～(3)給出了A的3種常見表達形式[33]：

A={(x，μA(x))：?x∈U}

(1)

(2)

A={μA(x)：?x∈U}

(3)

1.2 模糊變量定義

假設Θ為一個非空集合，θ是Θ的冪集，Pos是可能性度量，R為一個表示模糊事件的實數集，(Θ，θ，Pos)為概率空間，則模糊變量(fuzzy variable，FV)可被定義為一個由概率空間到實數集的函數[34]：ξ：(Θ，θ，Pos)→R.如圖1(a)所示，ξ為一個由(a，b，c，d，w)，a

(4)

(a) 梯形模糊隸屬度函數

(b) 三角模糊隸屬度函數

1.3 置信度理論

對于任意模糊事件{ξ∈B}，B?R，其可能性度量Pos{ξ∈B}的計算方法如式(5)所示，其必要性度量Nec{ξ∈B}的計算方法如式(6)所示[35].

(5)

(6)

對于任意模糊事件{ξ∈B}，B?R，其置信度度量Cr{ξ∈B}的計算方法如下：

(7)

與可能性度量Pos{ξ∈B}和必要性度量Nec{ξ∈B}相比，置信度度量Cr{ξ∈B}具有自偶性.若Cr{ξ∈B}=1，則表示模糊事件{ξ∈B}，B?R必定會發生；若Cr{ξ∈B}=0，則表示模糊事件{ξ∈B}，B?R必定不會發生.

結合上述置信度度量方法與FV的定義，可將式(7)推廣至模糊變量的置信度度量方法.令ξ為一個由(a，b，c，d，w)，a

(8)

(9)

針對梯形模糊變量ξ=(a，b，c，d，w)，a

Cr{ξ≤x}≥α?

(10)

Cr{ξ>x}≥α?

(11)

1.4 二型模糊集理論

?φ∈Jx?[0，1]}

(12)

(13)

(14)

(15)

(16)

2 模型構建

2.1 區域網格化

為了減少計算負載和協調選址模型，采用相同大小的網格將整個區域劃分為如圖2所示笛卡兒坐標系(n×m)中的二維空間.示例點1和2可以分別用坐標(2，5)和(5，9)表示.如果每個網格的長度為100 m，則圖2中任意兩個網格之間的距離可以用它們的坐標表示如下：

(17)

其中dij為網格i到網格j之間的距離；x*和y*為網格*的坐標.

圖2 網格化的選址區域

2.2 選址集最大覆蓋模型

基于上述網格化的選址區域，綜合分析選址決策的人口因素和地理因素，建立一個選址集最大覆蓋模型.模型假設如下：

(1)選址區域內的所有網格都視為選址模型中的需求點.

(2)不可放置應急設施的網格是已知的.

(3)應急設施的覆蓋半徑無限制，但其應急能力會隨著應急距離的增加而降低[22].令i為設施放置點，j為需求點，dij為設施點i到需求點j的距離，k為衰減系數，則設施應急能力和應急距離之間的衰減關系可表示為e-kdij.

(4)每個被選中的應急設施放置點會被分配同樣數量和類型的應急設施.

(5)可建立的應急設施放置點個數為p.

模型的決策變量如下：

?i≤n×m

(18)

模型的優化目標如下：

(19)

優化目標最大化應急設施需求加權覆蓋程度，以區域人口密度量化每個需求點對應急資源的需求，在資源有限的情況下盡可能側重于滿足人口密度較高區域的應急需求，ρj為網格j處的人口密度.由于人口的流動性，將人口密度定義為一個梯形區間二型模糊變量，任意網格處的人口密度ρi由式(20)定義.

(20)

圖3 ρi的隸屬度函數示例

根據ρi的邊界隸屬度函數，采用置信度理論和機會約束規劃方法處理帶模糊參數的目標函數Z.

對于上層隸屬度函數，其機會約束規劃如下：

(21)

對于下層隸屬度函數，其機會約束規劃如下：

(22)

式(21)、(22)中，αu和αl為預定義的置信度水平，根據式(10)、(11)，模型等價約束如下：

(23)

綜上所述，原帶模糊參數的目標函數Z被轉化為其等價確定性目標函數(24)、(25).

(24)

(25)

最終，采用線性加權技術將目標函數Z重定義為

maxZr=(Zu+Zl)/2

(26)

選址集最大覆蓋模型的等價確定性模型如下：

(27)

3 模型求解

選址問題是一類典型的NP-hard問題，分支定界法、割平面法以及PILP等精確算法往往難以在可接受時間范圍內得到最優解.進化算法是一類基于種群智能的全局優化啟發式算法，此類算法魯棒性較高，適用性強，不要求目標函數可微或可導，在機器智能領域得到了廣泛的關注.

以進化算法為基礎的遺傳算法(genetic algorithm，GA)已經被廣泛應用于求解NP-hard問題.GA自初始種群Pset開始，然后對當前種群Pset執行進化操作，進化操作一般按照選擇、交叉以及變異3種算子順序執行[37].選擇算子從Pset中選擇適應度高的個體放入交配集；交叉算子每次從交配集隨機選取個體執行交叉操作產生新個體；在交叉操作的基礎上，引入變異操作可以有效避免算法早熟.重復上述進化操作直至產生預定規模的子代種群Rset.為避免丟失優質個體，以子代種群Rset和當前種群Pset的并集為聯合解集Uset.最終，判斷算法是否滿足停止迭代條件，若滿足，則輸出當前最優解；若不滿足，則根據精英策略更新下一代種群，并重復上述迭代過程.GA的迭代過程是最優解不斷逼近真實最優解的過程.

當采用GA解決特定問題時，從問題空間到編碼空間的映射稱為編碼.進化算法中，常見的編碼策略為二進制字符串、實數、序列編碼、隨機序列和樹編碼[8，38-39].然而，由于應急設施選址問題涉及的空間數據量和解空間龐大，上述編碼策略往往難以保證產生可行的子代種群，這對算法收斂性造成了極大的影響.為了提升算法性能，采用了一種基于網格空間表示法的矩陣編碼策略.如圖4所示，采用矩陣表示笛卡兒坐標系中的二維空間，結合二進制編碼的特點，將應急設施放置點對應的矩陣元素設置為1.矩陣編碼策略在保持了二進制編碼便于操作特點的同時，減少了問題維度的規模.

圖4 基于網格空間表示法的矩陣編碼策略示例

4 仿真算例

以30×30網格化選址區域為例進行方法驗證.可建立的應急設施放置點p=10.假設每個網格都可以放置應急設施，即不可放置應急設施的網格集B=?.通過一定次數的測試運行，將最大迭代次數設為200，種群規模設為100，交叉概率設為0.8，變異概率設為0.08.

4.1 算法性能分析

為了測試編碼策略的性能，將采用矩陣編碼得到的最優解與采用整數向量編碼[8]以及采用二進制編碼[1]得到的最優解進行比較.

所有算法都運行在一臺配置為Intel (R) Core (TM) i7-7700 CPU @ 3.60 GHz，32.0 GB RAM的計算機上，算例實現的軟件環境均為Matlab 2016a.由于進化算法的隨機性，在評估算法性能時，需要執行多次獨立運行.在不失一般性的前提下，進行10次獨立運行，從最優解的平均質量與最優質量兩個方面比較算法性能.

3種編碼策略最優收斂曲線如圖5所示，GA-A為采用整數向量編碼策略所得最優收斂曲線，GA-B為采用二進制編碼策略所得最優收斂曲線，GA-M為采用矩陣編碼策略所得最優收斂曲線.仿真結果表明，采用矩陣編碼與遺傳算法耦合進行模型求解時的收斂性最好，采用二進制編碼和整數向量編碼與遺傳算法耦合進行模型求解時陷入了局部最優解.表1比較3種編碼策略10次獨立運行后所得最優解目標函數值以及算法運行時間.矩陣編碼所得最優解的平均質量與最優質量是最好的，整數向量編碼次之，二進制編碼最差.由于高維復雜的空間地理數據以及龐大的解空間，二進制編碼會嚴重影響算法性能[40].通過進一步分析可以發現，二進制編碼與整數向量編碼的平均運行時間要遠比矩陣編碼的運行時間長.這表明所提出的矩陣編碼策略在保持了二進制編碼便于操作特點的同時，減少了問題維度的規模，可有效避免維數災難.

圖5 3種編碼策略最優收斂曲線(p=10)

表1 算法性能比較

4.2 敏感性分析

等價確定性模型中，目標函數會隨著預定義的置信度水平αu和αl而改變，同一個解在不同置信度水平α下的目標函數值是不同的.因此，以置信度水平為敏感參數進行敏感性分析.通過敏感性分析，驗證所得最優選址決策的可靠性.

(28)

(29)

圖6 不同置信度水平下最優決策目標函數值

在實際應用中，為了應急設施選址決策可靠性，預定義的置信度水平應該設置為0.5～1.0，即αu，αl∈[0.5，1.0].

5 結 語

本文研究了突發事件應急管理中的應急設施選址問題.在傳統選址集最大覆蓋模型的基礎上，充分考慮了選址決策的人口因素和地理因素，以區域人口密度量化應急資源需求程度.在模型求解時，設計了一種新穎的基于網格空間表示法的矩陣編碼策略.與其他常見編碼策略相比，所提出的矩陣編碼策略可以成功地與遺傳算法耦合，實現在全局范圍內快速地搜索最優解，有效避免維數災難，顯著提升了算法性能.最后，以置信度水平為敏感參數進行了敏感性分析.通過敏感性分析，驗證了所得最優選址決策的可靠性.所提算法不限于求解不確定條件下的EFLP，對于許多具有不確定屬性的決策問題也有一定的適用性.