应急物资储备中心LAP问题的仿真研究

Simulation Research of Emergency Materials Reserve Center Location-Allocation Problem

摘要: 针对灾后应急救援阶段由于储备中心选址不当造成经济损失，受灾点物资分配不均造成救灾秩序不稳定的问题，以最小化受灾点应急物资的最大需求未满足率为公平目标，最小化应急救援总成本为经济目标，构建基于最小最大后悔准则的应急物资储备中心选址–分配(LAP)的整数非线性规划模型。设计一种改进的带精英策略的累积非支配排序遗传算法NDE-NSGA-II求解模型。数值实验表明构建模型和改进算法分别具有良好的鲁棒性和更高的搜索精度。

Abstract: In light of the economic losses incurred due to improper location selection of reserve centers during the post-disaster emergency rescue phase, as well as the uneven distribution of materials at disaster-stricken sites leading to an unstable disaster relief order, it is essential to establish a fair objective: to minimize the unmet rate of maximum demand for emergency supplies at these sites while also reducing overall emergency rescue costs. This economic target is addressed through the development of an integer nonlinear programming model for the location and allocation of emergency material reserve centers (LAP), which is based on the minimum-maximum regret criterion. Furthermore, an improved cumulative non-dominated sorting genetic algorithm with an elite strategy, referred to as NDE-NSGA-II, is designed to solve this model. Numerical experiments demonstrate that both the constructed model and the enhanced algorithm exhibit strong robustness and higher search accuracy.

1. 引言

近些年来，地震、台风、洪水、雪灾等自然灾害给人们生活带来了深远影响，使国家遭受的人员伤亡和经济损失显著增加，促使不同领域的研究人员集中解决应急管理的问题。应急管理通常分为四个主要阶段：缓解、防备、应急和恢复[1]。缓解和防备阶段是灾害发生前的阶段，目的是确定减少、减轻或防止灾害影响的必要措施，并制定灾害发生时执行的行动计划。当灾害发生时，应急和恢复阶段就会发生，应急阶段即干预阶段，是动员和部署灾区内的应急服务，以保护人民，减少人民和物资损失。恢复阶段确定恢复到灾害发生前的措施。本文重点讨论灾后应急阶段，更准确地说是两个重要的相关问题，即物资储备中心选址[2]和物资分配[3]。储备中心选址问题目的是确定灾区所需救援物资分配中心的数目、位置和任务。物资分配主要涉及将物资从储备中心分配到灾区需求点。将两个问题集成起来，即是本文研究的灾后应急物资储备中心的选址–分配(Location Allocation Problem, LAP)问题。

LAP问题[4]目前在应急管理领域已成为一个引人注目的研究热点，国内外学者均对其进行了大量研究，如：龙玉莹[5]等建立以效率最大化的整数规划模型，通过实验验证其有效性，分析并提出管理建议，为灾后应急资源分配提供高效动态决策支持。罗治洪等[6]结合传染病特征和政府隔离措施，建立以加权运输距离最小化为目标的选址–分配模型，设计自适应混合遗传禁忌算法求解，优化配送时效性，结果表明算法性能优于标准遗传算法。Lee [7]等利用遗传算法优化老年人应急服务中心选址问题，旨在缩短老年人出行距离并平衡应急资源分配，研究为城市应急规划者提供了数据驱动的框架。Ghaffar [8]等提出一种双模式配送框架，利用DBSCAN算法聚类传统车辆无法到达的需求区域，优化医疗物资配送路线，进一步通过人工蜂群(ABC)算法与模拟退火技术结合，克服了ABC算法早期局部最优的局限，显著提高了求解效率和质量，研究结果有效提升了危机期间医疗物流的运营效率和服务质量。大规模自然灾害发生初期的不确定性往往导致灾后初期应急物资需求的动态变化和供不应求，决策者在研究物资分配方案实现最大化效率的同时还需要兼顾应急物资分配的公平性，否则可能造成部分灾区灾民人心不稳、秩序混乱，从而造成更多的人员伤亡[9]。杨真真[10]构建多目标应急物资分配和车辆路径优化模型，以隔离点嫉妒值加权和最小化刻画公平性，通过运用NSGA-II和MOPSO算法求解，验证了模型的有效性，进而为突发公共卫生事件下的配送决策提供支持。Mostajabdaveh等[11]研究了灾后救援物资分配与车辆路径规划的双目标问题，旨在最小化基于基尼指数的分配不公平性和总旅行时间，实验表明平衡方法在中等时间限制下有效减少不公平性34%，为灾后救援提供了高效公平的决策支持。

