福建省加權(quán)網(wǎng)絡(luò)應(yīng)急物資儲備點(diǎn)選址

張翰祥，鄧麗娟 （集美大學(xué) 航海學(xué)院，福建 廈門361021）

ZHANG Han-xiang, DENG Li-juan (Navigation Institute, Jimei University, Xiamen 361021, China)

福建省作為海峽西岸經(jīng)濟(jì)區(qū)的主體，位于中國東南沿海。福建省特殊的地理位置既給了它快速發(fā)展的優(yōu)勢，同樣因地處我國東南沿海，成為洪、澇、風(fēng)、暴潮災(zāi)害較為嚴(yán)重的省份。嚴(yán)重的自然災(zāi)害在很大程度上制約著八閩地區(qū)的發(fā)展速度。自然災(zāi)害是難以避免的，因此在自然災(zāi)害發(fā)生前，如何通過科學(xué)的方法做好應(yīng)急物資準(zhǔn)備工作，對保障災(zāi)區(qū)的物資需求、縮短災(zāi)害響應(yīng)時(shí)間、及時(shí)有效救援、最大限度地減少生命財(cái)產(chǎn)損失，具有十分重要的現(xiàn)實(shí)意義。而目前，我國針對突發(fā)性自然災(zāi)害的應(yīng)急物資儲備的研究尚屬起步，因此對突發(fā)性自然災(zāi)害應(yīng)急物資儲備進(jìn)行探討及研究刻不容緩。

應(yīng)急物資儲備點(diǎn)選址是應(yīng)急管理中的非常關(guān)鍵的一環(huán)，它直接關(guān)系到資源高效調(diào)度和應(yīng)急方案實(shí)施的成敗。應(yīng)急物資儲備點(diǎn)選址問題，主要是研究如何通過合理安排有限的應(yīng)急資源，及時(shí)有效地進(jìn)行應(yīng)急救援行動，盡可能地減少事故所造成的人員傷亡和財(cái)產(chǎn)損失。

關(guān)于研究應(yīng)急物資儲備點(diǎn)選址問題，國內(nèi)外已有許多學(xué)者從不同的角度運(yùn)用不同的方法進(jìn)行了探討，如Ball 和Lin、List等站在系統(tǒng)穩(wěn)定性的角度研究了應(yīng)急物資儲備點(diǎn)最優(yōu)化的問題[1-2]。國內(nèi)方面，常玉林（2000） 等提出了應(yīng)急服務(wù)設(shè)施選址的模型[3]。方磊（2004） 提出了基于費(fèi)用最小的數(shù)學(xué)模型[4]。韓強(qiáng)（2007） 等提出了時(shí)間最短，費(fèi)用最小的模擬退火算法模型[5]。龍文（2008） 給出一種多目標(biāo)城市應(yīng)急設(shè)施選址問題的多目標(biāo)免疫算法模型[6]。郭子雪（2009） 等致力于研究基于梯形模糊數(shù)的應(yīng)急物資儲備庫最小加權(quán)距離選址模型[7]。李棟學(xué)（2009） 等引入帶精英策略的非支配排序遺傳算法解決應(yīng)急儲備庫選址研究中的多目標(biāo)優(yōu)化[8]。劉浪（2011） 運(yùn)用二次分層法的思想，通過集合覆蓋理論研究了無權(quán)網(wǎng)絡(luò)與有權(quán)網(wǎng)絡(luò)中的應(yīng)急物資儲備點(diǎn)選址問題[9]。

1 加權(quán)網(wǎng)絡(luò)應(yīng)急物資儲備點(diǎn)選址方法

應(yīng)急儲備點(diǎn)的選址問題實(shí)際上是一種點(diǎn)覆蓋類型問題，本文利用圖論的方法，在證明無權(quán)網(wǎng)絡(luò)中點(diǎn)對邊覆蓋問題也是整數(shù)規(guī)劃問題的基礎(chǔ)上，以物流運(yùn)輸時(shí)間作為應(yīng)急物流網(wǎng)絡(luò)的權(quán)重來構(gòu)建應(yīng)急物流網(wǎng)絡(luò)的加權(quán)拓?fù)浣Y(jié)構(gòu)，對加權(quán)網(wǎng)絡(luò)中的應(yīng)急物資儲備點(diǎn)選址問題進(jìn)行研究。

1.1 儲備點(diǎn)選址

