应急物资储备点选址多目标优化模型及算法研究*

冯舰锐，盖文妹

(中国地质大学(北京) 工程技术学院，北京 100083)

0 引言

随着城市的不断发展，建筑物、各类网络系统工程密集程度增加。地震、洪水、飓风等自然灾害以及火灾、爆炸、泄漏等事故灾难一旦发生，城市内部的公众安全将面临极大威胁，救援工作难度加大[1]。在城市中各类防救灾设施(消防机构，避难场所，物资场所等)的设置均有规划标准[2-3]，选择合适的地址对紧急情况下的人力物力的节约有重要意义。建立应急资源储备点来满足物流的配送要求，就必须考虑储备点的位置及其优化问题。

选址的优化问题近年来已成为一个研究热点，陈国华等[4]基于博弈论的思想，从安全性、可达性、适宜性3 个方面构建化工园区应急避难点选址评估指标体系，并结合AHP和熵值法的组合赋权法，对指标权重进行赋权；吴坷等[5]基于弗洛伊德最短路径算法模型，以时间成本作为目标函数值，确定应急资源储备点的个数以及位置分布的最优方案；吴健宏等[6]开发了基于GIS和多目标规划模型的决策支持系统，对选址优化问题进行研究；田书冰等[7]采用云模型，对水域风险评价体系进行评价，采用自适应差分进化算法，对构建的加权距离最小为目标的溢油应急设备点选址模型进行求解；朱建明[8]以时效性、均衡性和鲁棒性3个方面构建应急选址多目标优化模型，利用理想点目标扰动最小化模型和遗传算法说明了模型和算法的有效性；陈志宗等[9]在建立模型的过程中，综合考虑了其公平性和效率性，同时结合最大覆盖模型来验证模型的正确性；姜涛等[10]利用鲁棒优化的方法，建立不确定性应急选址模型，并给出模型正确性分析；韩强[11]将应急选址优化问题与模拟退火算法结合，通过仿真验证多目标优化问题的有效性。综合以上现有研究发现，在选址方面进行多目标优化时，大多没有对改变各个目标的权重对结果的影响进行探究。因此，本文综合考虑总路程最短、成本最小2个方面，基于智能算法[12-13]和运筹学中求解多目标优化问题[14-17]的理论和方法，通过引入并改变权重[18]探究不同权重下路程和成本对应急资源储备点的选址影响，改进并设计提出求解权重的算法，并以此为基础拓展到3个及3个以上的情况，以及其他领域选址问题。具体模拟分析过程中，为了简化问题，通过使用邻接矩阵表示交通网络，并使用0-1管辖矩阵描述储备点与受灾地点之间约束关系，以此为基础建立多目标与多约束模型，得到储备点的最佳选址。

1 应急物资储备点选址多目标优化模型

1.1 问题提出

正常环境下的企业运输调度通常考虑的是经济性，但是出现灾害情况下的救援物资运输调度与前者不同，它考虑更多的是时效性[19]。第一，紧急情况下时间是最宝贵的资源，缩短救援时间就能拯救更多的生命，减少财产损失，所以在任何紧急情况下，时间是不可忽视的决策属性之一；第二，合理的救援物资储备点选址方案可以减小救援物资的周转量，降低运输费用，节约能源，为紧急状态下的缓解运量大、运输时间集中以及各个储备点的工作量差异的问题提供解决方案。

综上，影响应急资源储备点服务范围的主要因素是到达时间和经济性。在遇到紧急情况下，应急物资储备点的选址，可以要求从救援物资储备点到受灾地点的运输线路的时效性和经济性2个目标进行优化。

1.2 模型建立

应急救援物资储备点的选址问题本质上属于多目标问题，同时也是在紧急条件下的物资调度问题。它是要求满足物资周转时间最短的情况下，提高经济性，在时效性和经济性2个目标约束下，选择合适的储备点。

对于此类双目标决策问题，本文通过计算受灾地点与应急资源储备点的最短路径，进而为受灾地点分配距离最近的应急资源储备点。在满足不超过一定时间到达受灾地点的条件下，考虑整个物资周转的经济性，降低运输费用，得到更加合理的服务分配方案。

在初期的选址中，容易确定m个备选点，在m个备选点中选出最佳储备点。为了使所述问题更方便用数学模型解决，假设接到预警后，应急资源储备点立即展开配送行动，无延时。

