基于聚类和免疫算法优化物资管理分配

Optimized Material Management Distribution Based on Clustering and Immune Algorithms

摘要: 本文在生活物资管理的科学发放问题中以优化生活物资投放点的位置和数量，减少投放物资需要的人力指标为目标构建相应的数学模型，为紧急安全事件中大规模封控情况下居民生活物资配送提供预案。为了实现较好的分配结果，我们建立模型计算出各区合理的投放点数量、大规模物资分拣场所数量，通过K-means聚类选出大规模物资分拣场和投放点的地址，使用免疫算法优化配送路径，得出最优分配方案。结果表明该模型能有效解决突发事件中物资分配管理问题，为公共物资资源配置管理提供了新的解决思路。

Abstract: In the scientific issuance of living materials management, this article uses the position and quantity of the placement point of life materials, and reduces the human indicators required for the need for the launch. Delivery provides a plan. In order to achieve good distribution results, we establish a model to calculate the number of reasonable launch points in each district and the number of large-scale material sorting places, select the address of the large-scale material sorting site and the address of the launch point through the K-MEANS cluster, and use the immune to use the immunity, and use the immunity to use the immunity. The algorithm optimizes the delivery path to obtain the optimal allocation scheme. The results show that the model can effectively solve the management of material distribution in emergencies, and provides new solutions for the management of public materials resource allocation.

1. 引言

疫情期间生活物资管理是一项复杂的工程，如果疫情得不到控制全民居家隔离和核酸检测是较好的选择，在疫情初期，没有采购足够物资的居民会产生恐慌，造成一定的管理混乱。然而数据分析显示，在疫情初期政府完全有能力调动足够的生活物资，我们需要制定更加科学的物资管理方案。在众多案例中，发放蔬菜包对居民物资补给起到了一定的作用。蔬菜包主要以新鲜蔬菜为主保质期长且政府有储备，蔬菜无论在数量、频次和影响等方面更为明显，蔬菜的科学供应极其重要。

目前在重大公共卫生事件下应急物资分配的相关研究中应急物资需求量通常来源于需求点对物资的需求量，在新冠疫情期间的物资配送情况存在主观判断，与实际需求量存在差异和信息滞后的问题，随着防控措施的变化与医疗水平的提升，物资分配应该配合实际情况灵活改变，一般投放点物资分配业务面对大批量救灾物资必然会出现物资管理分配不足和投放数量不符合实际的情况 [1] 。

本文在现有研究基础上，以长春市新冠疫情期间蔬菜包发放情况中存在分配混乱、分配能力有限的问题进行深入研究。疫情爆发初期急需要大量的人力资源又同时要尽量减少人员流动，投放点数量需尽量少且能服务所有小区。通过每人每日需要的食物数量对投放点数量合理性进行分析，并通过计算投放点数量模型进行适当优化，主要工作是在物资投放点地址选择和物资配送方式上进行优化，采用K-means聚类和免疫优化算法结合的优化模型，以长春市其中的一个区为例展示了该模型的优化结果，直观的显示了该方法对于应急物资分配有较好的效果。

2. 问题提出和模型建立

2.1. 问题的提出

疫情期间生活物资的管理是一项复杂的系统工程。交警、高速公路管理部门、商务局、邮政部门、防疫部门、民委及市场监管局等均参与其中。通常疫情发现的越早越有利于疫情的防控，然而在实际管理过程中仍会出现疫情发现较晚的特殊情况。如果疫情发现较晚，大量的人群间有了错综复杂的交互，全民居家隔离与全民核酸检测成为了较优的选择。由此产生的大规模居家人群的科学管理成为了新的难点。相关数据分析表明，在疫情期间政府完全有能力调动足够数量的生活物资。只是生活物资发放给社区居民的渠道不畅。因此我们需要制定科学的管理方案来高效应对物资发放问题。

考虑到在疫情初期既需要大量的人力资源又同时要求尽量减少人员流动、接触，投放点的数量显得尤为重要。由于需要充分考虑未来疫情、自然灾害等特殊事件，大规模物资分拣场所需要长期稳定分类储存足够种类的物资。在这里，我们通过k-means对小区进行聚类得到投放点的地址，此时投放点距离各服务小区最近，再对投放点进行聚类得到大规模物资分拣场所的位置。而政府储备物资属于备用场所，通过查找相关数据可得到政府储备物资的规模，再对投放点进行聚类备用场所的位置 [2] (图1)。

