基于NSGA-2的无人机配送中心选址优化

Location Optimization of UAV Distribution Center Based on NSGA-2

摘要: 以无人机物流配送中心选址问题为研究对象，结合其选址特点构建含有固定建设费用、存储管理费用、运输费用等成本要素的目标函数，建立了基于快速非支配排序遗传算法NSGA-2的选址模型进行求解，揭示了不同目标之间的Pareto最优解之间关系。最后，假设以天津市建立防疫物资无人机配送网为例，给出了优化方案，从而验证了模型的正确性。

Abstract: Taking the location problem of UAV logistics distribution center as the research object, combined with its location characteristics, an objective function containing fixed construction cost, storage and management cost, transportation cost and other cost elements is constructed, and a location model based on fast non dominated sorting genetic algorithm NSGA-2 is established to solve the problem, revealing the relationship between Pareto optimal solutions of different objectives. Finally, taking Tianjin as an example to establish a UAV distribution network for epidemic prevention materials, the optimization scheme is given to verify the correctness of the model.

1. 引言

由于无人机在大多数场景下都可以直线飞行，相比于传统的配送方式，具有配送距离短，速度快等特点，但是无人机也有着负载低，续航差等特点，所以无人机配送网的建立，关键一步就是建立覆盖范围适合、配送距离满足无人机续航特点的配送中心。与传统的物流配送中心不同，考虑无人机的运行特点和运输成本，无人机的配送中心选址具有独特的特征，具体表现在：1) 配送路线的变化；2) 多配送中心并存；3) 涉及各种资源成本的限制。建立合适的配送中心是一个MOP难题，为此很多学者针对该问题进行了研究以提高配送中心选址的优化，提升配送效率。

2. 文献综述

目前，针对物流配送中心选址的国内外研究主要以传统运输方式为主，目标函数分为：单、多目标；约束条件分为：确定和不确定，其中：刘海燕等 [1] 主要分析物流系统中库存管理、运输、配送中心之间的联系，应用最优化方法建立了物流配送中心选址的数学模型。并给出了按BENGERS 方法设计的求解算法。秦固 [2] 提出了一种解决多物流配送中心选址问题的蚁群算法模型，关菲、张强等 [3] 综合考虑了模糊环境下影响物流配送中心选址的各因素，建立了以物流总费用最少，物流配送中心综合服务水平最高为目标的模糊多目标物流配送中心选址模型。而针对无人机配送中心选址的有陈刚、付江月 [4] 对军民融合背景下无人机配送中心选址问题进行了研究，建立了一个以网络总里程最小为目标，以投资预算、规模效益、网络抗毁性等为约束条件的纯整数线性规划模型。在算法设计方面，配送中心选址常用的启发式算法有，重心法 [5] [6] [7] [8] [9]、蚁群算法 [10] [11] [12] [13]、模拟退火算法 [14] [15]、遗传算法 [16] [17] [18] [19] [20] 等。

由上可知，现有研究主要不足在于：现有配送中心选址研究主要以传统运输方式为主，较少有针对无人机配送方式下的研究。而随着无人机在配送领域的逐渐普及和发展 [21]，针对无人机配送模式下配送中心选址的研究是有意义的。

综上所述，本文研究无人机配送模式下的配送中心选址MOP问题，以初期建设无人机配送中心的固定成本和后期的运输、储存成本为目标，综合考虑无人机配送续航距离限制，设计该问题的NSGA-2，定义染色体编码、产生初始种群的启发式算法、遗传操作等。最后，假设以天津市建立无人机配送防疫物资为例，给出了最佳选址方案，从而验证模型和算法的有效性。

3. 无人机配送中心选址模型构建

3.1. 问题描述

无人机配送中心选址问题模型为：在某个地区有若干个配送中心备选点和若干个需求点，已知各个无人机配送中心备选点的固定建设费用、物资单位储存费用和库存容量，及各个需求点的需求量，同时知道备选中心距各个需求点的距离矩阵。现在该地区若干个配送中心备选点中选择部分作为配送中心，满足该地区所有需求点的需求，同时配送中心容量和大于各需求点需求量总和，并使得配送中心建设的固定费用和后续配送的储存及运输费用最少。

根据问题特征，建立NSGA-2的双目标数学规划模型，寻找其Pareto最优解，从固定建设费用角度和后期使用角度探寻不同优化方案对利益均衡性的影响。

本文的前提假设条件为：

1) 仅在给定的配送中心备选点中选择一部分建立配送中心。

2) 运输费用与运输距离成正比。

3) 配送中心的容量有限。

4) 选取的配送中心的容量必须满足各需求点需求量总和。

5) 各需求点的需求量已知。

6) 一个需求点只由一个配送中心配送。

3.2. 数学模型

假设有n个需求点，现从m个备选地中选取若干个建立配送中心，使得配送中心建设费用及储存、运输费用最少。

为了建立数学模型，各变量定义如下：

n：需求点个数；

m：配送中心备选地个数；

$D_j$ ：第j个需求点的年需求量；