为了便于描述，可以用T=(J，E)表示一个交通网络图，其中顶点集合J={j}中的元素，表示每个受灾地点的编号；集合E={eja,jb}中的元素，表示相邻受灾地点ja到jb的路程，单位：km，ja与jb的位置坐标可用(xa，ya)与(xb，yb)表示；假设i为应急资源储备点的编号；T中有N个节点、n个受灾地点，可以得到：

1≤m,n≤N

1

另外，为了方便利用0-1规划解决问题，可添加另一个0-1矩阵表示所有储备点的服务范围，其中的元素xij表示储备点i是否管辖受灾地点j，当取值为1时表示有服务关系；取值为0时表示没有服务关系。如式(1)所示。

(1)

为应急资源储备点分配管辖范围以及配送时，为每个应急资源储备点选择合理路径，需要获得储备点到所有受灾地点间的最短路径，按照最短路径算法可以得到备选点到受灾地点之间的距离，就可以定义为最短路程，如式(2)～(3)所示。

lij=xij·eij

(2)

(3)

式中：lij为储备点i与受灾地点j间的最短路程，单位：km；S为各条路径的之和，即总路程，单位：km。

此外，还需要考虑经济性目标，希望在物资运送过程中，能源消耗最低，这不仅与道路长度有关，而且还与道路的通行难易程度有关，比如上坡下坡、拐弯数量以及右转交通灯占交通灯总数等。因此，可以计算出相应路段的经济性权重，如式(4)所示。

cij=dij×xij

(4)

式中：dij表示储备点i到受灾地点j的经济消耗水平，包括人力资源消耗与能源消耗等。

本文所研究的应急物资储备点的双优化目标可以表示为：

(5)

(6)

(7)

(8)

式中：约束(7)表示所有受灾地点都至少需要1个储备点来服务；约束(8)中，v为车辆的平均速度，表示物资配送时间在一个可以接受的范围内，在实际应用过程中，可以改变a的值对目标进行限定，而a可以用来表示从储备点到受灾地点的时间，所以，约束(8)表示为满足一定的应急决策需求。

2 模型求解

道路下最优方案未必是经济成本的最优方案，考虑到算法未来的应用与拓展，同时降低计算的复杂度，减少紧急情况下的反应时间，借助加权法并应用变权的思想构造辅助决策函数。

2.1 模型转化与辅助函数构建

为解决2个目标的优化问题，引用权重λ得到1个无量纲数wij。

wij=λlij+(1-λ)cij

(9)

借助加权法，就可以将式(5)～(6)转化为单目标优化问题。

(10)

本文所建立的选址模型，实际上是求解满足式(8)的最优方案P。但是加权系数λ的赋值是一个关键问题，为了解决这个问题，构造1个基于式(8)的决策函数，用fk表示一个关于权重λ与W的对应关系：

y=fk(λ),λ∈[0,1]，k∈{1,2,…,X}

令Pλ表示满足约束条件的1个解，利用Pλ可构造另外2个辅助决策函数：

y=f1k(λ)=λlij(Pλ)，

y=f2k(λ)=(1-λ)cij(Pλ)

式中：λ∈[0，1]，k∈{1,2,…,X}；f1k(λ)表示权重与路程的对应关系；f2k(λ)表示权重与成本的对应关系，且fk(λ)=f1k(λ)+f2k(λ)。可证明辅助函数有如下性质成立。

性质：辅助函数y=f1k(λ)递增时，y=f2k(λ)递减，且分别在λ=0和λ=1时取得最小值，如图1所示。

证明：对W(P)取关于λ的微分，可以得到：

显然，W随lij的增大而增大，随cij的增大而减小。

图1 辅助函数性质示意Fig.1 Auxiliary function of the schematic

2.2 算法设计

