基于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