$x_{ij}$ ：配送中心i为需求点j供应的货物量；

$h_{ij}$ ：从配送中心到需求点的单位运费(包括装卸、运输费)；

$F_i$ ：在第个备选点建立配送中心的年固定建设费用；

$c_i$ ：在第i个配送中心存储单位货物的存储费；

$s_i$ ：第i个配送中心容量上限；

$y_i=\{\begin{array}{l}1,在备选点i建立配送中心\\ 0,不在备选点i建立配送中心\end{array}$ ；

$Z_1$ ：初期固定建设费用；

$Z_2$ ：后期运输成本和储存费用。

目标函数：

$\min Z_1={\displaystyle {\sum }_{i=1}^m{y}_i{F}_i}$ (1)

$\min Z_2={\displaystyle {\sum }_{i=1}^m{\displaystyle {\sum }_{j=1}^n{h}_{ij}{x}_{ij}}}+{\displaystyle {\sum }_{i=1}^m{\displaystyle {\sum }_{j=1}^n{c}_i{x}_{ij}}}$ (2)

约束条件：

1) 各个需求点的需求量必须得到满足。

${\displaystyle {\sum }_{i=1}^m{x}_{ij}}\ge D_j,j=1,2,\cdots ,n$ (3)

2) 选定的配送中心配送量不能超过其容量。

${\displaystyle {\sum }_{j=1}^n{y}_i{x}_{ij}}\le s_i,i=1,2,\cdots ,m$ (4)

3) 在m个备选地中选取t个建立配送中心。

${\displaystyle {\sum }_{i=1}^m{y}_i}\ge t$ (5)

4) 如果一个备选地为某些需求点提供货物，则需要在该地建立配送中心，其中M是一个很大的正数。

${\displaystyle {\sum }_{j=1}^n{x}_{ij}}\le M{y}_i,i=1,2,\cdots ,m$ (6)

5) 各变量的取值限制。

$x_{ij}\ge 0,y_j=0,1;i=1,2,\cdots ,m;j=1,2,\cdots ,n$ (7)

6) 本文中考虑了无人机的航程问题，设置无人机配送的最远距离为20 km，如果配送中心距离需求点的距离超过最远距离，设置运输费用惩罚值，同时该配送中心固定建设费用设置惩罚值。

4. NSGA-2算法设计

NSGA-II是Srinivas和Deb于2000年在NSGA的基础上，拓展了快速非支配排序算法、拥挤度和拥挤度比较算子，有效降低了算法的计算复杂度，而且Pareto域中的个体能均匀地扩展到整个解域，保持了种群的多样性，进一步提高了计算效率和算法的鲁棒性。NSGA-II已成为进化多目标优化领域的基准算法之一，被广泛应用在物流、生产调度等领域。

借鉴NSGA-II在选址问题的成熟研究经验，本文直接利用NSGA-2求解该多目标问题，根据问题的特点，定义了染色体编码，并设计了染色体解码的启发式算法，并给出了具体算法过程。

4.1. 染色体编码

由问题描述可知，问题求解核心在于变量 $y_i$， $y_i$ 决定了选址中心的固定建设费用及需求点分配，利用一维向量Y来表示问题的每一个解，其中 $Y=\left(y_1,y_2,\cdots ,y_m\right)$ 中元素 $y_i$ 取值为1或0， $y_i=1$ 表示第i个备选点被选为配送中心， $y_i=0$ 表示第i个备选点未被选为配送中心。例如一个染色体={1 0 0 1 0 1 0 0 1 0}表示备选中心1、4、6和9被选为配送中心。

4.2. 染色体解码

对于每个随机生成一维向量Y，确定了 $y_i$ 的具体值之后，就确定了配送中心的选址结果，但是需求点与配送中心的对应关系即染色体的表现形还没有确定，为此，设计启发式算法生成可行个体组成初始种群，具体的步骤如下：

步骤1：对于选中的配送中心i，首先计算选中的配送中心容量和 ${\displaystyle {\sum }_{i=1}^m{y}_i{S}_i}$ 是否大于 ${\displaystyle {\sum }_{j=1}^n{D}_j}$，如果大于则进入下一步骤，如果不大于则双目标函数值为INF。

步骤2：对于选中的配送中心i，查找距配送中心i距离较小的需求点集合 $U_i$，在 $U_i$ 中将满足容量的需求点分配给该配送中心，同时要求遵循 ${\displaystyle {\sum }_{j=1}^n{y}_i{x}_{ij}}\le s_i,i=1,2,\cdots ,m$，建立初步的配送任务分配关系。

步骤3：对于没有分配的需求点，首先查找剩余容量大于该需求点需求量的被选配送中心，再从中选择出距离最近的，建立配送关系。

步骤4：查找是否有需求点没有被分配，如果是，转至步骤3。

步骤5：根据表现形(任务分配关系)得出该个体的适应度函数值z₁和z₂。

4.3. 算法流程

NSGA-2的具体算法步骤见图1：

