汪文文，方 玺，何 朗，刘 扬，张 亮

WANG Wenwen,FANG Xi,HE Lang,LIU Yang,ZHANG Liang

武汉理工大学 理学院，武汉 430070

School of Science,Wuhan University of Technology,Wuhan 430070,China

1 引言

近年来，国内各种突发事件频发，造成了极大的人员伤亡和经济损失，如2008年“5·12”汶川特大地震，2015年天津大爆炸，2016年湖北、安徽、河北多地区暴雨等。在突发事件[1]频出不穷的情况下，应急问题已经成为十分紧迫的重大问题。在应急管理中，应急设施是救援过程中必不可少的组成部分，研究应急管理中的设施选址对于提高应急管理能力有重要的应用价值，吸引了国内外众多研究学者的目光。

应急选址优化问题是城市应急系统中不可或缺的一部分，近年来无数学者对其进行研究，提出不同的模型。Salman等[2]基于突发事件下的应急选址，通过最大化需求覆盖，提出0-1整数规划求解；Wohlgemuth等[3]考虑最小化配送中心到需求点的距离、区域内的需求点非覆盖需求建立多目标模型；由于传统静态、确定型选址模型在应用上仅考虑单一时间，Ballou[4]首先提出了动态设施选址问题，研究了如何选择一个仓库使其在规划期内实现利润最大；Gao等[5]将动态选址问题分为LAP与VRP两部分，并在动态环境下考虑随机与循环流量等因素，对模型进行求解；Marufuzzaman等[6]构建一个基于容量的动态选址模型，以期在满足需求点的需求条件下以最小的代价在决策时间内给出选址方案；动态模型被运用到多个领域，如战斗物流[7]、电商物流[8]、应急物流等。由于静态模型考虑其选址因素均独立于时间，而动态选址考虑了在实际应用中需求量、能源价格、市场增长等可变因素，其模型在实际应用中具有更强的适应性，且更加科学。

应急选址所需要考虑的因素极为复杂，通常需要考虑多个因素，其所研究的问题为多目标优化问题，该优化问题一般采用进化算法进行求解，例如SPEA、PSO、NSGA、MOEA/D。Dong等[9]提出一种基于MOEA/D的改进算法，通过多样性检测和混合种群操作增强解的全局搜索能力；MOEA/D算法效率较高，但其最优解的分布随机性较大；NSGA-II采用非支配排序机制降低算法的复杂度，且Pareto最优解集具有良好的分布性，是一种综合性能较好的算法。Badri等[10]构建了一个有约束的多目标优化问题，并通过NSGA-II、SPEA2以及PESA-II进行求解，实验结果显示NSGA-II可产生相对较优的Pareto前沿。由于NSGA-II在收敛过程中易产生重复个体而陷入早熟，对于NSGA-II算法的改进逐步被提出，Zade等[11]提出一种基于交叉和变异算子改进的NSGA-II，增强了解集的多样性以及精确性，但增加了算法的计算量；常辉等[12]提出基于递归的快速排序法，增强了算法的鲁棒性，降低了算法的复杂性，但其仅适用于双目标问题，而对于多目标问题其效率则具有一定的局限性。在实际应用中，单一的算法对于求解多目标优化问题往往已不能满足需求，混合优化算法逐步被提出，Li等[13]提出了一种基于改进的NSGA-II的二阶段变量值选择去解决包含多个解的质量特性，但在降低算法复杂度的同时造成优秀解在迭代过程中逐步损失。因此对于NSGA-II算法的改进仍需持续深入研究。本文拟通过将禁忌搜索算法融入到NSGA-II的精英策略中，加强算法的局部搜索能力，同时保留其多样性以及分布性，并通过数值算例验证算法的收敛性及分布性。

2 多目标动态选址模型

2.1 应急物资点选址决策目标评价体系

本文考虑以救援时间为评价的主要指标，用物资效用反映时效性，以灾区满意度反映公平性，以临时物资配送中心的个数反映均衡性，建立多目标动态选址模型；在模型求解时，充分对3个目标进行分析，通过改进的NSGA-II算法进行求解，得到更为合适的选址方案，对于应急管理系统进行科学决策具有一定的指导意义。

2.2 基本参数与决策变量

假定平面上存在3个集合，即需求点集合、临时物资候选点集合和固定物资点，已知任意两个点之间的可行距离以及汽车运行速度，选取合适的临时物资点，并得到最优调度方案。本文考虑物资效用、临时物资点个数以及灾区满意度作为目标函数，基本参数如下：在地震灾害中人的存活率与时间的关系，I为固定物资点集合，J为需求点集合，S为临时物资候选点集合，V为各种汽车运行速度的集合。候选点s被选择，则hs=1，否则hs=0。