综上可知，诸多学者的研究目标均是基于救援点数量、容量限制、救援效率等，仅从物资分配的公平性和效率性两个角度进行目标权衡，且大多采用已知的比例公平衡量准则，未见较为新颖的优化目标和公平性衡量准则，应急救援过程中的经济成本也是较为重要的目标因素，决策制定不当会导致更大的经济损失，影响救援效率。

本文在上述文献的基础上进行创新研究。首次考虑将公平目标与经济目标进行权衡，引入一种新颖的最小最大后悔准则构建应急物资储备中心选址–分配(LAP)模型，该模型是以最小化受灾点应急物资的最大需求未满足率为公平目标，以最小化应急救援总成本为经济目标的整数非线性规划模型。根据模型特征，设计了一种改进的带精英策略的累积非支配排序遗传算法NDE-NSGA-II。通过对模型的数值实验表明了基于最小最大后悔准则的应急物资LAP模型具有良好的鲁棒性，对比算法的收敛性分析表明了改进的算法具有更好的分布性和更高的搜索理解能力。

2. 问题及模型

2.1. 问题描述

针对灾后初期的应急救援工作，相关应急管理决策者首先会根据当前受灾情况，受灾地区需求点数量等进行应急物资储备中心选址研究，再根据应急物资供应量和需求量等规划应急物资的分配方案。因此，灾后应急物资储备中心的选址和物资分配是救援过程中两个密不可分的阶段，二者的集成优化研究具有更加实际的意义。本文所研究的问题是，自然灾害发生后，如何从公平视角确定各需求点的物资分配数量，从经济视角确定临时应急物资储备中心的选址方案，在有效权衡公平和经济的目标下，使得应急救援经济成本最小和受灾点应急物资最大需求的未满足率最小。

Figure 1. Site selection and allocation for emergency reserve centers diagram

图1. 应急储备中心选址–分配示意图

如图1所示，将某受灾地区分为若干个区域，通过考虑经济因素对每个区域选择出一个物资储备中心对其覆盖范围内的需求点进行物资分配，允许某储备中心将其多余的物资分配给其相邻区域中物资最大需求未满足率未达到最小的需求点，从而最大程度地实现应急物资的公平分配。由图1可知，本文所决策的问题是：在自然灾害发生后的前期响应阶段，如何在考虑应急物资储备中心容量等条件限制下，从经济角度选择建立若干个应急物资储备中心，使应急救援总成本最小，从引入最小最大后悔准则的公平性角进行物资分配，使受灾点应急物资的最大需求未满足率最小。

2.2. 假设条件

考虑模型的普适性，可作出基本假设如下：

模型中考虑的救济分配物资包括食物和水、医疗和卫生包裹、毛毯和布等，这些物品不需要任何特殊的存放设备。

有若干个候选应急物资储备中心、应急物资需求点，一个物资需求点最少有一个物资储备中心来供应物资。

应急物资储备中心的总容量总是可以满足需求点的总需求量。

将某受灾地区可以划分成n个子区域(n ≥ 2)。

2.3. 符号说明

指数：$c=1,2,\cdots ,C$ ——灾后对整个受灾地区进行一定数量的区域划分；

$e=1,2,\cdots ,E$ ——应急物资储备中心中存储的应急物资类型集合；

$a=1,2,\cdots ,A$ ——坐标(a, b)表示分区域中各结点的位置；