随机生成初始种群父群，再对父群进行非支配排序和拥挤度计算，然后进行选择、交叉、变异操作，生成一代子群，然后父子代合并进行非支配排序和拥挤度计算，通过淘汰个体，选择优秀个体组成新父代，重复上述操作，直至终止条件成立。

Figure 1. NSGA-2 algorithm flow diagram

图1. NSGA-2算法流程示意图

5. 算例分析

5.1. 问题背景

当前新冠疫情严重，防疫压力严峻，无人机在非接触配送中优势明显，尤其是对于防疫药品等急需物资配送来说具有速度快、反应及时等优点。

假设在天津市建立无人机配送防疫物资服务，现有10家大型三甲医院准备作为无人机配送中心建设待选点，天津市20家中小型医院作为需求点，建立无人机配送中心选址模型。根据天津市医院的地理位置和规模大小，模拟当地防疫物资需求算例。如下所示，需求点名称、经纬坐标及需求量见表1，待选中心名称、经纬坐标、容量、固定建设费用与物资单位储存费用见表2，待选中心与需求点直线距离矩阵见表3。现采用NSGA-2算法从10个待选中心中选择若干个建立配送中心，使得选中的配送中心总建设费用和后续运输、储存成本最低。

Table 1. Demand point sequence numbers and latitude and longitude coordinates

表1. 需求点序号与经纬度坐标

Table 2. Relevant parameters of the center to be selected

表2. 待选中心相关参数

Table 3. Distance matrix between the center to be selected and the demand point (unit: km)

表3. 待选中心与需求点距离矩阵(单位：km)

5.2. 仿真结果

本文利用matlab编写求解选址问题的NSGA-2算法，相关参数设置为：最大迭代次数500，染色体数50，交叉概率取0.8，变异概率取0.05。在经过NSGA-2算法的处理，达到预定迭代次数后，得到了以下3个候选结果，见图2~4。

表4中的结果表明，三个候选结果被选中心数量均为3个，且三个候选结果中z₁、z₂相差不大，在NSGA-2算法中属于同一代数，达到预定迭代次数后的Pareto解集图见图5：

Figure 2. Candidate results 1 (3, 6, 10 for selected centers)

图2. 候选结果1 (3，6，10为被选中心)

Figure 3. Candidate results 2 (3, 8, 10 for selected centers)

图3. 候选结果2 (3，8，10为被选中心)

Figure 4. Candidate results 3 (6, 8, 10 for selected centers)

图4. 候选结果3 (6，8，10为被选中心)

每个候选结果对应的目标值见表4。

以候选结果3为例，具体参数如下：候选结果3以3、6和10作为配送中心，即选择天津医院、天津医科大学口腔医院和天津医科大学总医院为配送中心，此方案的固定建设费用为69000元，后续运输和储存费用为52815每年，该配送方案选址中心的覆盖范围见表5：

Table 4. Target values for candidate results

表4. 候选结果的目标值

Figure 5. Pareto solution set diagram

图5. Pareto解集图

Table 5. Candidate 3 distribution center coverage

表5. 候选结果3配送中心覆盖范围

从表5可知：

1) 该算法求解的三个候选结果均为3个配送中心，说明3个配送中心是该案例中满足各项需求的最低配送中心数量。

2) 初期固定建设费用与后期运输储存成本是相互制约的，该算法能在众多可行解中求出非支配解，满足各个需求点医院的物资需求，同时做到各项成本最低，候选结果如表5所示，该方案最大程度利用了每个配送中心的容量，符合配送中心选取的要求。

3) 在配送中心数量的选择上，本文提供的算法能够自动迭代、选择出配送中心数量最少、总容量符合总需求量并且固定建设费用最低的方案。

4) 当非支配解集出现了不同的最终候选方案，从配送经营者的角度，需要进一步考虑除初期建设费用和后期运营成本以外的因素，在非支配解集中选择成本最低、获利最大的方案。

综上所述，该算法运行结果得到的配送中心选址方案基本满足了要求。

6. 结论

本文分析了无人机配送中心选址并建立配送关系的优化问题，建立了相应的多目标优化模型，综合考虑无人机配送距离限制、配送中心容量限制、需求点需求必须被满足等约束，最后设计了一种无人机配送中心选址算法，寻求初期固定建设费用和后期运营的运输、存储费用的最佳权衡关系，得出选址的最优解集。结果表明：NSGA-2在解决多目标优化的问题中，该算法能选出较优的配送中心，有效降低成本，同时降低了非支配排序遗传算法的复杂性，具有运行速度快，解集的收敛性好的优点。

影响无人机配送中心选址的因素还涉及了很多方面，本文仅从初期建设成本和后期运营成本角度提出目标函数，没考虑待选点的空域情况、无人机的性能参数、环境的干扰等不确定性因素。因此，如何考虑更多的相关不确定因素进行配送中心选址，仍然是一个未来值得探讨的研究方向。

基金项目

中国民航大学大学生创新训练计划项目(IECAUC2021016)。