2.3 多目标动态选址模型

基于应急物资中心选址决策目标评价体系的分析，本文将物资储备应急效用、灾区满意度、临时物资点的数目作为目标决策函数。

由文献[14]知某次地震灾害后，受灾人员的存活率与时间的关系为：

定义物资储备应急效用为各个物资点的有效利用量：

定义受灾区域的满意度为各个物资点（包括固定物资点和临时物资点）的储备效用与各个灾区所需要应急物资之比，且灾区的满意度值尽可能大，即：

式（5）保证了在固定物资点资源都用尽之后，才开始用临时物资点；式（6）表明由临时物资点运到各个灾区的资源量应该小于其储备量；式（7）表示运往灾区的物资量应该小于其需求量，以减少不必要的经济损失；式（8）保证运输量有意义。

本文所构建的为多目标动态选址模型，与传统静态选址模型的主要区别在于随着灾害的持续发展，往往会导致灾区对于应急物资的需求量逐步递增，原有的物资点并不能向灾区提供充足的物资，此时会造成供不应求的状况。而本文所构建的模型则将这一因素考虑进来，增加了模型的鲁棒性。

针对自变量个数较多且最优解较为复杂的多目标优化问题，传统的目标优化算法MOEA/D、NSGA-II的收敛性以及所得解的精度均较差。同时MOEA/D进行加权存在一定的主观因素，而本文所研究的背景为应急物资选址，对于目标函数的权重无法给出比较客观的分析，而NSGA-II在迭代搜索过程中难以找到孤立点，且子代容易产生重复个体，因此本文拟在NSGA-II的基础上加入禁忌搜索[15-16]算法设计一种混合优化算法，以期算法能够达到较强的收敛效果。

3NSGA-II及改进

本文研究的内容为一个多目标优化问题，对于多目标优化问题，一般采用多目标进化算法（MOEAs）[17]和多目标转换为单目标两种方式来进行求解，然而多目标问题转化为单目标问题则可能造成所求的解为非可行解，因此本文采用MOEAs进行求解。NSGA-II是一种较为常用的MOEAs算法，其优点在于运行效率高，所得解集具有良好的分布性，其主要不足在于难以找到孤立点，且容易产生大量重复个体。为克服上述缺点，本文提出一种改进的NSGA-II算法，主要在以下两方面进行改进：

（1）改进遗传算子的变异操作，变异个体从当前个体的领域产生，而非随机生成，从而减少了重复个体产生的概率，同时提高了搜索效率。

（2）提出一种混合的精英策略，在进行合并的时候，将父代个体、遗传算子所得的子代个体，以及禁忌搜索[18]所得子代进行合并，增强了子代群体的多样性。

具体操作如下：

（1）变异算子的设计

变异算子影响着遗传操作的效果，其可跳出局部最优解，从而达到全局最优解，而变异概率则影响着变异算子的效果。传统的变异具有一定的随机性，在搜索过程中易产生重复个体且具有一定的随机性。本文采用变异个体从当前解的邻域中产生而非随机产生，加强解的局部搜索效率，且变异概率Pm随着所产生的邻域解的效果而动态变化，当邻域最优解满足藐视准则，则Pm=1，否则Pm=0。当Pm=1时，则将当前个体作为变异个体加入到子代种群中。通过这种改进，减少了重复个体产生的概率，同时提高了搜索效率。可以通过增加搜索到孤立点的概率，从而增加个体的多样性。

（2）混合精英策略

本文通过将禁忌搜索算法引入到精英策略中，以期增加解集的多样性以及均匀性。令合并之后的解集为Rt=Pt⋃Gt⋃Tt，其中Pt为父代个体，Gt为遗传算子所得个体，Tt为禁忌搜索算子所得个体。其次由非支配排序及拥挤度距离从Rt中选取前N个个体作为下一代父代个体Rt+1，通过这种操作可以保留NSGA-II避免父代优良个体流失的优点，同时增强局部搜索能力，进而减少子代中重复个体的个数，增强解集的多样性。

禁忌搜索的策略如下：

（1）初始解

禁忌搜索算法对初始解的依赖性较高，因此初始解从父代个体非支配排序为1的个体中随机选取。

（2）邻域解

