1、基于備用覆蓋的多目標公共設施選址問題研究萬 波1,2，楊 超1，黃 松1，董 鵬1(1. 華中科技大學 管理學院, 武漢 430074；2. 江漢大學, 武漢 430056摘要： 關鍵詞：中圖分類號：O22 文獻標識碼：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 問題背景有一類公共服務設施稱為應急型公共服務設施，該類設施的作用在于對自然災害、人為災害等緊急事件(非常態 做出反應并進行處置。該類設施主要有醫療急救中心(120報警 、消防(119報警 、公安(110報警和122報警 、電力、通信、道路交通等專業工程搶險救援等設施。該類設施的一個顯著的特征為“急”，即對時效性要求很高，當突發事件發生時，需要調動一系列公共服務設施來消除和減輕災害或事故的影響，這要求更多地分散設置應急服務設施，以便在應急救援期間，可動用更多的緊急救援資源。應急服務設施通常處在三種狀態中：（1）在基站中待命；（2）服務中；（3）完成任務后回返中。服務設施可達

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

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

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

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

7、用隸屬度函數來描述各目標與目標期望值之間的接近程度。一個典型的模糊目標規劃問題描述如下：( , 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）中的“ ”、與“ ”分別表示“約小于或等于”和“約大于或等于”，體現了“模糊”的含義，（1）式表示第m 個目標的目標值允許在m Z 的右邊一定范圍r m 內波動，即( , m i m m Z x l u ，這里u m 與l m 分別代表第

8、m 個目標的上下界，即m m l Z =，m m m u Z r =+，（2）式表示第k 個目標的目標值允許在k Z 的左邊一定范圍p k 內波動，（3）式表示第j 個不等式約束，（4）式對決策變量進行定義。對于“約小于或等于”和“約大于或等于”的目標而言，線性隸屬度函數定義分別見（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 的求解方法，可行的模糊解集可通過模糊目標的隸屬度函數的交集獲得，即：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 = 對于模糊決策而言，最優決策由隸屬度最大的值確定，即12max ( max min (, (,., ( . k F Z Z Z x Fx Fu x u x u x u x =Zimmermann 將輔助變量引入模糊目標規劃，建立了經典的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 =該方法雖然將多目標問題轉化為單目標問題，便于求解。但該模型無法反映各目標之間的重要程度，Tiwari 等給出了加權的FGP （FGP-W ），k w 表示第k 個目標的權重，模型如下：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 給出了帶優先級的FGP 模型。設有4個目標，其優先級分別為：134332, , ，則帶優先級的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 符號含義本文需要用到的有關符號定義如下： I ： 需求點的集合，|1, I i n = ；J ： 設施候選點的集合，|1, J j k = ； R ： 覆蓋半徑；C ： 設施的臺套數目約束； w i

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

13、于j 點的臺套數。 3.2 基于備用覆蓋的多目標公共設施選址模型(MPFLMBC本文提出了一個基于備用覆蓋的多目標公共服務設施選址模型。該模型考慮以下三個目標：一是從傳統的最大覆蓋角度出發，尋求一次覆蓋的人口最大化；二是從備用覆蓋的角度出發，要求最大化至少兩次覆蓋的人口數；三是從非覆蓋范圍內的設施調試效率角度出發，要求在選址點與需求點超過覆蓋距離的情況下，實現系統總的旅行距離之和最小化。模型考慮了設施點的服務能力，系統成本約束等條件。模型如下：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式表示最大化至少覆蓋一次的人口數；(2式表示最大化備用覆蓋的人口數，即至少覆蓋兩次的人口數；(3式表示當選址點與需求點超過覆蓋距離的

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

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

17、可獲得1l 。（2）將1u 與1l 代入（5）式可得第一個目標的隸屬度函數1( z u x 。同理，可得到第二、三個目標的隸屬度函數2( z u x 、3( z u x 。Step2 利用FGP W ，求解基于備用覆蓋的多目標公共設施選址模型。將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節所提供的FGP C ，FGP P ，運用Lingo 軟件同樣可求得相應的解。4 實例分析本文以武漢市某區急救中心選址為例，根據該區的人口分布情況進行聚類，可將居民點聚類成50個需求點，即I =i 1， i 2，i 50，設施候選點的集合與居民點集合相同，即J=I=i 1， i 2，i 50。設需要建立100臺急救服務設施，每臺急救設備的服務容量k j 為1000人。w i 為50個居民區的需求人口數。因d ij 、w i 數據量大，在此不一一列出。設覆蓋半徑R=2.5km ，M=100。本文利用Lingo11軟件，先求出每個目標的上下界：11, 108,7249u l =，

19、22, 0,4670u l =，33, 16986,185087958u l =分別使用FGP W ，FGP C ，FGP P 方法對模型進行求解，并與傳統的多目標求解方法線性加權法WLM （Weighted Linear Method）進行比較，結果如表1所示。表1 各種求解方法所得結果 求解方法 選址點 首次覆蓋的人口及比例 備用覆蓋的人口及比例 旅行距離CPU 運行時間(秒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 =將四種方法的求解結果的三個目標值分別進行比較，結果如圖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 各種求解方法的目標 1 及目標 2 結果比較 圖 3 FGP 各種求解方法的目標 3 結果比較 由表 1，在相同的權重下，將 FGP-W 與 WLM 進行比較，可知首次覆蓋的人口比例為 81.44%，高于 WLM 的 78.26%；備用覆蓋的人口比例為 45.72%，高于 WLM 的 39.03%；旅行距離為 158708789.5，低于 WLM 的

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