根据辅助函数的性质，为了得到满足式(5)和式(6)的备选储备点，可利用Dijkstra算法作为底层算法求解lij，由于2个辅助函数分别单调递增和单调递减，可以将区间[α，β]细分为N份，只要取中间点验证是否满足约束(8)，直到找到1个不满足约束的点，改变搜索范围，缩短搜索区间，更新区间位置。令λ取值为k(β-α)/N，迭代过程中每次增加(β-α)/N，当得到满足约束(8)时，对α和β重新赋值以更新位置；当区间的长度小于精度ε时，就可以得到1个较小的近似区间[α，β]，输出此时赋值后的λ=(α+β)/2，即为1个满足条件的优化解。得到λ后，可以根据式(9)确定wij，此时，双目标优化问题转化为单目标优化问题，借助现有的Mat-lab优化工具箱即可得到关于xij的二维m×n矩阵，即应急救援物资储备点和受灾地点的对应关系。具体流程如图2所示。

图2 应急物资储备点选址双目标优化算法Fig.2 Algorithm of bi-objective optimum site selection

2.3 含3个及以上优化目标的最佳选址算法

在实际情况中，常常出现多种情况，应急救援物资储备点的多目标优化搜索算法可以以双目标优化算法为基础，增加多个权重因子，可以使含3个及以上的优化目标的最佳选址问题的求解变得容易。假设一个优化问题含有X个目标，若X>2，可将多目标优化问题分解为X个单目标优化问题。求解一个任意单目标优化问题时，可以把区间[0，1]分为若干份，获得一系列局部最优解Pi，其中i=1，2，…，N。由于多目标优化要使各个目标同时达到综合的最优值，含有多个目标的优化结果可能存在多组解。令集合A=P1∩P2∩…∩PX，那么集合A中满足目标及约束条件的解即为最优解，如果集合A为空集，则需要改变限定条件或精度ε重新迭代计算；如果这样的集合A不止1个就可以称为最优解集。

2.4 算法终止条件及优势分析

为在有限时间里解决这一问题，不能单单追求数值上的最优解，由于实际多目标优化问题较为复杂，可能存在多组改进的解，这就需要为决策者提供几种不同的方案，所以必须为该算法循环部分增加1个终止条件α-β<ε，使算法终止于决策者可接受的精度范围；其次，选取合适的N值可以提高求解效率，减少迭代时间。因为若N值过大，会因为区间过多而使寻找和迭代的次数过多，使求解效率降低，并且可能存在多个相邻点；如果N值过小，则可能丢失部分值并且同样使寻找时间增加，N值的确定可以通过多次模拟得到。

本文提出的多目标变权优化选址算法在应急管理中优势分析如下：

1)算法将紧急条件下的应急救援物资储备点选址的多目标优化问题和物资车辆的调度优化结合，利用车辆调度的最优化来确定最优选址，并建立合理的选址多目标优化数学模型，从运输路程和运输成本2个方面进行分析。借助可变权重构造辅助函数，并在辅助函数构成的搜索区间上寻找最优解。

2)算法为了保持较高的求解效率，采用启发式的思想，而不是在各个方向平均搜索，算法求解的区域相对普通多目标优化的算法小，区域缩小的速度快。

3)通过辅助函数的性质可知，令λ取值为k(β-α)/N，迭代过程中每次增加(β-α)/N，当得到满足条件的区间时，对α和β重新赋值以更新位置。当β-α缩小到可以接受的范围时，可根据模拟值绘制出辅助决策函数与参数λ的关系曲线。这样可根据所建立的应急救援物资储备点选址模型及算法，为决策者提供紧急情况下的选址优化方案，也可以通过加约束条件在可以接受的范围内提前终止算法，输出目前的局部最优解。在应急决策中，还可以根据实际情况改变目标和约束条件，形成适应于实际情况的应急救援物资储备点选址的优化方法。

3 算例分析

为了验证算法的正确性及优势，求解效率、辅助函数性质的正确性，本次算例的模拟选择某市的随机路网作为测试网络。受灾点之间，以及和储备点之间的距离可以通过GIS得到，获取距离矩阵的数据可以选择从.xls文件或者地理信息系统数据库导入。利用Mat-lab的函数库，直接调用Dijkskra算法获取储备点和受灾点的最短路径，再根据算法进行迭代，就可以得到W与λ的关系。

表1为1个具有30个受灾点(编号1～30)和10个备选应急物资储备点(编号A～J)的距离矩阵，假设受灾时所有储备点不受影响并且都可以使用，网络中每2个点的距离eij可以用1个10×30的矩阵来表示，通行速度v暂取45 km/h，最长到达时间a取2 h。