初始迭代，为增加搜索到最优解的概率，扩大搜索范围，随着迭代的逐步进行，所得解趋近于最优解，因此应该缩小搜索的范围，避免重复搜索。邻域生成以及搜索范围分别按以下公式更新：

边界处理：

若Xj＞UX,Xj=Xj+LX-UX，否则Xj=Xj-(LXUX)。

（3）候选解

对于给定个体X，计算其所有邻域解的计算量较大，因此需要一定的策略选取候选解。本文采用非支配排序和拥挤度算子从所给候选解里面选取一定数量的解作为候选解N(x)。

（4）藐视准则

X∈opt{N(x)}，若存在X≺Xbest，则X被选为下一个当前解。

（5）禁忌表

当前解X已被禁忌，当且仅当∀Xj∈Tabulist，满足

算法主要步骤如下：

步骤1产生初始种群Pop。

步骤2快速非支配排序，在进行选择运算之间，根据个体非劣解的水平先对种群进行分层得到父代个体Pt。

步骤3遗传算子操作（选择、交叉和变异），变异算子采取本文所提方式进行，产生新的个体Gt。

步骤4禁忌搜索策略：按照本文所提的禁忌搜索算法的流程执行，产生新的个体Tt。

步骤5精英策略，首先将父代Pt、遗传算子Gt和禁忌搜索算子Tt合并成一个种群Rt=Pt⋃Gt⋃Tt，种群Rt的个体数目变为2N；其次，对种群Rt进行非支配排序，并计算相应的拥挤度距离；最后，根据等级的高低逐一选取个体，直至个体总数达到N，令其为新一轮进化过程的父代种群Pt+1。

步骤6重复步骤3～步骤5直至满足迭代终止条件。

根据步骤1～步骤6可得NSGA-II-TS算法设计流程图如图1所示。

图1 NSGA-II-TS流程图

禁忌搜索算法在搜索过程中所产生的候选解在其当前解的邻域产生，而非随机生成，且其可以接受次优解，具有较强的爬山能力，因此其搜索到最优解的概率增大，同时保留了NSGA-II的遗传算子操作，从而保留了NSGA-II所产生个体多样且均匀的优点。基于应急选址对于实时性和优化性同等重要，本文通过在NSGA-II精英策略中加入禁忌搜索算法，设计一种混合的进化优化算法，一方面加强解的局部寻优能力，另一方面保留NSGA-II较优的全局搜索能力，从而使得收敛到局部最优解的速度加快且所得解的精度提高。

4 数值算例及结果分析

仿真实验分为两部分：首先对有界闭域上连续函数全局优化进行算法的有效性分析；其次将其应用到离散应急选址问题上进行算法分析。本文所有的仿真实验平台为Intel®CoreTMi5-4200H，4.0 GB RAM，实验环境为MATLAB R2012b（8.0.0.783）。

4.1 连续函数的应用

本文选择经典二维测试函数ZDT1、ZDT2、ZDT3[19]对算法进行实证分析，函数表达式如表1所示，选取经典NSGA-II、MOEA/D与NSGA-II-TS进行对比分析，通过Pareto前沿对算法的收敛性以及分布性进行分析。

ZDT1、ZDT2、ZDT3分别在变量个数为30、100时进行测试，设置算法的种群大小为500，迭代次数为100，分别独立运行20次，3种算法得到的Pareto前沿对比图如图2所示。从图2的Pareto前沿对比图中可以看出，通过NSGA-II-TS得到的Pareto收敛性以及多样性明显优于NSGA-II和MOEA/D、NSGA-II-TS所得的Pareto光滑、均匀，且基本上和真实的Pareto重合，而MOEA/D所得Pareto存在较多间断点，NSGA-II算法虽然得到的曲线形状与真实的Pareto基本一致，但其收敛性远远不如NSGA-II-TS；同时随着决策变量增加至100时，MOEA/D算法的效率明显下降，逼近效果尤为差，且需要至少300次迭代才可较好地逼近，NSGA-II算法可在100次迭代中逼近真实Pareto，但其效果远远不如NSGA-II-TS。由此说明，无论是较少的决策变量还是较多的决策变量，NSGA-II-TS均可以较好地逼近最优Pareto。

表1 测试函数

图2 ZDT系列函数Pareto对比图

表2 世代距离

表3 spacing指标值