$b=1,2,\cdots ,B$ ——坐标(a, b)表示分区域中各结点的位置。

参数：$p_{c,(a,b)}^{\text{zoning}}$ ——若坐标(a, b)的需求点属于分区c，则为1；否则为0。

$s_{c,(a,b),(a\text{'},b\text{'})}$ ——若应急设施储备中心点(a, b)允许服务需求点(a', b')，则为1；否则为0。

$s_{c,(a,b),(a^{\prime },b^{\prime })}=p_{c,(a^{\prime },b^{\prime })}^{\text{zoning}}\cdot p_{c,(a,b)}^{\text{zoning}};\forall c,\left(a,b\right)\in c,\left(a^{\prime },b^{\prime }\right)\in c$

$a{c}_{(a,b)}$ ——坐标(a, b)处作为应急物资储备中心的平均设置成本。

$a{d}_{(a,b),(a\text{'},b\text{'})}$ ——坐标(a, b)与(a', b')的平均距离。

$as{c}_{e,(a,b)}$ ——坐标(a, b)处物资e短缺的平均损失成本。

$\overline{\text{SS}}$——应急物资储备中心存储空间。

$ac{c}_{e,(a,b)}$ ——坐标(a, b)处物资e的平均持有成本。

${\text{MR}}_{e,(a,b)}$ ——坐标(a, b)处对e类型物资的需求。

决策变量：${\text{RC}}_{(a,b)}$ ——若应急物资储备中心位于坐标(a, b)处，则为1；否则为0。

${\text{AM}}_{e,(a,b),(a^{\prime },b^{\prime })}$ ——e类型物资从储备中心点(a, b)运输到需求点(a', b')的数量。

${\text{SQ}}_{e,(a,b)}$ ——e类型物资在储备中心坐标(a, b)处存储的数量。

${\text{MS}}_{e,(a,b)}$ ——储备中心点(a, b)处e类型物资的短缺。

${\text{TUD}}_{e,(a^{\prime },b^{\prime })}$ ——需求点(a', b')处e类型物资未满足的总需求量。

2.4. 模型构建

本文所构建的模型是考虑公平和经济权衡的多目标选址–分配模型。在公平性因素中，首次引入了管理学中的最小最大后悔值决策思想[12]，其基本思想是考虑机会损失值，即当发生某种情景时，决策者从所选择方案的成本与因此放弃的可能是最小的成本之间的差额最小的角度来进行决策选择和制定，其中目标函数F₁即为基于该准则的鲁棒优化目标函数。

$\min F_1={\displaystyle \sum _{e,(a\text{'},b\text{'})}{\text{TUD}}_{e,(a^{\prime },b^{\prime })}\cdot \max \left[{\displaystyle \sum _{e,(a^{\prime },b^{\prime })}{\text{TUD}}_{e,(a^{\prime },b^{\prime })}-{\displaystyle \sum _{e,(a,b)}{\text{RC}}_{(a,b)}\cdot {\text{TUD}}_{e,(a,b)}}}\right]}$ (1)

$\min F_2={\displaystyle \sum _{(a,b)}\left(a{c}_{(a,b)}\cdot {\text{RC}}_{(a,b)}\right)+{\displaystyle \sum _{e,(a,b)}\left(\left(ac{c}_{e,(a,b)}\cdot {\text{SQ}}_{e,(a,b)}\right)+\left(as{c}_{e,(a,b)}\cdot {\text{MS}}_{e,(a,b)}\right)\right)}}$ (2)

s.t. ${\displaystyle \sum _{(a^{\prime },b^{\prime })}{s}_{c,(a,b),(a^{\prime },b^{\prime })}\cdot {\text{AM}}_{e,(a,b),(a^{\prime },b^{\prime })}\le {\text{SQ}}_{e,(a,b)}}\forall c,e,\left(a,b\right)\in c$ (3)

${\text{SQ}}_{e,(a,b)}\le {\displaystyle \sum _c{\text{MR}}_{e,(a,b)}}\cdot {\text{RC}}_{(a,b)}\text{ ; }\forall e,\left(a,b\right)\in c$ (4)

