基于二型模糊集理論的應(yīng)急設(shè)施選址方法

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

( 1.臺(tái)州學(xué)院 電子與信息工程學(xué)院(大數(shù)據(jù)學(xué)院)， 浙江 臺(tái)州 318000；2.杭州電子科技大學(xué) 自動(dòng)化學(xué)院， 浙江 杭州 310000；3.浙江中天氟硅材料有限公司， 浙江 衢州 324000；4.衢州市特種設(shè)備檢驗(yàn)中心， 浙江 衢州 324000；5.杭州市西湖區(qū)保障性住房管理服務(wù)中心， 浙江 杭州 310000 )

0 引 言

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

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

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

鑒于EFLP的地理性質(zhì)，大多數(shù)研究將時(shí)間和距離視為應(yīng)急設(shè)施選址決策的關(guān)鍵因素.目標(biāo)函數(shù)通常側(cè)重于滿足預(yù)定義的受災(zāi)地點(diǎn)(需求點(diǎn)).傳統(tǒng)的空間優(yōu)化模型[5，25-29]通常并不會(huì)對(duì)這些預(yù)定義的需求點(diǎn)加以區(qū)分.然而，不同需求點(diǎn)對(duì)應(yīng)急資源的需求程度往往與區(qū)域內(nèi)人口密度密切相關(guān)[30].選址準(zhǔn)則不僅應(yīng)考慮應(yīng)急設(shè)施的空間特征，還應(yīng)考慮選址區(qū)域內(nèi)的人口分布.此外，由于人口的流動(dòng)性，實(shí)際應(yīng)用中通常難以獲得精確的人口密度數(shù)據(jù).在確定性環(huán)境下所得的應(yīng)急設(shè)施選址決策可能難以滿足突發(fā)事件風(fēng)險(xiǎn)管理的實(shí)際需求.

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

1 模糊集理論

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

1.1 模糊集定義

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

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

(1)

(2)

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

(3)

1.2 模糊變量定義

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

(4)

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

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

1.3 置信度理論

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

(5)

(6)

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

(7)

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

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

(8)

(9)

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

Cr{ξ≤x}≥α?

(10)

Cr{ξ>x}≥α?

(11)

1.4 二型模糊集理論

?φ∈Jx?[0，1]}

(12)

(13)

(14)

(15)

(16)

2 模型構(gòu)建

2.1 區(qū)域網(wǎng)格化

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

(17)

其中dij為網(wǎng)格i到網(wǎng)格j之間的距離；x*和y*為網(wǎng)格*的坐標(biāo).

圖2 網(wǎng)格化的選址區(qū)域

2.2 選址集最大覆蓋模型

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

(1)選址區(qū)域內(nèi)的所有網(wǎng)格都視為選址模型中的需求點(diǎn).

(2)不可放置應(yīng)急設(shè)施的網(wǎng)格是已知的.

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

(4)每個(gè)被選中的應(yīng)急設(shè)施放置點(diǎn)會(huì)被分配同樣數(shù)量和類型的應(yīng)急設(shè)施.

(5)可建立的應(yīng)急設(shè)施放置點(diǎn)個(gè)數(shù)為p.

模型的決策變量如下：

?i≤n×m

(18)

模型的優(yōu)化目標(biāo)如下：

(19)

優(yōu)化目標(biāo)最大化應(yīng)急設(shè)施需求加權(quán)覆蓋程度，以區(qū)域人口密度量化每個(gè)需求點(diǎn)對(duì)應(yīng)急資源的需求，在資源有限的情況下盡可能側(cè)重于滿足人口密度較高區(qū)域的應(yīng)急需求，ρj為網(wǎng)格j處的人口密度.由于人口的流動(dòng)性，將人口密度定義為一個(gè)梯形區(qū)間二型模糊變量，任意網(wǎng)格處的人口密度ρi由式(20)定義.

(20)

圖3 ρi的隸屬度函數(shù)示例

根據(jù)ρi的邊界隸屬度函數(shù)，采用置信度理論和機(jī)會(huì)約束規(guī)劃方法處理帶模糊參數(shù)的目標(biāo)函數(shù)Z.

對(duì)于上層隸屬度函數(shù)，其機(jī)會(huì)約束規(guī)劃如下：

(21)

對(duì)于下層隸屬度函數(shù)，其機(jī)會(huì)約束規(guī)劃如下：

(22)

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

(23)

綜上所述，原帶模糊參數(shù)的目標(biāo)函數(shù)Z被轉(zhuǎn)化為其等價(jià)確定性目標(biāo)函數(shù)(24)、(25).

(24)

(25)

最終，采用線性加權(quán)技術(shù)將目標(biāo)函數(shù)Z重定義為

maxZr=(Zu+Zl)/2

(26)

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

(27)

3 模型求解

選址問題是一類典型的NP-hard問題，分支定界法、割平面法以及PILP等精確算法往往難以在可接受時(shí)間范圍內(nèi)得到最優(yōu)解.進(jìn)化算法是一類基于種群智能的全局優(yōu)化啟發(fā)式算法，此類算法魯棒性較高，適用性強(qiáng)，不要求目標(biāo)函數(shù)可微或可導(dǎo)，在機(jī)器智能領(lǐng)域得到了廣泛的關(guān)注.

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

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

圖4 基于網(wǎng)格空間表示法的矩陣編碼策略示例

4 仿真算例

以30×30網(wǎng)格化選址區(qū)域?yàn)槔M(jìn)行方法驗(yàn)證.可建立的應(yīng)急設(shè)施放置點(diǎn)p=10.假設(shè)每個(gè)網(wǎng)格都可以放置應(yīng)急設(shè)施，即不可放置應(yīng)急設(shè)施的網(wǎng)格集B=?.通過一定次數(shù)的測(cè)試運(yùn)行，將最大迭代次數(shù)設(shè)為200，種群規(guī)模設(shè)為100，交叉概率設(shè)為0.8，變異概率設(shè)為0.08.

4.1 算法性能分析

為了測(cè)試編碼策略的性能，將采用矩陣編碼得到的最優(yōu)解與采用整數(shù)向量編碼[8]以及采用二進(jìn)制編碼[1]得到的最優(yōu)解進(jìn)行比較.

所有算法都運(yùn)行在一臺(tái)配置為Intel (R) Core (TM) i7-7700 CPU @ 3.60 GHz，32.0 GB RAM的計(jì)算機(jī)上，算例實(shí)現(xiàn)的軟件環(huán)境均為Matlab 2016a.由于進(jìn)化算法的隨機(jī)性，在評(píng)估算法性能時(shí)，需要執(zhí)行多次獨(dú)立運(yùn)行.在不失一般性的前提下，進(jìn)行10次獨(dú)立運(yùn)行，從最優(yōu)解的平均質(zhì)量與最優(yōu)質(zhì)量?jī)蓚€(gè)方面比較算法性能.

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

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

表1 算法性能比較

4.2 敏感性分析

等價(jià)確定性模型中，目標(biāo)函數(shù)會(huì)隨著預(yù)定義的置信度水平αu和αl而改變，同一個(gè)解在不同置信度水平α下的目標(biāo)函數(shù)值是不同的.因此，以置信度水平為敏感參數(shù)進(jìn)行敏感性分析.通過敏感性分析，驗(yàn)證所得最優(yōu)選址決策的可靠性.

(28)

(29)

圖6 不同置信度水平下最優(yōu)決策目標(biāo)函數(shù)值

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

5 結(jié) 語(yǔ)

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