重大疫情下贵州省应急物资LRP选址问题研究

Research on LRP Site Selection of Emergency Materials in Guizhou Province under Major Epidemic

摘要: 2020年新冠肺炎的爆发，使得我国应急救援体系遇到了极大考验。尤其是应急物资的分配，作为保障防疫工作开展的基础，科学合理的物资分配十分重要。因此本文在重大疫情背景下，对应急物资的选址–路径问题展开研究，并设计了基于非支配排序的自适应蝠鲼觅食优化算法来对模型进行求解，最终基于贵州省数据来对模型和算法进行仿真，结果表明本文构建的模型与算法具有一定优越性，能够有效解决重大疫情下的物资分配问题。

Abstract: The outbreak of new crown pneumonia in 2020 has made China’s emergency rescue system encounter a great test. In particular, the distribution of emergency materials, as the basis for ensuring the development of epidemic prevention work, scientific and reasonable material distribution is very important. Therefore, under the background of major epidemic, this paper studies the location-path problem of emergency supplies, and designs an adaptive manta ray foraging optimization algorithm based on non-dominant ranking to solve the model, and finally simulates the model and algorithm based on the data of Guizhou Province, which shows that the model and algorithm constructed in this paper have certain advantages and can effectively solve the problem of material allocation under major epidemics.

1. 引言

2020年爆发的新冠疫情给全国的应急救援体系带来了一次重大考验，虽然我国在应急方面都有成熟的预案进行处理，但新冠疫情爆发之突然，传播之快还是让现有的应急体系应对不及。在这次抗疫过程中，应急救援体系出现的问题主要集中在应急医疗资源有限、防疫操作不够规范、应急物资的分配不够合理等方面。尤其是应急物资的分配，兵马未动，粮草先行，应急救援物资是保障一线抗疫医护人员工作开展与安全保障的基础。在疫情扩散时期，各地对应急物资的需求都迅速膨胀，而如何在复杂的情况下科学合地分配应急物资是当下需要关注的问题。

当前，对于应急救援物资分配的LRP问题已经有了较为广泛的研究 [1] - [8] 。对于应急物资分配的决策目标，学者们主要从应急物资需求量、成本耗费、配送效率等方面出发来构建应急物资LRP问题的数学模型，并通过非支配排序遗传算法、模拟退火算法、云粒子群算法等启发式算法来根据实际场景求解模型得到最优结果。张旭 [9] 针对需求不确定下的应急物资分配问题，综合考虑需求量和需求时间的匹配度，构建以综合匹配度均值最大为目标的区间鲁棒优化模型并设计了自适应遗传算法来对模型进行求解。张立 [10] 考虑到多周期救援问题，建立了不确定条件下多周期车辆路径问题的多目标优化模型，并设计改进的蚁群算法来对模型进行求解。虽然目前国内外在应急救援方面的选址路径研究已经较为丰富，但较小从重大疫情的角度来对应急物资分配来展开研究。同时，现有研究在模型构建与算法设计方面仍有改进空间。一方面，在模型构建中，通常适用单目标来构成应急救援路径选址问题的目标函数，无法很好的反应应急决策真实需求。另一方面，在算法设计时，通常使用适用性最为广泛的遗传算法、模拟退火算法等启发式算法，缺乏针对应急物资分配情景下的特定算法，在整体搜索能力与解的优劣方面都有一定欠缺。

2. 模型构建

本研究的目的是构建应急物资分配的多目标数学模型，并通过启发式算法来求解特定情景下的应急物资选址与分配路径，使重大疫情下应急物资的分配能够以尽可能少的成本来尽可能快速的达到对应地点。

2.1. 问题描述

本文研究的问题是，当重大疫情发生时，如何在短时间内确定来援应急物资的存放地点与分配路线。具体包括，如何从众多备选地点选择最适宜的应急物资存放点，并根据不同疫情区域对物资的需求来进行路线规划以尽可能快速的将应急物资运输到对应地点。