${\displaystyle \sum _e{\text{SQ}}_{e,(a,b)}\le \overline{\text{SS}}}\cdot {\text{RC}}_{(a,b)}\text{ ; }\forall \left(a,b\right)\in c$ (5)

${\text{MS}}_{e,(a,b)}={\text{MR}}_{e,(a,b)}-{\displaystyle \sum _{(a,b)}{s}_{c,(a,b),(a\text{'},b\text{'})}}\cdot {\text{AM}}_{e,(a,b),(a^{\prime },b^{\prime })}\forall \left(a^{\prime },b^{\prime }\right)\in c$ (6)

${\displaystyle \sum _{(a,b)}{s}_{c,(a,b),(a^{\prime },b^{\prime })}\cdot {\text{RC}}_{(a,b)}\cdot {\text{AM}}_{e,(a,b),(a^{\prime },b^{\prime })}\ge {\text{MR}}_{e,(a^{\prime },b^{\prime })}}\forall c,e,\left(a^{\prime },b^{\prime }\right)\in c$ (7)

${\text{MS}}_{e,(a,b)},{\text{ AM}}_{e,(a,b),(a^{\prime },b^{\prime })},{\text{ SQ}}_{e,(a,b)},{\text{ TUD}}_{e,(a^{\prime },b^{\prime })}\ge 0\forall \left(a,b\right)\in c,\left(a^{\prime },b^{\prime }\right)\in c,e$ (8)

${\text{RC}}_{(a,b)}=0\text{ or }1;\forall \left(a,b\right)\in c$ (9)

其中，目标函数(1)为引入最小最大后悔值思想使受灾点应急物资的最大需求未满足率最小，从而满足应急物资公平性分配，实现公平目标；目标函数(2)分别由建立物资储备中心的总花费、物资在中心的总存储成本、物资在中心点短缺造成的总损失三个部分组成，旨在使应急物资救援过程中的成本最小，实现经济目标；约束条件(3)为将应急物资从储备中心运输到需求点的必要条件，其最大物资转移量不能大于物资的存储量；约束条件(4)确保只有储备中心点才可以储备应急物资；约束条件(5)定义了每个储备中心的存储容量限制；约束条件(6)将短缺量定义为每个需求点的供需差；约束条件(7)为非线性约束，确保储备中心供给需求点的应急物资满足需求点的所有需求；约束条件(8)为连续非负变量；约束条件(9)为二元变量。

2.5. 模型转换

由于约束条件(7)是非线性的，为了降低求解难度，因此通过引入一个新的整数变量的线性化技术将其转换为线性形式，可使用式(10)~(15)来定义。

${\beta }_{e,(a,b),(a^{\prime },b^{\prime })}={\text{RC}}_{(a,b)}\cdot {\text{AM}}_{e,(a,b),(a^{\prime },b^{\prime })}\forall e,\left(a,b\right)\in c,\left(a^{\prime },b^{\prime }\right)\in c$ (10)

由此可将约束条件(7)替换为以下5个约条件，重写为线性形式：

${\displaystyle \sum _{(a,b)}{s}_{c,(a,b),(a^{\prime },b^{\prime })}\cdot {\beta }_{e,(a,b),(a^{\prime },b^{\prime })}\ge {\text{MR}}_{e,(a^{\prime },b^{\prime })}}\forall c,e,\left(a^{\prime },b^{\prime }\right)\in c$ (11)

${\beta }_{e,(a,b),(a^{\prime },b^{\prime })}\le {\text{AM}}_{e,(a,b),(a^{\prime },b^{\prime })}\forall e,\left(a,b\right)\in c,\left(a^{\prime },b^{\prime }\right)\in c$ (12)

${\beta }_{e,(a,b),(a^{\prime },b^{\prime })}\le J\cdot {\text{RC}}_{(a,b)}\forall e,\left(a,b\right)\in c,\left(a^{\prime },b^{\prime }\right)\in c$ (13)