Figure 1. Flow chart of material drop point location

图1. 物资投放点选址流程图

2.2. 模型的建立

2.2.1. 数据预处理

在灾情发生之后需要及时的启动物资配送方案，为保障居民正常的生活物资消耗，需要及时收集疫情防控点的物资需求数量，通过合理的分析，及时调整物资分配方案。通过查阅长春市疫情防控期间的相关数据，将收集到的数据可视化。

长春市9个区隔离人口数量与生活物资投放点数量可得到下图2。

长春市9个区交通网络数据和主要小区相关数据可以得到图3和图4。

从上述图表中可以看出，长春市九个区的小区数目和居民人数分布差距较大，依靠有关部门的主观判断会使物资配送投放点的选择不能很好匹配实际情况。从图2中可以看到，二道区和汽开区中每个生活物资投放点对应服务的居民人数分别为4.73万人和2.17万人，服务压力较大，既影响配送速度又不能及时的保障居民的日常生活物资需求；而净月区和绿园区的每个生活物资投放点对应服务的居民人数分别为0.081万人和0.082万人，人数过少造成配送资源浪费现象。从图3和图4可以看到，二道区和绿园区的小区栋数和小区人口数相近，汽开区和净月区的小区栋数和小区人口数相近，说明人均配送的难度相近，但是设置的投放点物资配送难度相差巨大，说明投放点数量配置不合理，需要优化投放点的设置，我们选择先对九个区的分配需求进行模糊评价，经过优先级的排序后再通过K-means选择投放的点位。

2.2.2. 模糊综合评价

首先需要对数据进行归一化处理，公式如下所示：

$\alpha =\frac{x_{ij}}{{\displaystyle \sum \frac{x_{ij}-\min f\left(x\right)}{\max f\left(x\right)-\min f\left(x\right)}}}$ (1)

模糊综合评价步骤如下所示：

Figure 2. Number of people per delivery point of daily necessities in nine districts

图2. 九个区生活物资投放点对应人数(万)

Figure 3. Number of housing estates and buildings in nine districts

图3. 九个区的小区数和小区栋数(个)

Figure 4. Number of households and population in nine districts

图4. 九个区的小区户数和小区人口数

1) 确定因素集

所有因素构成了评价指标体系集合，即因素集，记为U

$U=\{u_1,u_2,\cdots ,u_n\}$ (2)

2) 确定评语集

每个指标的评价值不同会形成不同的等级，由各种不同决断构成的集合称为评语集，记为V

$V=\{v_1,v_2,\cdots ,v_m\}$ (3)

3) 确定各因素的权重

确定一个各因素的权重分配，它是U上的模糊向量，记为A

$A=\left[a_1,a_2,\cdots ,a_n\right]$ (4)

式中： $a_i$ 为第i个因素的权重，且满足 ${\displaystyle \underset{i=1}{\overset{n}{\sum }}{a}_i}=1$

4) 确定模糊综合判断矩阵

对指标 $u_i$ 的评判记为 $R_i$

$R_i=\left[r_{i1},r_{i2},\cdots ,r_{im}\right]$ (5)

各指标的模糊综合判断矩阵为R

$R=\left[\begin{array}{cccc}{r}_{11}& r_{12}& \cdots & r_{1m}\\ r_{21}& r_{22}& \cdots & r_{2m}\\ ⋮& ⋮& \ddots & ⋮\\ r_{n1}& r_{n2}& \cdots & r_{nm}\end{array}\right]$ (6)

5) 综合评价

利用R得到一个模糊变换

$T_R:F\left(U\right)\to F\left(V\right)$ (7)

由此变换，就可以得到综合评判结果 $B=A\cdot R$ 。

2.3. 基于K-Means聚类的选址

