无人机物流系统设计与优化

佟 刚，陈子超，王 锋，周国庆

（1.沈阳航空航天大学，辽宁 沈阳 110136；2.沈阳航空航天大学通用航空重点实验室，辽宁 沈阳 110136）

1 引言

随着电子商务的快速发展，国内物流产业呈现较快增长。据资料显示，2016年，全国社会物流总额为229.7万亿元；2017年，全国社会物流总额252.8万亿元，同比上涨10.06%，增长速度比2016年提高0.6个百分点[1]。物流业已然成为国民经济发展的朝阳产业，而随着现代交通技术和信息技术的快速发展，物流行业逐渐由传统以海陆运输方式为主转换为现代海陆空立体运输方式，因此发展自动化、智能化的现代物流配送体系是当今物流行业迫切需要解决的问题。其中城市区域及偏远山区的无人机物流方式因其快速方便、不受地面交通及地形影响、实用性强等优点，成为了现代物流发展的新趋势。

无人机物流系统以系统工程为依据，将现代信息技术作为系统核心，整合行业资源，优化配送过程，提高无人机物流系统的经济性和实用性。目前无人机物流系统的实际应用主要存在以下问题：多目标之间的航线规划与约束条件的确定。无人机物流系统航线规划是保证商品在配送过程中高效运行的关键，主要涉及到调度、行程安排和任务路线三个问题。与旅行商问题类似，无人机物流系统航线规划问题为寻找最优路径。

无人机物流系统路径规划为多无人机协同路径规划，可有效提高无人机配送效率。文献[2]将多无人机协同问题转换为车辆路径规划问题，依此建立多无人机协同搜索系统。文献[3]提出在多旅行商问题模型中引入聚类算法进行路径优化。文献[4]利用Du‐bins曲线找到有效节点，结合A*搜索算法来圆滑任务路径。

这里区别于传统单目标路径规划算法[5]，提出针对无人机物流系统，引入多目标优化算法来进行路径规划，将单个物流无人机的路径距离和各个物流无人机路径距离的总和同时作为约束条件，保证在配送路径总和最小的基础上，单个物流无人机的路径距离也最短，得到最优路径，从而使得无人机物流系统更具经济性。同时在多目标优化的基础上，结合遗传算法的全局搜索能力，有效的避免了寻优过程中出现局部最优解，从而保证系统解的多样性[6−7]。

2 无人机物流系统及建模

2.1 无人机物流系统

无人机物流系统是指以无人机为主要运输载体，实现商品从集散点向投递点配送而进行的规划、实施和控制的过程。无人机物流系统主要包括无人机干支线运输系统、区域级无人机配送系统、无人机应急系统和无人机即时充电系统，其中地区级无人机配送系统为该系统研究的重点。无人机物流系统的优点：

（1）配送距离短

物流无人机不会受到地形及地面交通的影响，升空后可直接点对点直线配送，大大节省配送时间。

（2）运营成本低廉

物流无人机在配送时具有较低的运营成本，根据京东运营报告，在系统搭建完成后，商品配送成本将会下降（40～50）%。

（3）配送迅捷

无人机物流系统摆脱了传统地面运输的局限性，由地面运输转换为立体运输，对配送效率有较大提升。

（4）实用性强

根据京东物流报告显示，85%的快递商品重量在2.7kg左右，适合采用无人机进行配送，从而有效降低运营成本。

2.2 无人机物流系统建模

无人机物流系统主要承担商品在配送点之间的配送工作，有M个配送无人机往返于N个配送点之间[8−9]。

对于投递点及无人机物流系统的选择主要考虑以下几点：（1）为简化模型，假设该系统只有一个集散站，并且每个配送无人机以此为每次配送路径的起点和终点。（2）当该系统内含有N个配送点（包括1 个集散点和N－1 个配送点）和M个物流无人机时，要保证N＞M[10]；（3）在一次配送环节中，默认每个配送点（除集散点之外）只会被访问一次[11]；（4）N个配送点之间的物流无人机配送航线是固定的，当两条航线有交点时，分别以不同的航线高度避免碰撞；（5）每个物流无人机的飞行速度是恒定不变的，不受搭载货物重量的影响；（6）同时约束每个物流无人机的配送距离与所有物流无人机的配送距离的总和为最小。

这里所建立的无人机物流系统的空间位置，如图1所示。模型由一个集散点和九个配送点组成，同时由五个物流无人机在各配送点之间进行配送任务。

图1 无人机物流系统空间位置Fig.1 Spatial Location of UAV Logistics System

约束与判断条件的数学表达式为：

目标函数的数学表达式为：

3 遗传算法

遗传算法起源于20世纪70年代，基本思想是依据达尔文生物进化论和孟德尔遗传学说，通过计算机来模拟生物进化过程中的优胜劣汰，得出想要的最优解[12]。其中基因对应优化求解中的变量组合，一个解或解集代表着生物种群中的某一个体。