2.2. 符号定义

集合：Z——备选中心与物资需求点集合；I——备选存储中心集合；K——物资需求点集合。参数：C_i——在i出开启存储中心需要耗费的费用；dc——单位行驶距离需要耗费的驾驶成本；dis_gh——点g到点h之间的行驶距离；T_k——应急物资到达需求点k的时刻；V——运输车辆行驶速度；Ci——物流中心i的储存物资；Cap-运载车辆的最大装载量；Dk——物资需求点的物资需求量。变量：yi——表示应急储存备选点被选用开启时yi为1，否则yi为0；X_gh——表示当有应急物资在配送过程中从g点到达h点时X_gh为1，未经过时X_gh为0；Q_gh——表示运载车辆从g点运输到h点时所运载的物资数量。

2.3. 模型构建

$F1=\min \left({\displaystyle \underset{i\in I}{\sum }yi\ast Ci+{\displaystyle \underset{g\in Z}{\sum }{\displaystyle \underset{h\in Z}{\sum }{X}_{gh}\ast di{s}_{gh}\ast dc}}}\right)$ (1)

$F2=\min {\displaystyle \underset{k\in K}{\sum }{T}_k}$ (2)

$M{T}_h=X_{gh}\left(M{T}_g+di{s}_{gh}/v\right)h\in Z;g\in Z$ (3)

$T_k=\max M{T}_{k}k\in K$ (4)

${\displaystyle \underset{g\in Z}{\sum }{X}_{gh}}\ge 1h\in K$ (5)

$Q_{gh}\le Capg\in Z;h\in Z$ (6)

${\displaystyle \underset{g\in I}{\sum }{\displaystyle \underset{h\in Z}{\sum }{Q}_{gh}}}={\displaystyle \underset{i\in I}{\sum }yi\ast Ci}$ (7)

${\displaystyle \underset{\text{g}\in Z}{\sum }{X}_{gh}}-{\displaystyle \underset{h\in Z}{\sum }{X}_{gh}}=0$ (8)

${\displaystyle \underset{h\in K}{\sum }{Q}_{ih}}\le Cii\in I$ (9)

${\displaystyle \underset{g\in Z}{\sum }{Q}_{gh}}=D_{h}h\in K$ (10)

${\displaystyle \underset{i\in I}{\sum }Ci}>{\displaystyle \underset{k\in K}{\sum }Dk}$ (11)

$yi=\left\{0,1\right\}i\in I$ (12)

$X_{gh}=\left\{0,1\right\}g\in Z;h\in Z$ (13)

${\displaystyle \underset{g\in Z}{\sum }{\displaystyle \underset{h\in Z}{\sum }{Q}_{gh}}}\ge 0$ (14)

其中(1)式代表模型的第一个目标，即最低的成本耗费，包括运输成本、应急物流中心开启成本。(2)式代表本文的另一个目标，即耗费最短的时间将应急物资运输到需求。(3)式不同批次运载车辆到达需求点处的时刻。(4)式代表需求点k处接收完足量物资的时刻。(5)式保证每个需求点都能够被服务到，(6)式保证运载车辆的运输量不超过运载上限。(7)式保证运输的总应急物资数量不超过储备物资总量，(8)式保证运载车辆的连续性，即驶入必驶出。(9)式保证从物流中心i处运出的物资总量不超过应急物流中心i的储存物资量。(10)式保证每个需求点的需求量都被满足。(11)式保证开启的应急物流中心中储存的物资能够满足需求点需求，式(12)与式(13)为0~1约束，式(14)为非负约束。

3. 算法设计

由于本文研究的问题是经典的NP难问题，并且数学模型涉及了两个目标函数，是典型的多目标规划，因此本文仔进行算法设计时考虑到了这两点因素，分别集合了非支配排序遗传算法与蝠鲼觅食优化算法的有点来组成新的启发式多目标规划算法来对问题进行求解。