${\beta }_{e,(a,b),(a^{\prime },b^{\prime })}\ge {\text{AM}}_{e,(a,b),(a^{\prime },b^{\prime })}-J\cdot \left(1-{\text{RC}}_{(a,b)}\right)\forall e,\left(a,b\right)\in c,\left(a^{\prime },b^{\prime }\right)\in c$ (14)

${\beta }_{e,(a,b),(a^{\prime },b^{\prime })}=\text{integer; }\forall e,\left(a,b\right)\in c,\left(a^{\prime },b^{\prime }\right)\in c$ (15)

3. 算法设计

本文研究内容为一个双目标优化问题，模型中考虑了应急物储备中心的选址及物资分配问题，属于NP-hard问题。为此，我们针对该模型提出一种基于NSGA-II算法进行改进的NDE-NSGA-II算法：该算法首先在引入算术交叉算子的同时，提出并引入一种累积适应度非支配排序策略，采用带有自适应参数的DE算法思想改进初始种群，自适应变异算子将随着进化代数发生变化，以便在突变中找到Pareto解，由此提高了算法的种群多样性和稳定性；然后引入非线性算法思想提高算法局部搜索能力，结合NSGA-II算法和DE算法较强的全局搜索能力，以得到复杂非线性多目标优化问题的全局最优解。

3.1. NDE-NSGA-II算法改进步骤

3.1.1. 累积非支配排序赋值策略

基于NSGA-II算法，该策略不仅考虑了个体的Pareto非支配排序值，还结合了个体周围的种群密度信息。改进型的累积排序适应度策略是重新定义相同级别的非支配排序中的个体适应度分配：个体的非支配排序是支配该个体的所有个体的非支配排序值与该个体当前非支配排序值的总和。首先，Pareto等级与NSGA-II算法中的所有个体相似，获得每个个体的Pareto等级值，设在第g代种群中支配个体x的个体集为：$z{x}_1,z{x}_2,\cdots ,z{x}_n$ ，则个体x的累积排序值可用式(16)表示：

$r{\left(x,g\right)}^{\prime }=r\left(x,g\right)+{\displaystyle \sum _{i=1}^{n}r\left(z{x}_i,g\right)}$ (16)

该策略通过兼顾个体的非支配排序和个体的周围密度信息。对种群的多样性分布提供了有效保证。

3.1.2. 算术交叉算子策略

NSGA-II算法采用SBX交叉算子策略。SBX (Simulated Binary Crossover)交叉算子可以将父级中的优越个体基因继承到下一代的子串中。使子代比父代具有更好的特征，并确保遗传算法收敛于全局最优解，其定义如式(17)所示，其中，λ为参数，与演化代数有关。局限性在于交叉算子具有较弱的全局搜索性能，无法保证种群的多样性。

$\{\begin{array}{l}{X}_s^{g+1}=\lambda X_s^g+\left(1-\lambda \right)X_q^g\\ X_q^{g+1}=\left(1-\lambda \right)X_s^g+\lambda X_q^g\end{array}$ (17)

改进策略令式(17)中的λ值为常数，则称交叉算子为算术交叉算子，该算术交叉算子结合了种群中个体的Pareto非支配排序级别信息和种群中的个体周围密度信息，定义如式(18)所示：

$\lambda =\frac{r\left(q,g\right)}{r\left(s,g\right)+r\left(q,g\right)}$ (18)

其中，$r\left(s,g\right)$ 表示g代中个体s的累积非支配排序分配，$r\left(q,g\right)$ 表示g代中个体q的累积非支配排序分配。因此，交叉算子λ与种群中每个个体的Pareto累积非支配排序水平相关联。可以看出，在算法运算的早期阶段λ值变化很大，而Pareto累积非支配排序值较小的个体在后代个体中占据相对较大的数量。随着演变的继续，种群中的个体倾向于处于相同的Pareto前沿，并且λ的值趋于恒定为0.5。

3.1.3. DE思想改进初始种群

1) DE种群初始化