通过种群个体之间的繁衍，对基因进行交叉和变异来改变个体的表现型（目标函数）。通过模拟自然法则中的优胜劣汰将符合环境要求的表现型的个体保留，若干代之后，种群得以生存于该环境，从而得到问题的全局最优解。遗传算法的一般流程，如图2所示。

图2 遗传算法流程图Fig.2 Flow Chart of Genetic Algorithm

3.1 基因型编码

定义作为起点和终点的集散点的基因代码为0，N－1个配送点的基因代码依次为1，2，…，N－1，在此基础上，增加M－1个虚拟集散点，依次编码为N，…，N＋M－2，虚拟集散点的作用是m号物流无人机配送任务的结束和m＋1号物流无人机配送任务的开始。将上述的基因代码组成一条染色体，即是所有的物流无人机配送航线。将模型带入上述基因型编码规则，即可得模型的基因型编码表，如表1所示。

表1 模型基因型编码表Tab.1 Model Genotype Coding Table

随机生成一条代表无人机物流系统的染色体，如图3所示。

图3 无人机物流系统的随机染色体Fig.3 Stochastic Chromosomes of UAV Logistics System

从该条染色体可以得知五架物流无人机的航线为：

1号物流无人机：0—6—4—0；

2号物流无人机：0—7—9—0；

3号物流无人机：0—3—8—1—0；

4号物流无人机：0—2—0；

5号物流无人机：0—5—0。

但是在种群初始化和变异交叉的过程中，可能会出现以下的情况，这些情况不符合实际情况，所以需要舍弃或重新编译染色体，因此需要在程序中引入检测机制，避免此种情况的发生，提高算法的运算效率。

错误情况一：染色体首位或末位基因型编码即为虚拟集散点基因型编码，此种情况会使得第一架或最后一架物流无人机空飞，降低无人机物流系统的配送效率，如图4所示。

图4 错误情况一染色体示意图Fig.4 Error−1 Case−Chromosome Schematic

错误情况二：染色体相邻两位基因型编码同时为虚拟集散点基因型编码，此种情况会使某一架物流无人机空飞，降低无人机物流系统的配送效率，如图5所示。

图5 错误情况二染色体示意图Fig.5 Error−2 Case−Chromosome Schematic

3.2 种群规模的选择

考虑到优化求解过程中的求解速度和避免局部自由解，一般将种群规模控制在5N左右，这样会加速遗传算法优化求解的收敛速度。

3.3 适应度函数

自然界中的种群竞争往往是由两个方面组成的：种群内部的斗争与种群和环境的斗争。在无人机物流系统的优化求解中，不存在种群内部斗争[13−14]。因此，只需考虑种群与环境的斗争即可。在本模型中，将每一条染色体通过解码器解码后，可直接代入第二节中的目标函数中得到函数值，以此作为适应性评分，即适应度函数为目标函数。

3.4 自然选择

在遗传算法中，最常用的选择方法为轮盘赌法和排名法。

轮盘赌法是通过种群中每个个体的适应度与种群总的适应度的比值大小来选择优秀个体。比值越大，则说明个体越能适应环境，存活下来的可能性越高。数学表达式为：

式中：Pi—第i个个体的淘汰概率；Fi—第i个个体的适应度函数值；∑F—种群适应度函数值的总和。

排名法是将种群个体按照各自适应度值的大小按照一定规则来进行排名，排名越高，则证明在环境中适应性越好，越容易存活。数学表达式为：

式中：Pi—第i个个体的淘汰概率；Ri—第i个个体的适应度函数值排名；5N—种群规模。

两种方法相比，轮盘赌法的算法设计较为复杂且速度较快，但存在使算法丧失解的多样性和造成早熟的风险。而排名法则很好的避免这种风险，因此在这里的模型中采用排名法作为自然选择的方法。

3.5 交叉操作

交叉是遗传算法中极为重要的操作，可以使得后代能够有效继承父代的优良特性，保证种群的稳定性，朝着最优解的方向进化。传统的交叉操作是在种群中随机选择两个个体，然后在染色体结构中随机选择一部分，两随机个体将该部分的基因型编码进行互换，产生新的子代个体。传统交叉操作示意图，如图6所示。

图6 传统交叉操作示意图Fig.6 Schematic Diagram of Traditional Crossover Operation

从图6的操作结果可知，传统的交叉操作会导致个体染色体内出现重复的配送点基因型编码，这与第二节中的（3）号假设相冲突，因此重新定义交叉规则。

在交叉过程中，引入目标函数来作为交叉操作的约束条件，具体操作如下文所示。在初始种群中随机选择某一个体，然后随机抽取另外一个个体，两个个体的基因型编码，如图7所示。1号染色体所代表的无人机物流系统总的配送距离为163，最长的单个物流无人机的配送距离为41；2号染色体所代表的无人机物流系统总的配送距离为177，最长的单个物流无人机的配送距离为47。