應(yīng)急物資儲備點(diǎn)選址問題是假設(shè)在現(xiàn)有的網(wǎng)絡(luò)頂點(diǎn)所在地作為物資儲備點(diǎn)的備選點(diǎn)，以網(wǎng)絡(luò)的邊和點(diǎn)作為應(yīng)急的對象，建立網(wǎng)絡(luò)模型。

1.2 加權(quán)網(wǎng)絡(luò)

運(yùn)用圖論的方法，將網(wǎng)絡(luò)模型轉(zhuǎn)化為二部分圖，進(jìn)而轉(zhuǎn)化為0-1 整數(shù)規(guī)劃問題。具體的方法是將網(wǎng)絡(luò)模型中的邊抽象成點(diǎn)，原來網(wǎng)絡(luò)模型中的點(diǎn)依然是點(diǎn)，將原網(wǎng)絡(luò)模型中的點(diǎn)與邊有連接關(guān)系的關(guān)系抽象成點(diǎn)，將點(diǎn)對邊的覆蓋轉(zhuǎn)化為點(diǎn)對點(diǎn)的覆蓋。如圖1 所示無權(quán)網(wǎng)絡(luò)可以將其轉(zhuǎn)化成圖2 所示的二部分圖。

集合覆蓋要求選出的儲備點(diǎn)滿足以下整數(shù)規(guī)劃公式：

式中：A為二部分圖化為0-1 整數(shù)規(guī)劃后的關(guān)聯(lián)矩陣，它是以頂點(diǎn)集合V中的點(diǎn)為行，邊集合E中的點(diǎn)為列，V、E中的點(diǎn)有連接關(guān)系的用1 表示，無連接關(guān)系的用0 表示而構(gòu)成的；表示任意1 個(gè)應(yīng)急對象至少有1 個(gè)儲備點(diǎn)能覆蓋到它。

對圖2 利用編程求解可得，當(dāng)選擇的頂點(diǎn)數(shù)目不小于2 個(gè)時(shí)，可以完成對點(diǎn)和邊的完全覆蓋。

1.3 加權(quán)網(wǎng)絡(luò)應(yīng)急物資儲備點(diǎn)選址

例如在圖2 中設(shè)E1=1h，E2=2h，E3=3h。則優(yōu)化目標(biāo)是從上面得到的解集中找到遍歷應(yīng)急系統(tǒng)所有線路所花時(shí)間最少的方案，讓選出的儲備點(diǎn)沒有盲點(diǎn)，且應(yīng)急時(shí)間最短，應(yīng)選擇V1和V2作為應(yīng)急物資儲備點(diǎn)，最短遍歷時(shí)間為

圖3 福建省市級拓?fù)鋱D

2 應(yīng)急物資儲備點(diǎn)選址的應(yīng)用

2.1 福建省拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)的構(gòu)建

因福建省交通運(yùn)輸主要依靠公路，且即使在重大臺風(fēng)災(zāi)害下，高速公路不會受到過大影響。因此，用各個(gè)市中心高速公路運(yùn)輸時(shí)間作為各邊的權(quán)重更加符合福建省實(shí)際情況。令頂點(diǎn)集合（分別代表寧德，南平，福州，三明，莆田，龍巖，泉州，漳州，廈門的市中心），邊集合E=｛E1,E2,…,E13｝（分別代表各個(gè)市中心之間高速公路的運(yùn)輸時(shí)間，單位：min），建立拓?fù)淠Ｐ汀Ｆ渲?，E1=272，E2=89，E3=116，E4=227，E5=104，E6=231，E7=248，E8=187，E9=85，E10=95，E11=118，E12=112，E13=91。如圖3 所示。

2.2 應(yīng)用集合覆蓋

將點(diǎn)對點(diǎn)和點(diǎn)對邊的集合覆蓋，抽象成為單一的點(diǎn)對點(diǎn)的集合覆蓋，將其轉(zhuǎn)化為二部分圖。要找出元素最少的點(diǎn)集P，使得點(diǎn)集P中的點(diǎn)可以覆蓋頂點(diǎn)集V和邊集E的所有元素，如圖4 所示。

圖4 無權(quán)網(wǎng)絡(luò)二部分圖

這樣點(diǎn)對邊覆蓋問題就轉(zhuǎn)化成了0-1 整數(shù)規(guī)劃問題，需要滿足條件：