DE的初始种群也是整个NDE-NSGA-II算法的初始种群。首先随机产生规模为N的初始种群$x_i\left(0\right)=\left(x_{i,1}\left(0\right),x_{i,2}\left(0\right),x_{i,3}\left(0\right),\cdots ,x_{i,w}\left(0\right)\right)$ ，$i=1,2,3,\cdots ,N$ 。每个种群个体由w维向量组成。计算可行解空间的初始变量的公式为：

$\begin{array}{l}{x}_{i,j}\left(0\right)=x_{j\_\min }+rand\left(0,1\right)\left(x_{j\_\max }-x_{j\_\min }\right)\\ i=1,2,3,\cdots ,N;j=1,2,3,\cdots ,w\end{array}$ (19)

其中，$x_{j\_\max }$ 和$x_{j\_\min }$ 分别是搜索j维变量的搜索上界和下界，rand是随机数。

2) DE变异操作

变异操作是使Pareto最优解空间分布均匀化

而满足种群多样性。

从第g次迭代的群体中随机选择3个个体$X_{p1}\left(g\right),X_{p2}\left(g\right),X_{p3}\left(g\right)$ ，且$p1\ne p2\ne p3\ne i$ ，$i\in 1,2,\cdots ,N$ 。生成的变异目标个体向量公式如下所示：

$H_i\left(g\right)=X_{p1}\left(g\right)+F\cdot \left(X_{p2}\left(g\right)-X_{p3}\left(g\right)\right)$ (20)

其中，F为缩放因子，且$F\in \left[0,1\right]$ 。

3) 改进的缩放因子

由于2)知，原始DE算法中参数F是固定的值，主要在0~1之间随机选择，缺乏对其敏感度的研究。而种群中新个体的产生主要依靠变异操作，参数F决定了搜索幅度，因此在提高算法收敛速度和解的多样性方面起到重要作用。通常，优化算法在运行早期主要进行全局搜索得到可行域，找到全局最优解，在运行后期主要进行局部搜索加速算法收敛。基于该策略，将定义改进的参数F如下：

$F=F_{\min }+\left(F_{\max }-F_{\min }\right)\cdot {\text{e}}^{1-\frac{g_M}{g_M-g+1}}$ (21)

其中，F_min和F_max分别表示变异参数的最小值和最大值；g表示当前进化代数，g_M表示最大进化代数。在算法运行初期，自适应变异算子为最大值F_max，可以保持种群个体多样，避免早熟；随着算法运行到中后期阶段，变异算子值逐步降低到接近F_min，可以保留群体的优良信息，避免破坏最优解，进而增加搜索到全局最优解的概率。

4) NSGA-II种群初始化

如果种群个体$X_i\succ P_i$ ，则把X_i加入新种群标记策略N_new中，在个体$P_i\succ X_i$ 情况下，将P_i加入到N_new中，否则，$X_i$ 、$P_i$ 同时被添加入N_new中。N_new种群规模为N~2N，其个体标记策略依据3.1.1节提出的改进累积非支配排序赋值策略和标准NSGA-II算法中的空间拥挤距离实现。因此，N_new是NSGA-II算法的初始种群，即DE优化初始种群的第二次优化，进一步提高Pareto最优解的质量。

求解经典的非线性规划算法较多采用梯度下降法，其全局搜索力较弱，但局部搜索力较强。DE-NSGA-II算法已实现对种群的二次寻优，全局搜索能力较强，但局部搜索能力较。因此，该策略依此作为结合点，在算法运行到中后期采用非线性寻优进行局部搜索，以提高算法收敛效率和全局最优解搜索能力。非线性寻优公式如下所示：

$X_{i,j}\left(g\right)=\text{fmincon}\left(\text{fun},X_{i,j}^{new}\left(g\right),A,b,Aeq,beq,X_{i,j}^{\text{new}\_\min }\left(g\right),X_{i,j}^{\text{new}\_\max }\left(g\right)\right)$ (22)