图7 随机抽取初始种群中的两个个体Fig.7 Random Selection of Two Individuals in Initial Population

以1号染色体的首位基因型编码作为交叉后代个体母本，对2号染色体的首位基因型编码进行操作，从右到左循环移动2号染色体中的基因型编码，直到两条染色体的首位基因型编码一致。交叉结果，如图8所示。

图8 首位基因交叉操作示意图Fig.8 A Schematic Map of the First Gene Crossover Operation

确定第二位基因型编码。由图1确定1号染色体首位基因型编码和第二位基因型编码之间的距离与2号染色体首位基因型编码和第二位基因型编码之间的距离，记为d（3，2）＝6和d（3，8）＝10，因此有d（3，8）＞d（3，2）。为了满足单个物流无人机的配送距离最短的约束条件，交叉后代个体的第二位基因型编码确定为2。

同理，交叉后代个体的其他位基因型编码也利用此种交叉操作，得到一条全新的个体染色体，如图9所示。交叉操作之后产生的后代个体所代表的无人机物流系统总的配送距离为161，最长的单个物流无人机的配送距离为40。可以看到，交叉操作之后可以有效降低总的配送距离和单个物流无人机的配送距离。

图9 交叉后代个体染色体示意图Fig.9 Individual Chromosome Map of Cross Progeny

3.6 变异操作

变异操作的优劣将会直接影响最终解与全局最优解之间的差距，可以有效增加种群的多元性，避免交叉操作可能产生的局部最优解。

基因突变是染色体上某一位基因型编码的改变。变异操作会使得该条染色体变成它的等位染色体，会引起染色体的表现型改变。这里所采用的变异规则为随机选择某一位配送点基因型编码，然后在该染色体内再随机抽取某一位配送点基因型编码，两者互换位置，形成子代，变异操作示意图，如图10所示。

图10 变异操作示意图Fig.10 Sketch of Mutation Operation

3.7 染色体的解码

染色体的基因型编码组合代表着优化问题的解，但在求解的过程中，染色体不能直接参与计算，需要进行解码。在此模型中，解码矩阵dco为配送点之间的距离矩阵，其中(idco，jdco)元素的含义为配送点idco与配送点jdco之间的配送距离。

以图3中随机生成的染色体为例，进行解码计算。第一步获得染色体中第一架物流无人机航线距离矩阵D1，其中(iD，jD)元素为1的含义为系统内某一物流无人机的配送路径为iD点到jD点，该染色体的的航线距离矩阵D1，如图11所示。

图11 随机染色体可达距离矩阵D1Fig.11 Rando m Chromosome Reachable Distance Matrix D1

同理可得其余四架物流无人机的航线距离矩阵D2、D3、D4和D5，最后可得到该条染色体总的航线距离矩阵D。

第二步将航线距离矩阵依次与解码矩阵元素相乘，求解矩阵的元素和，得出各物流无人机的配送距离和总的配送距离，并依此计算适应度函数的值。

4 程序设计与优化结果

通过第三节遗传算法设计，得到无人机物流系统模型的某些参数值，如表2所示。

表2 遗传算法中的参数值Tab.2 Parameter Values in Genetic Algorithms

图12和图13表明，在500次迭代过程中，这里所设计的遗传算法优化后的结果为无人机物流系统配送距离总和为121，单个物流无人机最大配送距离为42。表3 表明，与传统遗传算法相比，这里所采用的算法，从无人机物流系统配送距离和单个物流无人机最大配送距离来看，得出的结果更加高效，更加符合实际情况。

图12 无人机物流系统配送距离总和Fig.12 Total Distribution Distance of UAV Logistics System

表3 传统优化算法与这里优化算法的对比Tab.3 Comparisons between the Traditional Optimization Algorithm and the Optimization Algorithm in this Paper

算法程序编写过程略结果，如图13所示。

图13 单个物流无人机最大配送距离Fig.13 Maximum Distribution Distance of Single Logistics UAV

5 结论

针对现代物流系统的特点，引入遗传算法对多个物流无人机在多配送目标之间的配送航线进行优化，寻求最优路径。

通过对传统遗传算法的修改，采用单个物流无人机的航线距离和无人机物流系统航线距离的总和作为约束条件，将问题转换为多目标优化，使得优化后的航线距离更短。考虑到实际配送目标的情况，引入检测程序，对不符合的实际情况的方案进行重新编译或舍弃，得到更多的优良后代个体。

仿真结果表明：利用遗传算法对无人机物流系统航线进行多目标优化能够对整个系统的航线距离和单个物流无人机的航线距离进行缩短。从而提高了无人机物流系统的配送效率和物流无人机的利用效率，为现代无人机物流行业发展提供了保障和支持。