张翰祥，邓丽娟 （集美大学 航海学院，福建 厦门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.