福建省加權網絡應急物資儲備點選址

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

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

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

應急物資儲備點選址是應急管理中的非常關鍵的一環，它直接關系到資源高效調度和應急方案實施的成敗。應急物資儲備點選址問題，主要是研究如何通過合理安排有限的應急資源，及時有效地進行應急救援行動，盡可能地減少事故所造成的人員傷亡和財產損失。

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

1 加權網絡應急物資儲備點選址方法

應急儲備點的選址問題實際上是一種點覆蓋類型問題，本文利用圖論的方法，在證明無權網絡中點對邊覆蓋問題也是整數規劃問題的基礎上，以物流運輸時間作為應急物流網絡的權重來構建應急物流網絡的加權拓撲結構，對加權網絡中的應急物資儲備點選址問題進行研究。

1.1 儲備點選址

應急物資儲備點選址問題是假設在現有的網絡頂點所在地作為物資儲備點的備選點，以網絡的邊和點作為應急的對象，建立網絡模型。

1.2 加權網絡

運用圖論的方法，將網絡模型轉化為二部分圖，進而轉化為0-1 整數規劃問題。具體的方法是將網絡模型中的邊抽象成點，原來網絡模型中的點依然是點，將原網絡模型中的點與邊有連接關系的關系抽象成點，將點對邊的覆蓋轉化為點對點的覆蓋。如圖1 所示無權網絡可以將其轉化成圖2 所示的二部分圖。

集合覆蓋要求選出的儲備點滿足以下整數規劃公式：

式中：A為二部分圖化為0-1 整數規劃后的關聯矩陣，它是以頂點集合V中的點為行，邊集合E中的點為列，V、E中的點有連接關系的用1 表示，無連接關系的用0 表示而構成的；表示任意1 個應急對象至少有1 個儲備點能覆蓋到它。

對圖2 利用編程求解可得，當選擇的頂點數目不小于2 個時，可以完成對點和邊的完全覆蓋。

1.3 加權網絡應急物資儲備點選址

例如在圖2 中設E1=1h，E2=2h，E3=3h。則優化目標是從上面得到的解集中找到遍歷應急系統所有線路所花時間最少的方案，讓選出的儲備點沒有盲點，且應急時間最短，應選擇V1和V2作為應急物資儲備點，最短遍歷時間為

圖3 福建省市級拓撲圖

2 應急物資儲備點選址的應用

2.1 福建省拓撲網絡結構的構建

因福建省交通運輸主要依靠公路，且即使在重大臺風災害下，高速公路不會受到過大影響。因此，用各個市中心高速公路運輸時間作為各邊的權重更加符合福建省實際情況。令頂點集合（分別代表寧德，南平，福州，三明，莆田，龍巖，泉州，漳州，廈門的市中心），邊集合E=｛E1,E2,…,E13｝（分別代表各個市中心之間高速公路的運輸時間，單位：min），建立拓撲模型。其中，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 應用集合覆蓋

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

圖4 無權網絡二部分圖

這樣點對邊覆蓋問題就轉化成了0-1 整數規劃問題，需要滿足條件：

可以利用計算機循環程序從選擇所有頂點，依次遞減頂點數目，看是否滿足條件。當點集P有不少于5 個元素時可以滿足覆蓋條件。但是，當點集P有5 個元素時，總共有600 種方案，例如第51 種方案圖，見圖5 所示。因此必須對這些方案進一步優化取舍。

2.3 篩選應急物資儲備點最優選址方案

根據“災害發生時，以最短的時間運輸救災物資”的原則，對滿足條件的集合P進行優化。優化目標是從所有點集P中找到這樣一個點集B，使得點集B中所有頂點元素覆蓋的邊權重和最小。根據以上思路，利用計算機循環程序進行運算求解，可以進一步得出所有點集P的權重和，然后找出權重最小的方案。

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

圖5 應急物資儲備點選址圖（方案51）

圖6 應急物資儲備點最優選址方案最優方案

綜上所述，應該選取 ｛南平，福州，泉州，龍巖，廈門 ｝作為應急物資儲備點，最小遍歷運輸時間為2 182 分鐘。

3 結 論

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

[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] 常玉林，王煒. 城市緊急服務系統優化選址模型[J]. 系統工程理論與實踐，2000(2):104-107,117.

[4] 方磊，何建敏. 給定限期條件下的應急系統優化選址模型及算法[J]. 管理工程學報，2004(18):48-51.

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

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

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

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

[9] 劉浪，黃有方,等. 加權網絡應急物資儲備點選址方法1[J]. 北京理工大學學報，2011,31(2):244-252.