K-means算法是一种经典的无监督学习聚类方法。给定一个训练集 $\{x\left(l\right),\cdots ,x\left(m\right)\}$ (其中 $x\left(i\right)\in Rn$ )，将数据分组成几个内聚的“簇”。通过不断迭代逐次更新各聚类中心的值，直至得到最好的聚类结果。K-means算法的基本思想是初始随机给定k个簇中心，按照最邻近选取的原则把待分类的样本点分到各个簇中。然后，按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值 [3] 。K-means聚类算法主要分为4个步骤，如下：

Step 1：随机选取k个点作为初步聚类的中心；

Step 2：计算其他数据到每个聚类中心的距离，将数据归入到与其距离最近的聚类中心的簇中；

Step 3：对这k个聚类的数据计算均值，作为新的聚类中心；

Step 4：继续以上的三个步骤，直到新的聚类中心与上次的聚类中心的值相等时结束算法。

该方法存在k值选取、初始聚类中心选择、及终止条件选取的问题，故要选取合适的方法进行预设。

1) k值选取

对于k的计算方法包括层次聚合、稳定性方法、手肘法等，本文采用手肘法进行k的选取。手肘法(elbow法)的核心指标是误差平方和(SSE)，即所有样本的聚类误差，随着聚类数k的增加样本划分会更加精细，则SSE就会逐渐减小。k小于真实聚类数时，随着k的增加SSE会大幅下降，而达到真实聚类数后，SSE的小降幅度会减小并趋于平缓，也就是SSE和k的关系图是手肘的形状，而肘部对应的k值就是数据的真实聚类。

2) 初始中心的选取

选择适当的初始质心是基本k-means算法的关键步骤。常见的方法是随机选取，但是这样簇的质量常常很差。选取初始质心问题的一种常用方法有多种：

第一种是通过多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE (误差的平方和)的簇集。这种策略简单，但是效果可能不好，取决于数据集和寻找的簇个数。第二种方法是取一个样本，用层次聚类技术聚类。从层次聚类中提取个簇，并用这些簇的质心作为初始质心。该方法通常很有效。第三种是随机地选择第一个点，或将所有点的质心作为第一个点，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。这种方法，确保了选择的初始质心不仅是随机的，还是散开的，但这样可能会选中离群点 [4] 。

3) 算法停止条件

有两种方法来终止迭代，一种方法是设定迭代次数T，到达第T次迭代，终止迭代。此时，所得的类簇即为最终的聚类的结果；另一种是采用误差平方和准则函数，函数模型如下：

$J={\displaystyle \underset{k=1}{\overset{K}{\sum }}{\displaystyle \underset{x_i\in C_k}{\sum }dist\left(x_i,Cente{r}_k\right)}}$ (8)

4) 类簇中心的重新计算

k-means算法每次迭代对应的类簇中心要重新计算进行更新。定义第k个类簇的类簇中心为 $Cente{r}_k$ ，则中心更新方式如下：

$Cente{r}_k=\frac{1}{\left|C_k\right|}{\displaystyle \underset{x_i\in C_k}{\sum }{x}_i}$ (9)

其中， $C_k$ 表示第k个类簇中数据对象的个数，求和是指类簇 $C_k$ 中所有元素在每个属性上的和。

2.4. 模型的求解

经过对比分析九个区域的小区数量，居民人口，新增感染人数等八个相关因素的综合分析，得出关于九个区域的综合评判结果，如下图5所示。

Figure 5. Comprehensive evaluation ranking of nine districts

图5. 九个区综合评价排序

可以看出朝阳区，宽城区，南关区三个区域排名靠前，说明在疫情中受到的影响比较大，并通过每个区域中人口和小区的数量规划食物的需求，对每个区域的投放点数量进行修改分配。通过查阅资料简化模型，我们就以每人(成年人)每日需要900克物资包，假设每一个投放点单日最大物资发放量为4吨进行模型的建立，则每个区的投放点个数N为

$N={\displaystyle \underset{i=1}{\overset{9}{\sum }}\frac{0.0009\times W_i\times {\alpha }_i\times \beta }{4}}$ (10)

其中，表示每个区的权重系数，由上图5得到，考虑到小区人口数中存在的老人儿童等因素存在，我们设置参数 $\beta$ 表示人口系数，在本题中设置 $\beta =0.\text{9}$ 。

由式(10)得出下表1。

