基于Prim算法和AHP的疫區救援物資投放的優化方法

張智昊，李林巍，楊澤宇

（大連理工大學 運輸管理學院，遼寧 大連 116023）

基于Prim算法和AHP的疫區救援物資投放的優化方法

張智昊，李林巍，楊澤宇

（大連理工大學 運輸管理學院，遼寧 大連 116023）

首先利用AHP，計算得出疫區救援物資投放系統安全性、有效性等方面的權重，并在此基礎上建立疫區簡化模型，引入Prim算法得到基于最小生成樹的最優救援物資投放系統.最后以2014年利比里亞的埃博拉疫情對上述模型進行了檢驗，證實該模型可行.

Prim算法；AHP；最小生成樹；疫區救援；應急物流

物資的迅速投放是緊急事件救援例如疫區救援中一項十分重要的工作，對此前人也已經做了很多細致的研究.其中的物資投放路徑規劃這一問題，已經有基于隨機規劃、遺傳算法[1]、蟻群算法[2]、AHP、Dijkstra算法[3]等比較方便實用的路徑規劃方法.

在以往的對基于圖的宏觀模型的研究中仍存在著這樣的局限：決策中，一些影響因素與結點（投放點）有關，有些與邊（投放路徑）有關.這樣在利用AHP綜合處理這兩方面的因素時，如何計算權重仍是一個尚待解決的問題.另外，當疫情出現在偏遠、道路等方面數據不全面的地區的時候，AHP的各個影響因素的評定很難確定.因此本文將在之前研究的基礎上，給出一定程度上解決這兩問題的方案.

1 Prim算法和AHP簡介

Prim算法是1957年由R.C.Prim獨立發現的一種在給定的有權重連通圖中構造最小生成樹的方法.這種算法適用于在稠密圖中構造最小生成樹.自問世以來，在路徑規劃問題中已取得廣泛應用[4].

這一算法的核心是兩個集合T和R，T用于記錄構成目標最小生成樹的結點，而將剩下的結點存放在R中.每次，從R中選出與T中結點相連的權重最小的點，將之加入T中.這樣遍歷R中所有結點，就可以得到原始圖的最小生成樹.

對于疫區救援問題，應先算出每條路徑的權重，再利用這一算法編程解決.

AHP是1970s由T.L.Saaty首先提出的，用于對一些較為復雜模糊的問題做出決策的簡易方法，主要對具有不同重要性的元素進行比較，然后用“標度”量化，適用于難以完全定量分析的問題[5,6].核心在于分別評價各個因素的作用強弱，應用數學方法進行檢驗，避免評價的不一致.

2 模型建立

2.1 建立遞階層次結構模型

模型假設：

（1）假設影響一個投放點在配送系統中的優先級的因素除了距離，還有當地疫情嚴重情況、海拔、繁榮程度、偏僻程度.

（2）假設疫情可以用當地發病人數衡量.

（3）假設繁榮程度可以用當地人口、搜索量衡量.

（4）假設偏僻程度可以用與地域中心（例如首都）的直線距離衡量.

（5）我們約定，路徑的長度稱作實際長度；綜合了這五個因素之后，某路徑對分配的吸引力稱為調整后長度.

如引言中所述，假設1中前四個因素是與圖的結點相關的，而最后一個則和圖的邊相關.由于路程因素始終是影響運輸人員路徑選擇的首要因素，因而不將這五種因素看作是平權的，而是將路徑的調整后長度作為這條邊的權重.

因此可以得到第i個結點的權重kj；設這一結點與權重為kj的第j個結點之間的路徑長度為l，那么這一路徑的最終權重是：

其中L是邊的調整后長度，V是邊的權重.

因此根據假設，建立遞階層次結構模型如下：

圖1 遞階層次結構模型

2.2 構造判斷矩陣

根據經驗和資料，針對上述各因素構造判斷矩陣如下：

表1 判斷矩陣A

其中分別表示上述四個因素對結點權重的影響.

2.3 一致性檢驗

計算上述矩陣的一致性指標CI，引用公式[6]如下：

可知

查得平均隨機一致性指標RI表[6]可知：

這樣依據文獻[5]，可以認為上述判斷矩陣是一致的.因此可以將上述矩陣A作為判斷矩陣.

2.4 權向量解算

根據求權向量的特征根法[6]，可以根據如下公式得出各因素權重：

其中λ是判斷矩陣A最大的特征值，對應的向量w歸一化后就是上述前四個影響要素的權向量.按照這一方法，解得權向量并歸一化如下：