其中，考虑到算法的效率，当前进化代数g是N (N为10的倍数)的倍数时，执行非线性优化，其中初值$X_{i,j}^{\text{new}}\left(g\right)$ 为经过DE-NSGA-II算法二次全局寻优后的种群个体，通过进一步局部搜索寻优得到问题的全局最优解，从而实现整个NDE-NSGA-II算法流程。

3.2. NDE-NSGA-II算法复杂度分析

假设种群规模为M，算法迭代次数为T_gen，需求点数目为N₁，储备中心点数目为$N_2=N\left(RC\left(a,b\right)=1\right)$ ，则对种群进行累积快速非支配排序的时间复杂度为$O\left(M\right)$ ，算术交叉算子的时间复杂度为$O\left(M{N}_2\right)$ ，变异算子的时复杂度为$O\left(N_1{N}_2^3\log N_2\right)$ ，非线性寻优的时间复杂度为$O\left(N\right)$ ，因此，NDE-NSGA-II算法的时间复杂度为$O\left(T_{\text{gen}}\left(M\left(M+N_2\right)+N_1{N}_2^3\log N_2+N\right)\right)$ ，可以看出，算法的计算量主要与问题规模(需求点数量N₁，储备中心点数量N₂)，算法设定的种群规模M和迭代次数T_gen有关。

3.3. NDE-NSGA-II算法流程图

本文研究改进的带精英策略的累积非支配排序遗传算法(NDE-NSGA-II)，其核心流程如图2所示。首先初始化种群，若终止条件未满足，则引入差分进化(DE)变异算子改进初始种群策略，并标记新种群个体；随后，采用累积快速非支配排序对种群进行分层，结合NSGA-II算法的算术交叉与变异操作增强种群多样性；通过精英选择策略保留优质个体以生成下一代初始种群，并在进化过程中引入非线性寻优策略以提升收敛精度。该算法通过迭代优化实现多目标问题的高效求解，兼具全局探索能力与局部开发能力。

Figure 2. NDE-NSGA-II algorithm

图2. NDE-NSGA-II算法流程图

4. 算例分析

假设某地区发生自然灾害且共有30个受灾点，各个受灾点的位置信息在5000 km × 5000 km的平面上随机生成，各坐标点之间的距离用平面坐标上的欧式距离简化表示。从中选择8个点作为应急物资储备中心点，可根据分区方式计算出$p_{c,(a,b)}^{\text{zoning}}$ 。应急物资需求点及需求量、应急物资类型等主要参数如表1、表2所示。

Table 1. Emergency material demand point parameters

表1. 应急物资需求点参数

seq	(a, b)/km	Total Demand	seq	(a, b)/km	Total Demand
1	(1334, 2552)	2506	16	(3725, 1688)	1498
2	(3665, 1345)	4770	17	(3928, 2189)	5355
3	(4157, 2234)	4498	18	(4071, 2381)	4343
4	(3742, 1480)	4567	19	(3791, 2223)	3856
5	(3478, 1436)	4895	20	(3686, 2588)	5878
6	(3343, 1566)	3437	21	(4029, 2848)	4330
7	(3248, 1251)	3904	22	(4273, 2941)	3979
8	(4205, 4321)	8277	23	(3439, 1917)	3935

续表

9	(4331, 790)	5038	24	(3516, 2386)	3662
10	(4396, 590)	1678	25	(3403, 2653)	4875
11	(3016, 1989)	1946	26	(3449, 3210)	4725
12	(2572, 1766)	4338	27	(2945, 3251)	5510
13	(2798, 1501)	2064	28	(3152, 3561)	6037
14	(2391, 1686)	4073	29	(2556, 2367)	7102
15	(1342, 704)	5324	30	(2788, 2836)	3254

Table 2. Emergency material type

表2. 应急物资类型

Parameter E	ACCe/unit	ASCe/unit
E = 1 (医疗和卫生用品)	15,020	21,020
E = 2 (救援设备)	7020	15,020
E = 3 (食物和水)	11,020	19,020
E = 4 (毛毯和衣服)	3020	15,020