根据得到的每个区所需要的生活物资投放点数量进行K-means聚类，投放点地址可视化如下图6所示。

由于需要充分考虑未来疫情、自然灾害等特殊事件，大规模物资分拣场所需要储备足够数量且种类充足的食物。根据长春市疫情期间每日生活物资相关数据，民生商品储备应达到如下标准：成品粮油达到15天(含)以上，肉类方面不低于3天，蔬菜不低于7天。通过各区隔离人数占比可以得到各区保障物资情况，如下表2所示。

通过长春市生活物资情况图可得到长春市大规模物资分拣场所的数量，如下表3所示。

那么，对投放点进行k-means聚类得到大规模物资分拣场所的位置，可视化如下图7所示。

部分大规模物资分拣场所的关键信息如下表4所示。

Table 1. Effects of different grazing intensities on soil moisture at different levels

表1. 各区生活物资投放点数量的优化结果

Figure 6. Drop point address

图6. 投放点位置

Table 2. Life materials guarantee in each district

表2. 各区生活物资保障情况

Figure 7. Large-scale material sorting site address location

图7. 大规模物资分拣场所地址位置

Table 3. Number of large-scale materials sorting venues

表3. 大规模物资分拣场所数量

Table 4. The key information of some large-scale materials sorting venues

表4. 部分大规模物资分拣场所的关键信息

3. 分配案例模型

3.1. 免疫优化算法

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

1) 产生初始抗体群

将要解决的问题看作抗原，抗原识别即问题识别，对问题进行分析后，设计出解的合适表达形式。可以采用遗传算法中的简单编码方式，每个选址方案形成一个长度为q的抗体(q表示应急物资储备库数量)，每个抗体表示被选为应急物资储备库的序列。

2) 解的多样性评价

a) 抗体与抗原之间的亲和力

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

$A_u=1/F_u=1/\{{\displaystyle \underset{i\in N}{\sum }{\displaystyle \underset{j\in M_i}{\sum }{\omega }_i{d}_{ij}{Z}_{ij}-C{\displaystyle \underset{i\in N}{\sum }\min \left[\left({\displaystyle \underset{j\in M_i}{\sum }{Z}_{ij}}\right)-1,0\right]}}}\}$ (11)

其中， $F_u$ 表示新的目标函数；分母中第二项 $C{\displaystyle \underset{i\in N}{\sum }\min \left[\left({\displaystyle \underset{j\in M_i}{\sum }{Z}_{ij}}\right)-1,0\right]}$ 表示对违反距离约束的解给予惩罚，C为常数。

b) 两抗体之间的亲和力

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

c) 评价解的浓度

计算抗体的浓度 $C_v$ ，即 $C_v=\left({\displaystyle \underset{j\in N}{\sum }{S}_{v,s}}\right)/N$ 。其中：N为抗体总数； $S_{v,s}=\{\begin{array}{l}1,S_{v,s}>T\\ 0,\text{others}\end{array}$ ；T为预先设定的一个阈值。

d) 期望繁殖概率

每个个体的期望繁殖概率由 $A_u$ 和 $C_v$ 两部分共同决定，即 $P=\alpha \left(A_v/{\displaystyle \sum A_v}\right)+\left(1-\alpha \right)\left(C_v/{\displaystyle \sum C_v}\right)$ 。其中： $\alpha$ 为常数。个体的适应度越高，则期望繁殖概率就越大；个体浓度越大，则期望繁殖概率就越小。

3.2. 参数设置

本次案例我们选择经开区来进行分析。利用免疫算法模型进行最小距离的计算，参数设置为：种群规模即投放点与大规模物资分拣场所的数量，经开区31(大规模物资分拣场所5个，投放点26个)个坐标值，记忆库容量为10，迭代次数100，交叉概率0.5，变异概率0.4，多样性评价参数0.95，配送中心数就是大规模物资分拣场所数目5，然后得到旧路径与规划好的路径之间的比较，如下图8所示。

因此我们得到两种最短路径方案：

第一种是按照顺时针走向：1—31—1；第二种是按照逆时针方向走：1—2—1。