对于算法的运算与验证，在计算机上采用Matlab2016a和Lingo12共同完成， 根据本文提出的双目标优化模型，借用Dijkstra算法得到各受灾点到各应急救援物资储备点的最短距离矩阵，调用算法得到权重λ与无量纲数W的关系，如图3所示。其中，时效性和经济性曲线的变化趋势都与理论预测相同，在实际应用过程中，决策者要根据实际情况确定时间和经济成本的上限，这样就可以得到λ的取值范围，在这个范围内，可以有多种方案供决策者选择。

图3 λ与W、路程S、经济成本C的关系Fig.3 Relationship between theλ and W, the distance S, and the economic cost C.

km

表2中列出当λ=0.5时，应急物资储备点对应的受灾点，以及每个储备点的成本和路程，在10个备选点中选择了8个。此时，对应的总成本为609.5，总路程为 1 294.2。

表2 应急物资储备点与受灾点对应关系及各点的成本和路程Table 2 Corresponding relationship between emergency material reserve points and disaster points and the total cost and total distance of each point

同时，分析表2中的数据可知：应急物资储备点和受灾点的对应关系并不是均匀的，也就是各个储备点在灾变条件下的工作量不同。基于本文的算法进行选址时，时效性和经济性能得到较好地满足，能使运输路程和运输成本降到可接受范围，进而为决策者提供多组合适的储备点备选位置。

4 结论

1)利用运筹学中求解多目标优化问题的理论和方法，建立应急救援物资储备点选址数学模型。在此基础上，借用智能算法中系统动态演化方法，利用可变权重因子构造辅助函数，改变权重因子并反复迭代，可以寻找到最优解的范围，为决策者提供更多选择。

2)在求解应急救援物资储备点选址双目标优化问题时，通过辅助函数的性质改进并设计双目标优化和求解权重算法，并以此为基础推广到3个及以上优化目标的选址问题，不仅仅可以从时效性和经济性2个方面进行考虑，还可以加入关于路况、储备点的工作量以及道路安全性目标等。最后，通过算例验证了算法的正确性及优势，求解效率、辅助函数性质的正确性。

3)应急救援物资储备点选址的多目标优化数学模型适用于灾害条件下的应急资源储备点选址优化问题，同时也可扩展应用到应急管理领域中其他优化与选址问题。

[1] 徐志胜, 冯凯, 白国强,等. 关于城市公共安全可持续发展理论的初步研究[J]. 中国安全科学学报, 2004, 14(1):1.

XU Zhisheng, FENG Kai, BAI Guoqiang, et al. Preliminary Study on Sustainable Development Theory of Urban Community Safety[J]. China Safety Science Journal,2004, 14(1):1.

[2] 冯凯, 徐志胜, 冯春莹,等. 城市公共安全规划与灾害应急管理的集成研究[J]. 自然灾害学报, 2005, 14(4):85-89.

FENG Kai, XU Zhisheng, FENG Chunying, et al. Comprehensive study on urban community safety plan and disaster emergency management[J]. Journal of Natural Disasters,2005, 14(4):85-89.

[3] Hernández J Z, SERRANO J M. Knowledge-based models for emergency management systems[J]. Expert Systems with Applications, 2001, 20(2):173-186.

[4] 陈国华, 夏浩, 高子文. 化工园区应急避难点选址评估模型应用研究[J]. 中国安全生产科学技术, 2017, 13(8):61-66.

CHEN Guohua,XIA Hao,GAO Ziwen.Research on application of evaluation model for emergency shelter location in chemical industrial park[J]. Journal of Safety Science and Technology,2017, 13(8):61-66.

[5] 吴坷, 宋英华, 吕伟. 城镇应急资源储备点选址与布局优化研究:考虑暴雨灾害和路径长度[J]. 中国安全科学学报, 2017, 27(9):170-174.

WU Ke,SONG Yinghua,LYU Wei.Research on siting of urban emergency resources depots and layout optimization considering rainstorm disaster and distribution route[J]. China Safety Science Journal, 2017，27(9):170-174.

[6] 吴健宏, 翁文国. 应急避难场所的选址决策支持系统[J]. 清华大学学报(自然科学版), 2011(5):632-636.

WU Jianhong,WENG Wenguo.Decision support system for urban shelter locations[J]. Journal of Tsinghua University(Sci & Tech),2011(5):632-636.

