基于免疫优化算法的应急物资储备库选址

张爱琳，刘晓佳，何利军

(集美大学航海学院，福建 厦门 361021)

0 引言

灾后应急物资不同于一般物资，它具有时效性、不确定性、弱经济性和非常规性等特征，而应急物资储备库选址直接影响着物资运输的时效性。为了达到时间效益最大化或灾害损失最小化的目的，国内外许多学者从不同角度运用不同的方法对应急物资储备库选址进行了深入研究。Sheu[1]针对紧急救援期间的应急需求，提出了一种混合模糊聚类优化方法，以需求满足率最大为目标函数并设计了动态规划算法求解。Pereira等[2]以最小化距离和成本为优化目标建立最大覆盖概率的应急设施选址优化模型，提出一种混合算法求解模型。Yang等[3]提出一种模糊多目标规划和遗传算法相结合的方法，以成本和最远距离最小为目标建立双目标选址模型。Ai等[4]针对海上应急系统中应急物资储备库选址问题，提出一种离散的多目标非线性整数规划模型，并用遗传算法求解了该模型。王芳等[5]采用R因子分析法计算出应急物资储备设施备选点，再以设施点与应急需求点距离之和最小为目标函数构建应急物资储备库选址模型。吴坷等[6]运用弗洛伊德最短路径算法以时间成本为目标函数值，计算出最短路径长度，以便确定应急资源储备点的个数以及位置分布。赵玲等[7]针对应急环境的复杂性和不确定性，构建了基于三角模糊数的最大覆盖模型。俞武扬等[8]构建了基于最小风险的应急服务设施选址模型，设计改进后的模拟退火算法对模型进行求解，提出应急服务设施选址优化策略。

可以看出，多数应急物资储备库选址的研究都是以时间效益最大化为目标函数建立选址模型。在应急物资储备库选址的研究中不但要关注时间效益，同时也需要考虑到应急系统一旦建立后所带来的社会效益，譬如公众的“易接近性”。Church等[9]曾表示，确定公众到设施的平均距离是测量某个应急系统位置有效性的重要方式，平均距离上升，设施的易接近性下降。以往的选址模型忽略了各个应急需求点的风险权重，不同应急需求点的风险权重是不同的。因此，本文针对应急物资运输调度的时效性特点，从应急物资储备库的“易接近性”出发，利用三角模糊数对应急需求点历史灾害事件数据进行模糊化处理，引入风险权重系数，建立应急物资储备库选址模型。构建的选址模型目标函数在满足设置的约束条件下取最小值，即实现了应急物资运输距离最短或用时最少。鉴于模型非凸和非光滑的非线性结构特点，利用具有良好自适应性的免疫优化算法进行求解。最后结合实例进行分析，获得最优可行解，为决策者提供方案选择。

1 应急物资选址优化模型

1.1 问题描述

灾害事件发生时，制定应急物资调度方案需要对多个应急需求点进行处理，通常情况下一般物资的运输调度只考虑经济效益，但在灾害情况下的应急物资运输调度更大程度上考虑的是时效性。为了实现对某一区域应急需求点和重要高危需求点的全面覆盖，需要解决如下问题：1)应急物资储备库到需求点的时间最少或距离最短，以便在灾害事件发生时能够快速到达应急需求点；2)在模型中引入应急需求点的风险权重系数，保证应急物资储备库设置在风险权重较高的需求点附近；3)每个应急物资储备库的应急救援能力有限，超过其能力范围外，则储备库无法对应急需求点提供应急物资，因此保证任何一个需求点至少有一个应急物资储备库提供应急救援。

模型假设如下：

1)假设接到预警通知后，应急物资储备库马上展开应急行动；

2)各运输工具均满载应急物资正常运行，物资流为单向流，考虑到装卸时间差别不大，因此在模型中不做考虑，只求解最小运输距离；

3)不考虑应急物资储备库到应急需求点的运输费用。

1.2 模型构建

根据以上分析，可建立如下选址模型。

约束条件：

应急物资储备库到应急需求点的距离要满足其应急救援半径的要求，sj为应急物资储备库的应急救援半径，则dij≤sj。

1.3 三角模糊数学理论

由于每个地区的地理位置不同，气候和地壳运动等信息难以预测，使得灾害事件的发生具有较大的不确定性，只能类比该地区已发生的灾害事件来估计该地区的灾害事件区间值，从而得到上述模型中各地区的风险权重系数。三角模糊数就是为了解决不确定环境下的问题，因此先剔除一些非常规异常数据，再利用三角模糊数对各地区往年灾害事件数进行模糊处理。对于三角模糊数A=(a,b,c)，其中：a≤b≤c，a,b,c∈R，则其隶属度为：

(1)

对于三角模糊数的比较，可利用该模糊数的整体期望值进行去模糊化处理[11]。若A是一模糊数，其隶属函数定义如式(1)所示，可知该模糊数的整体期望值为：IT(A)=[IL(A)+IR(A)]/2。式中：IT(A)表示该模糊数的整体期望值；IL(A)代表模糊数的左期望值；IR(A)代表模糊数的右期望值。对于A=(a,b,c)，有IT(A)=(a+c+2b)/4。

