基于備用覆蓋的多目標(biāo)公共設(shè)施選址問(wèn)題研究

1、基于備用覆蓋的多目標(biāo)公共設(shè)施選址問(wèn)題研究萬(wàn) 波1,2，楊 超1，黃 松1，董 鵬1(1. 華中科技大學(xué) 管理學(xué)院, 武漢 430074；2. 江漢大學(xué), 武漢 430056摘要： 關(guān)鍵詞：中圖分類(lèi)號(hào)：O22 文獻(xiàn)標(biāo)識(shí)碼：AWAN Bo, YANG Chao, HUANG Song, Dong Peng(1.School of Management, Huazhong University of Science & Technology, Wuhan 430074, China;2. Jianghan University, Wuhan 430056, ChinaAbstract : K

2、ey words:1 問(wèn)題背景有一類(lèi)公共服務(wù)設(shè)施稱為應(yīng)急型公共服務(wù)設(shè)施，該類(lèi)設(shè)施的作用在于對(duì)自然災(zāi)害、人為災(zāi)害等緊急事件(非常態(tài) 做出反應(yīng)并進(jìn)行處置。該類(lèi)設(shè)施主要有醫(yī)療急救中心(120報(bào)警 、消防(119報(bào)警 、公安(110報(bào)警和122報(bào)警 、電力、通信、道路交通等專(zhuān)業(yè)工程搶險(xiǎn)救援等設(shè)施。該類(lèi)設(shè)施的一個(gè)顯著的特征為“急”，即對(duì)時(shí)效性要求很高，當(dāng)突發(fā)事件發(fā)生時(shí)，需要調(diào)動(dòng)一系列公共服務(wù)設(shè)施來(lái)消除和減輕災(zāi)害或事故的影響，這要求更多地分散設(shè)置應(yīng)急服務(wù)設(shè)施，以便在應(yīng)急救援期間，可動(dòng)用更多的緊急救援資源。應(yīng)急服務(wù)設(shè)施通常處在三種狀態(tài)中：（1）在基站中待命；（2）服務(wù)中；（3）完成任務(wù)后回返中。服務(wù)設(shè)施可達(dá)

3、性是指服務(wù)設(shè)施不僅處在服務(wù)需求的覆蓋范圍內(nèi)，還須處在隨時(shí)可用狀態(tài)。在上述三種狀態(tài)中，第二種狀態(tài)顯然是不可用的狀態(tài)，也就是說(shuō)服務(wù)設(shè)施處在被“占用”狀態(tài)，這時(shí)，服務(wù)設(shè)施需要啟用額外的備用(Backup 覆蓋，以保證服務(wù)設(shè)施的可達(dá)性。在設(shè)計(jì)規(guī)劃應(yīng)急服務(wù)設(shè)施容量時(shí)，決策者必須充分考慮系統(tǒng)的復(fù)雜性，避免出現(xiàn)由于系統(tǒng)“擁擠”，需求區(qū)域看似全被覆蓋、實(shí)際上可能“失防”的現(xiàn)象。服務(wù)設(shè)施的可達(dá)性要求在需求觸發(fā)時(shí)，系統(tǒng)能夠提供數(shù)量充足的應(yīng)急型公共服務(wù)設(shè)施，并在規(guī)定時(shí)間內(nèi)到達(dá)現(xiàn)場(chǎng)，以滿足應(yīng)急服務(wù)需求。然而，由于受到資金約束，設(shè)施數(shù)目不可能無(wú)限制增加。挖掘系統(tǒng)內(nèi)部潛能，實(shí)行科學(xué)管理，盡可能地使設(shè)置的應(yīng)急服務(wù)設(shè)施具有備

4、用覆蓋，是提高系統(tǒng)的調(diào)度效率，解決應(yīng)急型公共服務(wù)設(shè)施時(shí)效性問(wèn)題的有效途徑。2 相關(guān)理論2.1 備用覆蓋當(dāng)城市應(yīng)急服務(wù)系統(tǒng)出現(xiàn)擁擠現(xiàn)象時(shí)，由于單一覆蓋不能保證服務(wù)設(shè)施提供及時(shí)的應(yīng)急響應(yīng)，通常需要附近的其他服務(wù)設(shè)施提供備用覆蓋(backup coverage ，保證在單一覆蓋設(shè)施不可達(dá)的情況下，備用覆蓋設(shè)施可及時(shí)予以頂替。備用覆蓋的概念見(jiàn)圖 收稿日期：2010-05-10基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(70871044作者簡(jiǎn)介：萬(wàn)波(1972-，男，湖北武漢人，博士研究生，主要研究方向：現(xiàn)代管理理論與方法，信息理論與信息系統(tǒng)。需求點(diǎn)i 在單一覆蓋情況下，由服務(wù)設(shè)施j 1提供專(zhuān)屬的應(yīng)急服務(wù)。當(dāng)i 點(diǎn)

5、產(chǎn)生服務(wù)需求時(shí)，如果j 1處在空閑狀態(tài)時(shí)，j 1可及時(shí)地提供響應(yīng)；如果j 1正處在忙碌狀態(tài)時(shí)，不能及時(shí)提供響應(yīng)。在備用覆蓋情況下，服務(wù)設(shè)施j 1和j 2都覆蓋需求點(diǎn)i ，在正常情況時(shí)，i 的服務(wù)需求由服務(wù)設(shè)施j 1提供響應(yīng)，當(dāng)j 1不能及時(shí)響應(yīng)時(shí)，由服務(wù)設(shè)施j 2做出應(yīng)急響應(yīng)(j 1為i 的首選設(shè)施，j 2為i 的備用設(shè)施 。顯然，需求點(diǎn)i 的備用覆蓋的應(yīng)急服務(wù)設(shè)施越多，其服務(wù)需求被及時(shí)響應(yīng)的可能性越大。（參考：陳志宗，城市防災(zāi)減災(zāi)設(shè)施選址模型與戰(zhàn)略決策方法研究）2.2 模糊目標(biāo)規(guī)劃選址問(wèn)題需要綜合考慮公平與效益等多種因素，是一項(xiàng)系統(tǒng)工程，因而也是一個(gè)多目標(biāo)決策問(wèn)題。目標(biāo)規(guī)劃GP （Goal

6、Programming）是一種非常有用的多目標(biāo)決策方法，已經(jīng)被廣泛地應(yīng)用于求解多個(gè)相互矛盾的目標(biāo)問(wèn)題。GP 方法最早是由Charnes3提出的，其思路為：首先確定各目標(biāo)的期望值，然后使得目標(biāo)值與目標(biāo)期望值之間的偏差最小化，從而求得最優(yōu)解。但是，GP 方法有一個(gè)局限性，那就是必須確定目標(biāo)的期望值。然而，在實(shí)際的多目標(biāo)規(guī)劃問(wèn)題中，目標(biāo)的期望值往往難以精確的確定。鑒于這種情況，模糊集理論4被引入到多目標(biāo)規(guī)劃問(wèn)題中來(lái)，產(chǎn)生了模糊目標(biāo)規(guī)劃FGP （Fuzzy Goal Programming ）方法5。FGP 只需要給出“模糊”的目標(biāo)期望值，也就是利用模糊集理論中的隸屬度的概念，構(gòu)造各目標(biāo)的隸屬度函數(shù)，

7、用隸屬度函數(shù)來(lái)描述各目標(biāo)與目標(biāo)期望值之間的接近程度。一個(gè)典型的模糊目標(biāo)規(guī)劃問(wèn)題描述如下：( , 1,2,., , m i m Z x Z m M = （1） ( , 1, 2,., , k i k Z x Z k M M K =+ （2） ( ,1,2,., , j i j g x b j J =（3）1,2., . i x i n =（4）公式（1）、（2）中的“ ”、與“ ”分別表示“約小于或等于”和“約大于或等于”，體現(xiàn)了“模糊”的含義，（1）式表示第m 個(gè)目標(biāo)的目標(biāo)值允許在m Z 的右邊一定范圍r m 內(nèi)波動(dòng)，即( , m i m m Z x l u ，這里u m 與l m 分別代表第

8、m 個(gè)目標(biāo)的上下界，即m m l Z =，m m m u Z r =+，（2）式表示第k 個(gè)目標(biāo)的目標(biāo)值允許在k Z 的左邊一定范圍p k 內(nèi)波動(dòng)，（3）式表示第j 個(gè)不等式約束，（4）式對(duì)決策變量進(jìn)行定義。對(duì)于“約小于或等于”和“約大于或等于”的目標(biāo)而言，線性隸屬度函數(shù)定義分別見(jiàn)（5）式與（6）式。1( ( ( 1( ( 0m m m m mz m m m m mm m if z x l z x l u x if l z x u u l if z x u -=-<->（5）1( ( ( 1( ( 0k k k k k z k k k k kk k if z x u u z x u

9、 x if l z x u u l if z x l >-=-<-（6）利用Belman 和Zadeh 的求解方法，可行的模糊解集可通過(guò)模糊目標(biāo)的隸屬度函數(shù)的交集獲得，即：1212( ( ( . ( min (, (,., ( . k k F Z Z Z Z Z Z u x u x u x u x u x u x u x = 對(duì)于模糊決策而言，最優(yōu)決策由隸屬度最大的值確定，即12max ( max min (, (,., ( . k F Z Z Z x Fx Fu x u x u x u x =Zimmermann 將輔助變量引入模糊目標(biāo)規(guī)劃，建立了經(jīng)典的FGP （FGP-C ）模

10、型：12max . ( , ( , ( , ( , 1, 2,., ,01, 2., ,01.k Z Z Z j i j i Z s t u x u x u x g x b j J x i n =該方法雖然將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題，便于求解。但該模型無(wú)法反映各目標(biāo)之間的重要程度，Tiwari 等給出了加權(quán)的FGP （FGP-W ），k w 表示第k 個(gè)目標(biāo)的權(quán)重，模型如下：1max . ( , 1,., , ( , 1, 2,., , 01, 2,., ,01, 1,., .k mk kk Z k j i j i k Z w s tu x k m g x b j J x i n k m =

11、Chen 和Tsai 給出了帶優(yōu)先級(jí)的FGP 模型。設(shè)有4個(gè)目標(biāo)，其優(yōu)先級(jí)分別為：134332, , ，則帶優(yōu)先級(jí)的FGP （FGP-P ）模型如下：41134332max . ( , 1, , 4, ( , 1, 2,., , , ,1, 2., ,01, 1, , 4.k kk Z k j i j i k Z s tu x k g x b j J x i n k =3 模型建立與求解算法3.1 符號(hào)含義本文需要用到的有關(guān)符號(hào)定義如下： I ： 需求點(diǎn)的集合，|1, I i n = ；J ： 設(shè)施候選點(diǎn)的集合，|1, J j k = ； R ： 覆蓋半徑；C ： 設(shè)施的臺(tái)套數(shù)目約束； w i

12、 ： 需求點(diǎn)i 的需求量；k j ： 定位于j 點(diǎn)的單個(gè)設(shè)施的服務(wù)容量； d ij ： 需求點(diǎn)i 到設(shè)施點(diǎn)j 的距離；a ij ： 如果, 1ij ij d R a =則；0ij a =否則； e ij ： 如果, 1ij ij d R e >=則；0ij e =否則； F i ： 如果需求點(diǎn)i 被覆蓋一次，則F i =1；否則F i =0； S i ： 需求點(diǎn)i 被至少覆蓋兩次的人口份額；M ： 一個(gè)足夠大的正數(shù)。 同時(shí)定義如下的決策變量：z ij ： 源于需求點(diǎn)i 的需求分配給j 點(diǎn)的份額；y j ： 服務(wù)設(shè)施定位于j 點(diǎn)，則y j =1；否則y j =0； x j ： 服務(wù)設(shè)施定位

13、于j 點(diǎn)的臺(tái)套數(shù)。 3.2 基于備用覆蓋的多目標(biāo)公共設(shè)施選址模型(MPFLMBC本文提出了一個(gè)基于備用覆蓋的多目標(biāo)公共服務(wù)設(shè)施選址模型。該模型考慮以下三個(gè)目標(biāo)：一是從傳統(tǒng)的最大覆蓋角度出發(fā)，尋求一次覆蓋的人口最大化；二是從備用覆蓋的角度出發(fā)，要求最大化至少兩次覆蓋的人口數(shù)；三是從非覆蓋范圍內(nèi)的設(shè)施調(diào)試效率角度出發(fā)，要求在選址點(diǎn)與需求點(diǎn)超過(guò)覆蓋距離的情況下，實(shí)現(xiàn)系統(tǒng)總的旅行距離之和最小化。模型考慮了設(shè)施點(diǎn)的服務(wù)能力，系統(tǒng)成本約束等條件。模型如下：max i i iw F (1max i i iw S (2 min ij i ij ij ije w d z (3Subject to ：0, , i

14、ji i jaF S i I -(4 , , i i S F i I (5 1, , ij jz i I (6 , , j j x My j J (7 , , j j y x j J (8 , , i ijj jiw z k x j J (9 , j jy B (10 , jjxC (11 0,1, , i F i I (12 0,1, i S i I (13 0,1, , ij z i I j J (140, , . j j x x Z j J (15其中，(1式表示最大化至少覆蓋一次的人口數(shù)；(2式表示最大化備用覆蓋的人口數(shù)，即至少覆蓋兩次的人口數(shù)；(3式表示當(dāng)選址點(diǎn)與需求點(diǎn)超過(guò)覆蓋距離的

15、情況下，最小化非覆蓋范圍內(nèi)的旅行距離；(4式確定需求點(diǎn)覆蓋距離之內(nèi)的設(shè)施數(shù)目；(5式表示當(dāng)且僅當(dāng)首次覆蓋存在的情況下才可能有備用覆蓋；(6式表示每一個(gè)需求點(diǎn)的需求均得以分配；(7式表示當(dāng)服務(wù)設(shè)施未選址于j 點(diǎn)時(shí)，其設(shè)施臺(tái)數(shù)為零；(8式表示設(shè)施臺(tái)數(shù)為零時(shí)，服務(wù)設(shè)施不會(huì)選址于j 點(diǎn)；(9式表示分配給一個(gè)設(shè)施點(diǎn)的總?cè)丝跀?shù)不超過(guò)該點(diǎn)所有設(shè)施的服務(wù)容量；(10式表示設(shè)施點(diǎn)的數(shù)目約束；(11式表示設(shè)施的臺(tái)套數(shù)目約束；(12式定義了中間變量Y i ；（13）式定義了中間變量U i ，表示需求點(diǎn)i 被至少覆蓋兩次的人口份額不一定要求為整數(shù)，說(shuō)明模型允許第二次覆蓋為部分覆蓋；(14式、（15）式定義了決策變量。

16、 3.3求解算法本文利用模糊目標(biāo)規(guī)劃（FGP ）的方法對(duì)基于備用覆蓋的多目標(biāo)公共設(shè)施選址模型(MPFLMBC進(jìn)行求解。以加權(quán)的FGP （FGP-W ）為例，將求解算法分成兩個(gè)部分。第一步求隸屬度函數(shù)，方法為對(duì)每個(gè)目標(biāo)分別利用Lingo 軟件求出其上下界，即可得每個(gè)目標(biāo)的隸屬度函數(shù)。第二步將多目標(biāo)問(wèn)題利用FGP W 方法轉(zhuǎn)化為單目標(biāo)模型，然后利用Lingo 軟件求解。Step1 求隸屬度函數(shù)。（1）求第一個(gè)目標(biāo)的上限1u 與下限1l 。將MPFLMBC 中的（2）、（3）式去掉，利用Lingo 軟件求解單目標(biāo)模型，獲得1u 。將（1）式用min i iiwY 替換，同樣利用Lingo 軟件求解，

17、可獲得1l 。（2）將1u 與1l 代入（5）式可得第一個(gè)目標(biāo)的隸屬度函數(shù)1( z u x 。同理，可得到第二、三個(gè)目標(biāo)的隸屬度函數(shù)2( z u x 、3( z u x 。Step2 利用FGP W ，求解基于備用覆蓋的多目標(biāo)公共設(shè)施選址模型。將1( z u x 、2( z u x 、3( z u x 作為約束條件加入FGP W 模型中，并將MPFLMBC 模型中的（4）-（12）式代入，可得如下模型，并用Lingo 軟件求解。31max . ( , 1,.,3, (4(12,01, 2,., , 01, 1,., .k k kk Z k i k Z w s tu x k x i n k m

18、=-= 利用2.3節(jié)所提供的FGP C ，F(xiàn)GP P ，運(yùn)用Lingo 軟件同樣可求得相應(yīng)的解。4 實(shí)例分析本文以武漢市某區(qū)急救中心選址為例，根據(jù)該區(qū)的人口分布情況進(jìn)行聚類(lèi)，可將居民點(diǎn)聚類(lèi)成50個(gè)需求點(diǎn)，即I =i 1， i 2，i 50，設(shè)施候選點(diǎn)的集合與居民點(diǎn)集合相同，即J=I=i 1， i 2，i 50。設(shè)需要建立100臺(tái)急救服務(wù)設(shè)施，每臺(tái)急救設(shè)備的服務(wù)容量k j 為1000人。w i 為50個(gè)居民區(qū)的需求人口數(shù)。因d ij 、w i 數(shù)據(jù)量大，在此不一一列出。設(shè)覆蓋半徑R=2.5km ，M=100。本文利用Lingo11軟件，先求出每個(gè)目標(biāo)的上下界：11, 108,7249u l =，

19、22, 0,4670u l =，33, 16986,185087958u l =分別使用FGP W ，F(xiàn)GP C ，F(xiàn)GP P 方法對(duì)模型進(jìn)行求解，并與傳統(tǒng)的多目標(biāo)求解方法線性加權(quán)法WLM （Weighted Linear Method）進(jìn)行比較，結(jié)果如表1所示。表1 各種求解方法所得結(jié)果 求解方法 選址點(diǎn) 首次覆蓋的人口及比例 備用覆蓋的人口及比例 旅行距離CPU 運(yùn)行時(shí)間(秒WLM 26,36,39,46,48 6244(78.26% 3114(39.03% 184005697.6 4FGP-W 5,6,15,22,24,26,37,38,39,46 6489(81.44% 3648(45

20、.72% 158708789.5 8FGP-C 6,7,15,22,24,26,27,38,39,46 6010(75.33% 4242(53.16% 128464439.2 7FGP-P 5,6,16,22,26,27,36,38,39,466183(77.49% 3960(49.63% 129041598.4 4注：WLM 與FGP-W 求解方法中的1230.6, 0.3, 0.1w w w =將四種方法的求解結(jié)果的三個(gè)目標(biāo)值分別進(jìn)行比較，結(jié)果如圖2、圖3所示。7000 6000 5000 4000 3000 2000 首次覆蓋的人口 備用覆蓋的人口 180000000 160000000

21、 140000000 120000000 100000000 旅行距離 80000000 60000000 40000000 1000 0 FGP-W FGP-C FGP-P 20000000 0 FGP-W FGP-C FGP-P 圖2 FGP 各種求解方法的目標(biāo) 1 及目標(biāo) 2 結(jié)果比較 圖 3 FGP 各種求解方法的目標(biāo) 3 結(jié)果比較 由表 1，在相同的權(quán)重下，將 FGP-W 與 WLM 進(jìn)行比較，可知首次覆蓋的人口比例為 81.44%，高于 WLM 的 78.26%；備用覆蓋的人口比例為 45.72%，高于 WLM 的 39.03%；旅行距離為 158708789.5，低于 WLM 的

22、 184005697.6。因此，F(xiàn)GP-W 的三個(gè)目標(biāo)值均優(yōu)于 WLM。原因在于模糊目標(biāo)規(guī)劃對(duì)目標(biāo)的上下界 進(jìn)行了限定，雖然是“模糊”的，但更切合實(shí)際情況，可在其各自調(diào)整的范圍內(nèi)自己進(jìn)行優(yōu)化，達(dá)到較好 的求解質(zhì)量。但從 CPU 運(yùn)行時(shí)間來(lái)看，F(xiàn)GP-W 為 8 秒，而 WLM 僅為 4 秒。因此，需要消耗 CPU 的運(yùn)行 時(shí)間， 從而獲得較好的求解質(zhì)量。 在計(jì)算機(jī)資源日益豐富的今天， 模糊目標(biāo)規(guī)劃與傳統(tǒng)的線性加權(quán)法相比， 顯示出明顯的優(yōu)勢(shì)，其求解質(zhì)量明顯提高。 由圖 2 可知，在 FGP-W 與 FGP-C、FGP-P 所求得第一目標(biāo)值結(jié)果中，F(xiàn)GP-W 的結(jié)果是最好的。原因 為 FGP-W 定義了第一目標(biāo)的權(quán)重 w1 = 0.6, 明顯高于 w2 , w3 ；FGP-P 的求解結(jié)果次之，因?yàn)?FGP-P 雖然定 義了三個(gè)目標(biāo)的優(yōu)先級(jí)，但其沒(méi)有賦予第一目標(biāo)較大的權(quán)重；而 FGP-C 根本沒(méi)有給出第一目標(biāo)的權(quán)重，故 其結(jié)果是最差的。由圖 2、圖 3 可知，在 FGP 各種方法所求得的第二目標(biāo)值、第三目標(biāo)值結(jié)果中，F(xiàn)GP-C 的結(jié)果是最好的，它是對(duì)第一目標(biāo)較差