[7] 田书冰, 杨亚东, 田延飞,等. 长江干线中下游溢油应急设备点选址优化[J]. 安全与环境学报, 2017, 17(1):90-93.

TIAN Shubing, YANG Yadong,TIAN Yanfei, et al. On the optimized construction site choice for the oil spilling emergency point in the middle and lower reaches of Yangtze River[J]. Journal of Safety and Environment, 2017, 17(1):90-93.

[8] 朱建明. 损毁情景下应急设施选址的多目标决策方法[J]. 系统工程理论与实践, 2015, 35(3):720-727.

ZHU Jianming.Methods of multi-objective decision-making for emergency facility location problem under failure scenario[J]. Systems Engineering-Theory&Practice, 2015, 35(3):720-727.

[9] 陈志宗, 尤建新. 重大突发事件应急救援设施选址的多目标决策模型[J]. 管理科学, 2006, 19(4):10-14.

CHEN Zhizong,YOU Jianxin. A Multi-objective Decision Model of Emergency Rescue Facility Location for Large-scale Emergency Incidents[J]. MANAGEMENT SCIENCES IN CHINA, 2006, 19(4):10-14.

[10] 姜涛, 朱金福. 应急设施鲁棒优化选址模型及算法[J]. 交通运输工程学报, 2007, 7(5):101-105.

JIANG Tao, ZHU Jinfu.Robust optimization model and algorithm of eanergency establishment[J]. Journal of Traffic and Transportation Engineering, 2007, 7(5):101-105.

[11] 韩强. 多目标应急设施选址问题的模拟退火算法[J]. 计算机工程与应用, 2007, 43(30):182-183.

HAN Qiang.Simulated anealing algorithm for multi-object emergency location problem[J]. Computer Engineering and Applications, 2007, 43(30):182-183.

[12] 焦巍, 刘光斌. 非线性模型预测控制的智能算法综述[J]. 系统仿真学报, 2008(24):6581-6586.

JIAO Wei, LIU Guangbin. An overview of intelligent algorithms for predictive control of nonlinear models[J]. Journal of System Simulation, 2008(24):6581-6586.

[13] 余建平, 周新民, 陈明. 群体智能典型算法研究综述[J]. 计算机工程与应用, 2010, 46(25):1-4.

YU Jianping, ZHOU Xingming, CHEN Ming. Research overview of group intelligent typical algorithms[J]. Computer Engineering and Applications, 2010, 46(25):1-4.

[14] 师立晨, 魏利军, 吴宗之. 危险品道路运输多目标路径优化方法研究[J]. 中国安全生产科学技术, 2006, 2(5):59-63.

SHI Lichen, WEI Lijun, WU Zongzhi. Study on multi-objective path optimization for dangerous goods road transport[J]. Journal of Safety Science and Technology,2006, 2(5):59-63.

[15] KHALAFALLAH A, El-RAYES K. Automated multi-objective optimization system for airport site layouts[J]. Automation in Construction, 2011, 20(4):313-320.

[16] GASPAR-CUNHA A,COVAS J A. Robustness in multi-objective optimization using evolutionary algorithms[M]. Kluwer Academic Publishers, 2008.

[17] 盖文妹, 蒋仲安, 邓云峰,等. 应急救援物资车辆运输路线多目标优化[J]. 北京科技大学学报, 2014(10):1384-1393.

GAI Wenmei,JIANG Zhongan, DENG Yunfeng, et al. Multi-objective route optimization of transporting emergency goods and materials for rescue[J]. Journal of University of Science and Technology Beijing, 2014(10):1384-1393.

[18] 任子晖, 王坚. 一种动态改变惯性权重的自适应粒子群算法[J]. 计算机科学, 2009, 36(2):227-229.

REN Zihui, WANG Jian. An adaptive particle swarm optimization algorithm for dynamic change of inertia weight[J]. Computer science, 2009, 36(2):227-229.

[19] 袁媛, 汪定伟. 灾害扩散实时影响下的应急疏散路径选择模型[J]. 系统仿真学报, 2008, 20(6):1563-1566.

YUAN Yuan, WANG Dingwei. Route Selection Model in Emergency Evacuation under Real Time Effect of Disaster Extension[J]. Journal of System Simulation, 2008, 20(6):1563-1566.