w=(0.6511,0.04923,0.1838,0.1159)T

2.5 各決策因素的度量

根據疫情、海拔、繁榮程度以及偏僻程度對所有需要經過的投放地點進行排序，按照具體情況進行分組，在某區間中進行評級.根據實驗，當這一區間選在(0,2,1)時，模型能取得較好的敏感性和魯棒性.

3 模型檢驗

以2014年前后的利比里亞埃博拉疫情為例，在利比里亞20余個主要城市中構造一個有效的藥品疫苗等物資的投放網絡，并對模型進行檢驗.

3.1 構造利比里亞各主要城市關系圖

根據維基百科，獲得利比里亞各主要城市的經緯度.考慮到疫情救援物資的特殊性和利比里亞國土面積較小以及全國以公路運輸為主，假設物資投放完全依賴公路運輸，并假設每兩個城市之間均可以直線到達.這一假設的不準確由海拔等其他決策因素在一定程度上彌補.

根據這些資料和假設，以城市作為結點，城市之間的道路作為邊，可以得到利比里亞主要城市運輸圖如下.

圖2 利比里亞主要城市運輸圖

3.2 對各決策因素進行度量

疫情嚴重程度

通過查閱世界衛生組織2015年2月4日的疫情通報[7]可以得到各州最大疫情人數，對于至少包含一個較大城市的州，將該州人數取平均數作為各個城市疫情嚴重程度的度量，并以此由大到小對各個城市排序，每四個城市為一組，分別賦予權重（1，0.82，0.64，0.46，0.28）.

海拔

通過各個城市經緯度查閱谷歌地球獲取各地海拔，將各個城市按海拔由小到大進行排序，以四個城市為一組，分別賦予權重（1，0.82，0.64，0.46，0.28）.

繁榮程度

查閱維基百科，將各個城市按經濟發展狀況及城市建設進行排序，以四個城市為一組，分別賦予權重（1，0.82，0.64，0.46，0.28）.

偏僻程度

計算各個城市與首都距離，將各個城市按與首都距離由小到大進行排序（這是由于利比里亞首都作為外界物資運輸的入口相對合理），同樣每四個城市為一組，分別賦予權重（1，0.82，0.64，0.46，0.28）.

3.3 對所有結點和邊賦權重

按照上面列出的評級，根據3.2.4中計算得出的權向量可以對所有結點賦權重.根據各城市的經緯度資料，可以計算得出每條邊的長度.在此基礎上，根據3.1中的式（1）可以得出每條邊的權重.數據較多故不具體列出.

3.4 模擬仿真實驗

在前面工作的基礎上，對利比里亞的物資投放系統已經有了初步的模型.接下來利用Prim算法和AHP求得最小生成樹如下：

圖3 分配系統最小生成樹圖

按照上述結果，在最小生成樹的分叉處，也就是第1、12、10、2、13、8號城市應該修建配送中心，而在其余結點設立一般的配送點.

5 結語

在疫區救援物資投放的路徑規劃問題中，我們基于AHP和Prim算法，提出了一種將結點與邊的權重綜合考慮的方案，同時提出了一種在這一情況下AHP的遞階層次模型，得出了一種新的路徑權重計算方法.最后以利比里亞埃博拉疫情為例證實了模型的實用性.但由于信息較少，假設較多，整個模型的實用性和準確性方面仍然可以進一步優化.

〔1〕王新平，王海燕.多疫區多周期應急物資協同優化調整[J].系統工程理論與實踐，2012，32（2）：283-291.

〔2〕劉勇.基于蟻群算法的應急救援最優路徑研究[D].武漢：中國地質大學，2010.

〔3〕王洪,陸愈實,王莎莎.基于MATLAB的應急救援最優路徑選擇[J].工業安全與環保，2009，35(1):48-50.

〔4〕PRIM,R.C.Shortest Connection Networks And Some Generalizations[J].THE BELL SYSTEM TECHNICAL JOURNAL,November 1957:1389-1401.

〔5〕章志敏，魏翠萍.層次分析若干理論與應用研究[J].曲阜師范大學學報，2013，39（1）:37-41.

〔6〕姜啟源，謝金星，葉俊.數學模型(第四版)[M].高等教育出版社1987.249-258.

〔7〕HTTP://APPS.WHO.INT/EBOLA/EN/EBOLA-SITUATION-REPORT/SITUATION-REPORTS/EBOLA-SITUATION-REPORT-4-FEBRUARY-2015) [OL].

U412.2

A

1673-260X（2015）09-0194-02