2 模型求解

本文建立的应急物资储备库选址模型属于NP-hard问题，精确求解的计算量会随问题规模的增加呈指数形式增长，为避免陷入局部最优解，采用免疫优化算法求解该模型。

免疫优化算法的核心思想是：选择一组任意解，输入目标约束条件，然后随机进行交叉、选择以及变异操作来提高种群进化的自我解决问题的能力，更大程度提高其适应度，避免群体的退化，最终求得全局最优解[12]。它利用免疫系统的整体多样性和个体特异性来保持群体的多样性，避免了在该问题寻优过程中难以处理的“早熟”问题。因此，本文利用免疫优化算法跳出局部最优解和增强算法遍历寻优能力，可以有效而快速地求得应急物资储备库选址模型的最优解或近似最优解。

免疫优化算法流程如图1所示。

2.1 产生初始抗体群

将要解决的问题看作抗原，抗原识别即问题识别，对问题进行分析后，设计出解的合适表达形式。可以采用遗传算法中的简单编码方式，每个选址方案形成一个长度为q的抗体(q表示应急物资储备库数量)，每个抗体表示被选为应急物资储备库的序列。例如，考虑包含32个需求点的问题,1，2，…，32代表需求点的序号，从中选出7个作为储备库。抗体[3,9,14,17,25,28,35]代表一个可行解向量，它表示3、9、14、17、25、28、35被选为储备库。

2.2 解的多样性评价

1)抗体与抗原之间的亲和力。

抗体与抗原之间的亲和力用于表明抗体对抗原的识别程度，针对应急物资储备库选址模型设计了亲和力函数Av，

2)两抗体之间的亲和力。

抗体与抗体之间的亲和力用于表明两抗体之间的相似程度，即Sv,s=kv,s/L。其中：kv,s为抗体v与抗体s中相同的位数；L为抗体的长度。

3)评价解的浓度。

4)期望繁殖概率。

每个个体的期望繁殖概率由Av和Cv两部分共同决定，即P=α(Av/∑Av)+(1-α)(Cv/∑Cv)。其中：α为常数。个体的适应度越高，则期望繁殖概率就越大；个体浓度越大，则期望繁殖概率就越小。

3 算例分析

安徽省作为南北地理交汇的过渡地带，因其特殊的地理位置，天然汇聚低温冷冻灾害、干旱、雨雪冰冻灾害、洪涝、台风以及次生灾害等时有发生[13]。利用本文设计模型和算法对安徽省应急物资储备库选址进行研究分析。该省有16个地级市，要在这些地级市中选择7个地区作为应急物资储备库，为其余9个应急需求点提供应急物资救援(如果在该地区建有应急物资储备库，则该地物资由本地应急物资储备库供应)。

根据建立的模型，需要知道各地区的风险权重系数，利用该地区发生自然灾害等突发事件的历史频率乘以地区人口数并归一化来表示该地区的风险权重系数。由于灾害事件的发生具有很大的不确定性，因此先剔除一些非常规异常数据，再利用三角模糊数对16个地区2010—2017年灾害事件起数进行模糊处理，处理后的历史灾害起数统计见表1。表1中列出各地区人口数量以及各地区的几何中心坐标，在实际运算中将其视为平面坐标，以便计算各地区间的距离。

表1 各地区坐标、风险权重系数及人口数量

根据应急物资储备库选址优化模型，在Window 10系统下，运行内存为8GB的运行环境下，利用Matlab编程，按照免疫优化算法步骤对模型进行求解。求解过程收敛曲线如图2所示。从表2可以看出，随着初始种群规模的增大，迭代次数增加，目标函数值逐渐变小，但同时运行时间也越来越长。当初始种群规模为50，迭代次数增加到300以后，适应度函数值基本稳定。

表2 不同种群规模与迭代次数的运行结果对比

采用免疫优化算法对模型进行求解，选择初始种群规模为50，迭代次数为500次，可以求得较好的结果，此时运行结果为[2,13,6,9,15,3,10]。选出的应急物资储备库与各应急需求点详见图3，图3中方框表示应急物资储备库，圆点表示城市点，若点间有连线表示该点的应急物资由连接的应急物资储备库供应。

从图3可以看出，求解得到的应急物资储备库选址地点分别为阜阳、六安、淮北、蚌埠、池州、芜湖和黄山。经查阅资料可知安徽省现有应急物资储备库分别位于阜阳、六安、淮北、蚌埠、池州及芜湖。求解结果与安徽省现有应急物资储备库选址基本一致，而黄山市地处皖南山区,区域地质环境脆弱,灾害频发，在黄山市建设应急物资储备库，可以有效地弥补救助力量的薄弱区。

4 结论

本文以应急物资储备库到各应急需求点风险加权距离最小为目标函数，建立了考虑时间和安全风险的选址模型，利用免疫优化算法对模型进行求解，并通过实例加以验证。验证结果表明，求解得到的应急物资储备库选址地点与现有应急物资储备库选址基本一致。此外，本文未考虑多种物资的情况以及不同应急物资的优先级问题，并且简略了装卸时间，这些问题都有待于进一步研究。