根据疫情防控要求，希望减少人员的直接、间接接触，对物资运输进行工作量运输距离与货物重量未要求，我们有两类车，大卡车每辆可装10吨，小卡车每辆可装4吨，对于距离投放点较远且人数较多的小区我们利用大卡车长距离运输运送物资，并且发放蔬菜包量是应该多的，这样节省多次的往返运输工作；对于人数少且离投放点较劲的小区，我们采用小卡车运输蔬菜包，这样即使运输总量少，但是因为距离近可以进行多次运输。

Figure 8. Large-scale material sorting places and the shortest path map of the launch point

图8. 经开区某大规模物资分拣场所和投放点的最短路径图

建立目标函数为：总运输费用由两方面构成，一是运输车送货路程，二是车辆大小。总费用如下：

$\min M=m_i{\displaystyle \underset{i=1}{\overset{31}{\sum }}{\displaystyle \underset{j=1}{\overset{31}{\sum }}{g}_{ij}\cdot d_{ij}+t_{ij}}}$ (12)

式中 $m_i=\{\begin{array}{l}4,小货车\\ 10,大货车\end{array}$ ， $g_{ij}$ 为小区蔬菜包需求量， $d_{ij}$ 为运输距离， $t_{ij}$ 是运输时间。

约束条件为

$\text{s}\text{.t}.\{\begin{array}{l}{g}_{ij}=g_0-{\displaystyle \underset{j=1}{\overset{31}{\sum }}{g}_{ij}\left(i=1,2,\cdots ,30\right)}\\ g_{30,j}\ne 0\\ {\displaystyle \underset{i=1}{\overset{30}{\sum }}{g}_{i,31}=0}\end{array}$ (13)

无真实障碍时，各大规模物资分拣场所与投放点的最短路径长度函数例如大规模物资分拣场所m与投放点n之间的距离为

$d_{mn}=\sqrt{{\left(x_m-x_n\right)}^2+{\left(y_m-y_n\right)}^2}$ (14)

3.3. 模型求解

为了使得运输成本最低，偏远小区和小区人口数目多的小区我们采用大卡车运输蔬菜包，并且量多；而在投放点较近的小区，我们运用小卡车多次运输达到我们的运输目的，将此模型进行多目标优化 [6] [7] ，运用Matlab求解，得到运输方案如下图9。

为了清晰直观看出各投放点的运输方案和每天线路的蔬菜包量，整理出下表5。

Figure 9. Transportation scheme roadmap

图9. 运输方案路线图

Table 5. Transportation scheme

表5. 运输方案

我们定义运输车的平均速度为v = 600 m/min，每个投放点下货时间为10 min，每个站点的固定运输车辆为3辆车(2大1小)，得下表6。

如下图10所示，可以直观的看出对于第一种方案，第二种方案部分大规模分拣场所(大规模分拣场所4)用到了三辆车来节省成本(人力、物力)，总共的花费时间就减少了，因此方案2优于方案1。

Table 6. Optimizing transportation scheme

表6. 优化运输方案

Figure 10. The time required for two schemes

图10. 两种方案所需要花费的时间

3.4. 结果分析

通过优化分析，原长春市区生活物资投放点1556个，在保证物资分配力的基础上优化为958个，节省了38%物资投放点建设资源，合理规划每个区投放点数量并且增加了大型物资分拣场的位置选址，可以进一步提高物资配送能力。同时以一个区的物资配送方案为例对比了两种物流模式，结果显示可以节省55%的物流配送时间，模型优化结果良好。

4. 结语与建议

本文充分研究了大规模应急物资分配随着疫情趋势动态变化中出现物资分配不足，分配能力不匹配等问题，提出基于K-means聚类和免疫算法结合优化疫情期间物资分配模型，在保障居民日常生活需求的同时满足资源配送要求。在文中研究了物资投放点位置并制定出详细预案可以实现较好的优化结果，证明本文中优化分配模型可以满足大规模应急物资的实际发放需求，可以在未来的物资分配中提供重要参考。本文只考虑了在疫情爆发前中期物资准备不充足和分配资源紧张条件下以最短分配路径和最少花费时间为目标的优化问题，在疫情发展中后期，由于物流运输逐步恢复，可以进一步考虑再优化分配物资问题。

NOTES

^*通讯作者。