3.1. 非支配排序遗传算法

首先是非支配排序遗传算法(NSGA-Ⅱ)，它是解决多目标问题的经典启发式算法。NSGA-Ⅱ是在遗传算法的基础上引入非支配排序与拥挤度的概念，使得算法运行使能够通过不同个体展现的支配关系，与解的分布密度程度来对优秀个体进行筛选。

支配关系是非支配排序遗传算法的核心，在筛选优秀个体时都是从支配层级最高的个体中选择，当层级中个体数量无法满足需要个体时，继续从下个层级选择，而当当前层级中的个体数量超过了需求个数，则引入拥挤度的概念通过公式来计算个体的拥挤程度，优先选择拥挤度较低的个体以保证种群分布的多样性。

对于支配关系的确定，假设存在个体X1与X2，当f1x1 ≥ f1x2且f2x1 ≥ f2x2时(等号不同时存在)则表示个体X1支配个体X2，X2被X1所支配，而当两边等号同时存在，或者当f1与f2不存在同时优于对方的情况时X1与X2不存在支配关系，处于同一支配层级。

对于拥挤度的计算，具体步骤如下：

① 每个点的拥挤度id置为0；

② 针对每个目标，对种群进行非支配排序，令边界的两个个体拥挤度为无穷；

③ 对其他个体进行拥挤度的计算： $id={\displaystyle {\sum }_{j=1}^m\left(\left|f{j}^{i+1}-f{j}^{i-1}\right|\right)}$ ；

其中：id表示i点的拥挤度，fj^{i + 1}表示i + 1点的第j个目标函数值，fj^{i − 1}表示i − 1点的第j个目标函数值。

3.2. 蝠鲼优化算法

蝠鲼觅食优化算法(MRFO)是模拟了自然界中蝠鲼觅食动作而设计的算法，主要包括蝠鲼的链式、螺旋以及翻滚觅食方式，由于其独特的搜索觅食方式，使得蝠鲼觅食优化算法的更新算子在全局搜索能力与局部搜索能力方面具有较高的优越性。但蝠鲼觅食优化算法的更新算子更适用于连续平面的位置更新，而LRP属于离散问题，无法很好的进行求解，因此本文采用了自适应蝠鲼觅食优化算法(AMRFO)，通过随机化处理与自适应函数的引入来解决算法的应用问题，并进一步提高算法的搜索能力与求解效率。自适应蝠鲼觅食优化算法的更新算子如下所示：

自适应的链式觅食更新：