本文为进一步说明3种算法的收敛性以及解集的均匀性，分别采用Deb[20]提出的世代距离和Schott[21]提出的spacing，对算法进行定量分析。表2和表3分别为对ZDT系列函数在不同变量下测试20次所获得的spacing以及世代距离的均值、标准差和中值。由表1和表2可以看出，在20次实验中，NSGA-II-TS获得的spacing值和世代距离值均小于NSGA-II、MOEA/D，且NSGA-II-TS的波动性比较小，这种优势在决策变量增加至100时更为明显，说明本文算法在解决连续多目标优化问题上具有更好的收敛性。

4.2 应用分析

设置候选临时应急物资点为100个，固定点为3个，需求点为10个，设定种群为100，迭代次数100，实验20次，得到最优Pareto解集。由于在实际应急救援中需给出最优行动方案，本文采用理想点法[11]对组合解的优劣程度进行评判，得出在该标准下的最优应急方案。

首先，利用公式进行标准化：

其次，选择理想点：

最后，使用欧式距离评测解的好坏，d(h)越小越好：

表4为各个算法通过理想点法所确定的最优解。由表4可知，NSGA-II-TS效果比NSGA-II和MOEA/D算法好。首先，对于应急物资点个数NSGA-II比NSGAII-TS少两个，但其物资效用度却比NSGA-II-TS小了833 m3，并且灾区的满意度也比NSGA-II-TS小了4.6%，保证灾区人民的满意度较大，且物资效用达到最大，同比增加两个物资点是值得考虑的；其次，对于MOEA/D算法，其物资效用度平均值基本在47000以上，达到比较好的效果，与NSGA-II-TS差别较小，然而其物资点则增加了NSGA-II-TS的一倍，代价较大，因此NSGA-II-TS在灾区满意度相当的情况下，表现效果更优。

表4 各算法所得的平均值

图3为NSGA-II、MOEA/D以及NSGA-II-TS基于理想点法所得最优解的对比分析图。由图3可知，在物资效用和满意度下NSGA-II-TS所得的最优方案均高于NSGA-II和MOEA/D所得的最优方案，且NSGA-II-TS的波动性非常小，说明每次实验基本上可得到最优方案。结合表3，可以得出NSGA-II-TS优于传统的多目标求解算法MOEA/D及NSGA-II。

表5为NSGA-II、MOEA/D以及NSGA-II-TS基于秩和检验的差异度分析，结果显示3种算法在物资效用、临时物资点个数、满意度上的显著水平分别为0.01、0、0.02。拒绝原假设：物资效用、临时物资点个数、满意度在NSGA-II、MOEA/D以及NSGA-II-TS算法上是相关的，即3种算法所得的结果在统计学上具有显著性差异，从而说明基于表3的分析是可靠的，再次验证了NSGA-II-TS较传统的NSGA-II、MOEA/D算法更优。

由上述对比分析，可以明显地发现NSGA-II-TS在处理大规模应急选址问题上效果更优，可见本文算法的改进是有效的，随着应急选址规模的增大，算法的优越性更是明显。

5 结论

泥石流等突发自然灾害造成的人员伤亡和经济损失十分巨大，因此应急中心选址问题是应急救援方案中的核心环节。根据突发性事件具有动态性和时效性，考虑将救济物资效用、受灾区域满意度以及临时物资点个数作为目标函数，建立多目标动态选址模型，提出了一种改进的NSGA-II算法。该算法在精英策略上引入禁忌搜索的思想，从而实现了局部和全局搜索能力同时达到较优的结果，同时保留解集的多样性和均匀性，其理论与数值分析结果优良。

图3 对比分析图

表5 假设检验汇总

（1）通过经典函数ZDT1、ZDT2和ZDT3分别进行测试，从Pareto前沿、世代距离以及spacing指标值验证了算法的收敛性和分布性。实验结果显示NSGA-II-TS的收敛性以及Pareto解集的分布性相比NSGA-II、MOEA/D均有显著的提升。

（2）实证分析中NSGA-II-TS比NSGA-II所得的物资效用高出818 m3，满意度同比增长4.6%，而临时物资点个数仅仅增加两个；与MOEA/D算法相比较，在物资效用及满意度略优的情况下，其临时物资点的个数少了一倍，体现了NSGA-II-TS算法在解决应急物资处理中更为高效。

（3）通过秩和检验验证NSGA-II、MOEA/D及NSGAII-TS所得最优解之间的差异性，结果显示3种算法在物资效用、临时物资点个数、满意度在统计学上具有显著性差异，再次验证了NSGA-II-TS较传统的NSGA-II、MOEA/D算法在处理大规模应急选址优化问题上表现更优。

本文提出的算法在突发性灾害危机的应急管理以及其他保障体系建设问题中具有较高的应用价值。