4.1. 计算结果

实验环境为Lenovo (2.5 GHz)，RAM 4 GB，500 G硬盘上运行，操作系统为Windows10，编程工具为MATLAB2016b。参数设置分别为：种群大小为250，最大代数为200，交叉参数为10，交叉概率为1，变异分布指数为50，变异概率为：1/决策变量规模。

如图3所示为算法所得的选址方案，其中应急物资储备中心点的序号按照x坐标的区间范围划分为3个区域依次为：[(14, 29), (28, 25, 2, 17), (22, 9)]。

Figure 3. NDE-NSGA-II algorithm site selection plan

图3. NDE-NSGA-II算法选址方案

如表3所示为该选址方案下的应急物资分配情况。

Table 3. Material distribution plan

表3. 物资分配方案

分区域	应急物资储备中心点	物资分配方案	F1/unit	F2/元
1	14	15	232.433	2.14E+07
		12
		13
	29	1
		30
		11
2	28	27	542.346	5.01E+07
		26
		8
	25	24
		20
	2	7
		6
		5
		16
		4
	17	23
		19
		8
		3
3	22	21	77.467	7.30E+06
	9	10
Total			852.246	7.88E+07

4.2. 算法分析

Figure 4. Comparison of objective function Pareto distributions

图4. 目标函数Pareto分布对比

图4所示为NDE-NSGA-II算法和NSGA-II算法、MOEA/D算法[13]分别求解目标函数的Pareto解分布情况对比。

由图4中Pareto解的分布情况可知，NDE-NSGA-II算法由于其DE改进初始种群策略，提高了前期Pareto解的多样性，算法中间阶段由于改进的累积快速非支配排序策略提高了解的分布性和稳定性，最后由于引入非线性增强局部寻优，使得算法快速收敛到全局最优解，算法整体寻优能力优于另外两个算法。MOEA/D算法由于其快速分解并行求解的思想，使解的分布性和收敛性稍优于NSGA-II算法。

表4所示为三种算法的计算结果比较，由结果可知，NDE-NSGA-II算法对公平和经济两个目标因素的权衡优化结果整体优于另外两种算法。

Table 4. Results of three algorithms

表4. 三种算法结果

三种算法结果对比	NDE-NSGA-II	NSGA-II	MOEA/D
受灾点物资未被满足的最大总需求量(unit)	852.246	1009.402	996.553
建立储备中心总花费，总存储成本和物资短缺造成的总损失(元)	7.88E+07	1.21E+08	1.03E+08

图5所示为三种算法各执行20次的算法效率对比，结果表明，NDE-NSGA-II算法由于加入了改进的初始种群策略、累积非支配排除策略和非线性寻优策略，一定程度上影响了算法效率，但NDE-NSGA-II算法中pareto解的多样性、分布性和稳定性、算法收敛性整体优于另外两种算法，符合算法改进的宗旨，保证算法效率不被严重影响的前提下，最大程度的提高算法寻优精度。

Figure 5. Comparison of algorithm average efficiency

图5. 算法平均效率对比

5. 结束语

针对自然灾害发生后应急物资供不应求、物资分配不均，物资储备中心选址不当等原因造成的救援成本大量损失等问题进行相关研究：1) 引入一种新颖的最小最大后悔准则构建应急物资储备中心选址-分配(LAP)模型，模型考虑最小化受灾点应急物资的最大需求未满足率，最小化应急救援总成本，从而实现对应急救援过程中公平因素和经济因素的有效权衡。2) 设计了一种改进的带精英策略的累积非支配排序算法NDE-NSGA-II对模型进行优化。3) 通过数值实验对三种算法分别所求解的多样性、分布性和收敛性分析表明了改进的算法具有更好的解分布性和更高的搜索解能力。

基金项目

上海市“科技创新行动计划”项目(22YF1415400)；中华人民共和国海关总署科研项目(2024HK296)。

NOTES

^*通讯作者。