$x_i^d\left(g+1\right)=\{\begin{array}{l}{x}_i^d\left(g\right)+\beta \left[x_{best}^d\left(g\right)-x_i^d\left(g\right)\right]+\epsilon \left[x_{best}^d\left(g\right)-x_i^d\left(g\right)\right],i=1\\ x_i^d\left(g\right)+\beta \left[x_{i-1}^d\left(g\right)-x_i^d\left(g\right)\right]+\epsilon \left[x_{best}^d\left(g\right)-x_i^d\left(g\right)\right],i=2,3,\cdots ,N\end{array}$ (15)

$\gamma =\frac{1}{1+{\text{e}}^{-\left[x_{best}^d\left(g\right)-x_i^d\left(g\right)+10\right]}}$ (16)

$\epsilon =2\gamma {\left|\lg \left(\gamma \right)\right|}^{\frac{1}{2}}$ (17)

自适应的螺旋觅食更新：

r_ran是取值为[0, 1]是随机数，当g/g_max < r_ran时，选择当前最优解为参考位置。

$x_i^d\left(g+1\right)=\{\begin{array}{l}{x}_{best}^d+\beta \left[x_{best}^d\left(g\right)-x_i^d\left(g\right)\right]+\epsilon \left[x_{best}^d\left(g\right)-x_i^d\left(g\right)\right],i=1\\ x_{best}^d+\beta \left[x_{i-1}^d\left(g\right)-x_i^d\left(g\right)\right]+\epsilon \left[x_{best}^d\left(g\right)-x_i^d\left(g\right)\right],i=2,3,\cdots ,N\end{array}$ (18)

当g/g_max > r_ran时，选择随机位置作为参考位置，则有：

$x_i^d\left(g+1\right)=\{\begin{array}{l}{x}_{ran}^d+\beta \left[x_{ran}^d\left(g\right)-x_i^d\left(g\right)\right]+\epsilon \left[x_{ran}^d\left(g\right)-x_i^d\left(g\right)\right],i=1\\ x_{ran}^d+\beta \left[x_{i-1}^d\left(g\right)-x_i^d\left(g\right)\right]+\epsilon \left[x_{ran}^d\left(g\right)-x_i^d\left(g\right)\right],i=2,3,\cdots ,N\end{array}$ (19)

$x_{ran}^d=V_{\min }^d+\beta \left(V_{\max }^d-V_{\min }^d\right)$ (20)

其中 $x_{ran}^d$ 为在第d维生成的随机位置， $V_{\max }^d$ 和 $V_{\min }^d$ 分别为种群中第d维里的上下线

翻转觅食更新：

$x_i^d\left(g+1\right)=x_i^d\left(g\right)+S\ast \left(r2\ast x_{best}^d-r3\ast x_i^d\left(g\right)\right)i=1,\cdots ,N$ (21)

3.3. 基于NSGA-Ⅱ的自适应蝠鲼觅食算法

因此为了更好的对重大疫情下应急物资分配进行选址路径决策，本文在设计算法时，分别借鉴了非支配排序遗传算法的筛选机制与自适应蝠鲼觅食优化算法的更新机制，设计出基于非支配排序的自适应蝠鲼觅食优化算法来对模型进行求解，算法进行步骤如图1所示：

Figure 1. Adaptive manta ray foraging optimization algorithm based on NSGA-II

图1. 基于NSGA-Ⅱ的自适应蝠鲼觅食优化算法

4. 实例仿真

本文使用贵阳市数据作为仿真案例，来模拟重大疫情下应急物资分配的决策。数据包括了各防疫站点的位置分布、应急物资需求量；应急物资储存中心的地理位置、物资储存量。具体数据如表1所示：

Table 1. Specific data

表1. 具体数据

在操作系统为win10，主频为2.7GHz的Inter Core2 i5下，使用MATLAB R2016a对本文构建的重大疫情下应急救援物资分配模型通过基于非支配排序的蝠鲼觅食优化算法进行多次求解，来得出满足目标的最优解集，使管理者能够在满足所有防疫站点的需求基础上，尽可能降低整个过程的成本耗费。

Figure 2. Solution results

图2. 求解结果

从图2可以看出，通过基于非支配排序的蝠鲼觅食优化算法可以得到清晰的pareto最优决策解集，且解的分布较为合理，表面改进后的算法，在搜索能力与求解能力方面在都十分优秀，对求解此类问题时具有一定的优越性。从得到的最优解集中选择两个典型个体其具体路径如图3所示：

Figure 3. Typical individual path map

图3. 典型个体路径图

5. 总结

为解决重大疫情下应急物资的分配，使得分配决策能够在满足防疫点需求的基础上，可以花费尽可能低的成本来高效完成物资分配，本文构建了模拟重大疫情下应急物资分配的多目标数学函数，包括成本耗费目标函数、配送效率目标函数以及约束函数三部分组成。在数学模型构建完毕后，本文设计了基于非支配排序的自适应蝠鲼觅食优化算法，结合了非支配排序算法与自适应蝠鲼觅食优化算法的优点来对模型进行求解，并最后通过贵阳市数据来进行仿真验证，表面算法和模型具有一定科学性，能够对应急物资分配实践起到指导作用。

基金项目

项目编号为gzwjkj2020-1-216。