可以利用計(jì)算機(jī)循環(huán)程序從選擇所有頂點(diǎn)，依次遞減頂點(diǎn)數(shù)目，看是否滿足條件。當(dāng)點(diǎn)集P有不少于5 個(gè)元素時(shí)可以滿足覆蓋條件。但是，當(dāng)點(diǎn)集P有5 個(gè)元素時(shí)，總共有600 種方案，例如第51 種方案圖，見圖5 所示。因此必須對這些方案進(jìn)一步優(yōu)化取舍。

2.3 篩選應(yīng)急物資儲備點(diǎn)最優(yōu)選址方案

根據(jù)“災(zāi)害發(fā)生時(shí)，以最短的時(shí)間運(yùn)輸救災(zāi)物資”的原則，對滿足條件的集合P進(jìn)行優(yōu)化。優(yōu)化目標(biāo)是從所有點(diǎn)集P中找到這樣一個(gè)點(diǎn)集B，使得點(diǎn)集B中所有頂點(diǎn)元素覆蓋的邊權(quán)重和最小。根據(jù)以上思路，利用計(jì)算機(jī)循環(huán)程序進(jìn)行運(yùn)算求解，可以進(jìn)一步得出所有點(diǎn)集P的權(quán)重和，然后找出權(quán)重最小的方案。

最符合優(yōu)化條件的為第52 種方案，如圖6 所示。

圖5 應(yīng)急物資儲備點(diǎn)選址圖（方案51）

圖6 應(yīng)急物資儲備點(diǎn)最優(yōu)選址方案最優(yōu)方案

綜上所述，應(yīng)該選取 ｛南平，福州，泉州，龍巖，廈門 ｝作為應(yīng)急物資儲備點(diǎn)，最小遍歷運(yùn)輸時(shí)間為2 182 分鐘。

3 結(jié) 論

本文將應(yīng)急物資無權(quán)網(wǎng)絡(luò)選址問題的覆蓋問題轉(zhuǎn)化為圖論中的二部分圖問題，并且以遍歷應(yīng)急系統(tǒng)所花時(shí)間最少原則篩選出滿足覆蓋條件的最優(yōu)方案。結(jié)合福建省實(shí)際情況代入上述模型求解，得到了福建省應(yīng)急物資儲備點(diǎn)的選址方案。為以后解決此類問題提供了簡單可行的參考。該方法依賴計(jì)算機(jī)編程窮舉解決，在面對更多數(shù)據(jù)時(shí)可能會有很高的時(shí)間復(fù)雜性，具有一定的局限性。

[1] BallM O, Lin F L. A Reliability Model Applied to Emergency Service Vehicle Location[J]. Operations Research, 1993,41(1):18-23.

[2] List G F. Routing and Emergency-response- team Sitting for High-level Radio active Waste Shipments[J]. IEEE Transactions Engineering Management, 1998,45(2):141-152.

[3] 常玉林，王煒. 城市緊急服務(wù)系統(tǒng)優(yōu)化選址模型[J]. 系統(tǒng)工程理論與實(shí)踐，2000(2):104-107,117.

[4] 方磊，何建敏. 給定限期條件下的應(yīng)急系統(tǒng)優(yōu)化選址模型及算法[J]. 管理工程學(xué)報(bào)，2004(18):48-51.

[5] 韓強(qiáng)，宿潔. 一類應(yīng)急服務(wù)設(shè)施選址問題的模擬退火算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2007,43(14):202-203,239.

[6] 龍文，黃漢明，李小勇,等. 多目標(biāo)城市應(yīng)急系統(tǒng)選址問題的免疫算法[J]. 廣西物理，2008(2):26-28.

[7] 郭子雪，齊美然，張強(qiáng). 應(yīng)急物資儲備庫最小加權(quán)距離選址模型[J]. 計(jì)算機(jī)工程與應(yīng)用，2009(34):195-197,200.

[8] 李棟學(xué)，劉茂. NSGAⅡ在應(yīng)急物資儲備庫選址中的應(yīng)用[J]. 工業(yè)安全與環(huán)保，2009(35):1-3.

[9] 劉浪，黃有方,等. 加權(quán)網(wǎng)絡(luò)應(yīng)急物資儲備點(diǎn)選址方法1[J]. 北京理工大學(xué)學(xué)報(bào)，2011,31(2):244-252.