复杂环境下无人机配送路径优化

张蓓蓓 靳舒葳 由嘉伟 谢晓迪

摘  要：針对偏远地区无人机配送时效差以及配送环境复杂的问题，构建了复杂环境下无人机配送路径优化模型。模型以配送时间最短为目标，不仅考虑了无人机的续航能力、载重能力、载重变化对路径选择的影响，而且还将影响配送时间的环境因素（如风速、风向）考虑在内。为了验证模型的有效性，以湖北某乡村为例设计案例，通过蚁群算法对模型进行求解，并对风速、风向的交互作用进行了情景分析。实验结果表明，在无人机的飞行极限范围内，风速越大对无人机飞行的影响越大，配送时间整体呈现增加的趋势；当风速增加到一定程度时，风向角度变化会对无人机飞行时间产生较大影响。该研究可为复杂环境下无人机物流配送提供理论依据，进而为无人机路径规划研究提供有力支持和参考依据。

关键词：物流配送；蚁群算法；复杂环境；路径优化

中图分类号：TP18；F252 文献标识码：A 文章编号：2096-4706（2023）09-0121-06

Abstract： A model for optimizing UAV delivery paths in complex environments is constructed to address the issues of poor delivery timeliness and complex delivery environments in remote areas. The model aims to minimize delivery time， taking into account not only the impact of UAV's endurance， load capacity， and load changes on its path selection， and also taking into account environmental factors that affect delivery time， such as wind speed and wind direction. In order to verify the effectiveness of the model， a case study is designed using a rural area in Hubei Province. The model is solved using ant colony algorithm and scenario analysis is conducted on the interaction between wind speed and wind direction. The experimental results show that within the flight limit range of UAV， the greater the wind speed， the greater the impact on UAV's flight， and the overall delivery time shows an increasing trend; When the wind speed increases to a certain extent， the change in wind direction angle will have a significant impact on the flight time of the UAV. This study can provide theoretical basis for UAV logistics distribution in complex environments， and thus provide strong support and reference for UAV path planning research.

Keywords： logistics distribution; ant colony algorithm; complex environment; path optimization

0  引  言

近年来，随着技术革新与城市发展，我国物流市场不断扩大，需求量剧增。根据中国年货物运输量数据显示，从2011年至2021十年的时间里，年货物运输量整体呈现稳步增长的趋势，从2011年到2021年年货物运输增长了43个百分点。无人机作为低空空域物流运输的新宠，依托于我国庞大的物流运输市场，拥有广阔的市场背景。相较于传统的物流运输方式，无人机物流运输配送的优势显著。利用无人机配送可以避免传统快递物流运输路线的局限性，运输的效率更高，在一定程度上降低了人力资源和时间成本的消耗。无人机在完成农村配送“最后一公里”难题上具有更明显的优势。但是对于无人机的物流配送，不能忽略配送过程中的复杂环境，这些复杂环境必然会影响到无人机的飞行速度，从而影响整个配送系统的配送时间。

关于无人机系统优化路径算法，仍然是国内外的学者研究的热点，现有路径规划算法主要分为经典算法和元启发式算法，经典算法包括基于搜索的算法如A*算法、D*算法、图搜索法，这些算法在单无人机路径规划问题上表现出良好的性能，但是难以适用于大规模、高维度、非线性的多无人机路径规划问题中，部分学者在此基础上做出了更有深度的研究。例如，宋佳艳利用改进后的蚁群算法解决了自动驾驶多车的协同安全性与轨迹的平滑[1]；赵宏业研究了遗传算法与蚁群算法相结合解决医疗人力资源的调度问题[2]；毛寿祺利用基于细菌觅食-改进蚁群算法解决了水面无人船全局路径规划问题[3]；潘红丽提出改进的粒子群算法用于垃圾清运车的路径规划问题[4]；黄辰[5]、Carabaza[6]等均研究了改进蚁群算法解决路径优化的最短时间问题和停滞问题，以及最小时间搜索规划无人机的飞行轨迹；胡丹[7]等研究了改进精英蚁群算法在未知环境下的机器人路径规划问题，使得改进后的蚁群算法在搜索时具有更好的收敛性和更优的平滑性；Rivera[8]等研究了一种基于蚁群的超启发式排列多目标进化算法，偏好融入多目标后进行模型求解；Nie等将蚁群算法与神经网络算法相融合，提高了解决三维路径的效率问题[9]。虽然许多学者已经对无人机的配送路径优化进行了一系列的研究，但是针对无人机在复杂环境下的配送路径优化的研究相对较少，且实际应用于解决相关行业的路径优化多是以成本最小为目标，对于要求时间最短的路径优化来解决实例的较少。

本文將结合无人机物流配送的特点，研究复杂环境下无人机配送路径的优化，以时间最短为目标建立基于无人机复杂环境下配送路径优化模型，加入自然风、载重对无人机飞行速度的影响，电池续航能力的限制、配送点的需求量等其他复杂条件。通过改进蚁群算法实现无人机配送路径的优化，最后利用实例验证整个物流配送模式的可行性。从而达到高效的配送，提高经济效益以及物流的便捷性。

1  问题描述

对于现在已有的配送服务，农村快递物流配送普遍存在“配送最后一公里”的问题，在农村物流配送中面临着配送链条长、需求分散、配送时间较长的问题，而传统的配送车体积大、成本高、偏远地区配送不到，在一定程度上造成了资源的浪费，使用物流无人机则可以在一定程度上解决这些问题。基于“复杂环境下无人机配送路径优化模型”，假设配送中心有四旋翼货运无人机K架，无人机的载重均为15 kg，最大续航时间为30 min，飞行高度为200 m。对某农村区域需求量不同的L个配送点进行快递配送，每一条路径配送完成后，无人机会返回配送中心进行补货和充电。由于无人机的载重能力和续航能力是有限的，就需要多架无人机进行协同配送。根据各个配送点的需求量，分别选择最优路径进行货物配送。无人机配送模式如图1所示。

在此过程中，无人机的飞行会受到天气情况的影响，比如大风天气会影响无人机的飞行速度；在无人机垂直起落的过程中，载重会大量消耗电池的续航能力，减少续航里程，增长配送时间。随着载重的改变，无人机的配送时间也会发生改变。这些原因造成的时间损耗都会使得客户的满意度和服务体验下降。因此，为了能够缩短客户等待时间，提高用户满意度，就需要对物流无人机进行路径优化研究，建模的优化目标将是无人机物流配送的时间最短。

问题假设如下：

1）假设配送站最多可以用同一型号的无人机K架对L个配送点进行配送，且每个配送站点的总需求量不超过无人机的最大载重量。

2）无人机从配送站出发后，在途中未收到指令的情况下，完成配送后，无人机需要返回配送中心。且所有的配送点都是一站式交付，即无人机在一次飞行工作中同一个站点只访问一次。

3）无人机在配送中心一次性装货，在配送点多次卸货。

4）需要考虑无人机在配送过程中风力和负载对其速度造成的影响。

5）不考虑无人机的飞行姿态，以及无人机在风力条件下的结构变化。

6）在整个配送过程中，无人机均保持恒定的速度行驶，初始阶段的加速与结束阶段的减速均不考虑。

7）不考虑配送过程中鸟类和人为因素的影响。

2  数学模型

无人机路径优化问题的目标主要有时间最短。即无人机在电池续航时间允许的前提下，能够在最短时间内完成配送点的目标配送。对于一架无人机来说，在整个配送过程中的总时间可以由以下几部分相加得到：

其中，式（1）表示总时间的组成部分；式（2）表示无人机在配送过程中的飞行时间；式（3）表示无人机在各个站点起飞和降落的时间；式（4）表示无人机在配送站装货的时；式（5）表示无人机在各个配送点的停靠卸货时间；式（6）为目标函数时间最小化；式（7）表示从配送站出发的无人机的最大数量为K；式（8）表示被派遣参与配送的无人机最终都要返回配送站；式（9）和式（10）表示每个配送点仅有一架无人机进行配送；式（11）表示配送路线上的配送点货物需求总和要小于额定最大载重；式（12）表示每一架无人机到达某个配送点p完成配送后就离开该配送点；式（13）表示无人机配送时的剩余电量足够完成配送；式（14）表示无人机充电后的能量能够满足配送的飞行以及交付任务式（15）和式（16）表示路径选择。同一地点的客户只能一次性配送完成，无人机只能从配送站出发，完成若干个配送点的配送后返回配送站。具体符号说明详见表1。

3  路径优化算法设计

3.1  蚁群算法的原理

经典蚁群算法是DORIGO等[10]通过观察蚂蚁群体觅食行为提出的一种模拟优化算法，主要用于解决最短路径问题，m只蚂蚁中，每一只蚂蚁随机从某个节点出发，或全部从某一选定节点出发，根据轮盘赌法以及信息素浓度来确定蚂蚁将去往哪一节点，蚂蚁会在路径上留下信息素，该信息素与节点之间的距离成正比，所有蚂蚁遍历完所有节点并回到各自出发节点后，完成第一次迭代。经过多次迭代后，即可根据信息素浓度来确定最短路径。

本文的模型涉及类VRP问题，即无人机路径规划或派送问题。考虑无人机装货总量的限制，如果使用传统的蚁群算法，会出现在航程允许的情况下，无人机能够到达某一配送点并返回配送站，但其携带的货物量无法满足该配送点的全部需求量。因此，需要对算法进行改进，首先节点期望程度的公式进行改进；其次，更改蚂蚁经过路径时信息素的增长方式为以时间为主。应用改进后的蚁群算法对模型进行求解。在此过程中，每条配送路线都需要综合考虑无人机的最大航程和最大载重，当无人机的剩余航程或剩余载重无法到达下一配送点，以及到达下一配送点后无法返回配送站时，重新选择除该配送点之外的其他未访问配送点，若均无法满足，则直接返回配送站完成该次迭代。

3.2  计算规则

蚂蚁从i节点移动到j节点的概率计算公式为：

其中，（1-ρ）表示信息素的持久性系数；∆τij表示本次迭代中节点i到节点j路径上的信息素增量； 表示第k只蚂蚁在本次迭代中在节点i到节点j路径上留下的信息素量；m为蚂蚁总数；Q为正常数，用以控制蚂蚁信息素量的积累；Lk为第k只蚂蚁在本次迭代中所走的路径长度。

3.3  计算步骤

计算思路如图2所示。

具体步骤描述如下：

1）初始化参数，令时间t=0，给定蚂蚁数目m、节点数目n、最大迭代次数iter_max、信息素浓度重要程度因子α、节点间期望程度重要程度因子β、信息素挥发程度ρ（0＜ρ＜1）、蚂蚁（无人机）最大飞行时间TIME和最大载重量CAP。

2）初始化节点位置，以及每个节点的货物需求量，包括需求件数和每件货物的质量。计算每两个节点之间的距离，更新距离矩阵D。此后需要根据距离矩阵计算巡航时间。并计算每个节点的货物需求总质量，更新总需求量数组Demand。

3）蚂蚁每到达一个节点，则更新剩余飞行时间Time_res和剩余载重量Demand_res。根据Time_res和Demand_res，判断每只蚂蚁是否能够前往下一节点，如果能，则计算下一节点的选择概率，反之，则下一节点的选择概率为0。直至所有蚂蚁完成所有节点的访问，记完成一次迭代。

4）记录本次迭代的最佳路线，即飞行时间（巡航时间+起降时间+起降额外时间）最短的路径。

5）重置禁忌表、剩余飞行时间、剩余载重量和受载重影响的基础速度。

6）更新信息素浓度。

7）重复迭代步骤2）～6）。

8）达到最大迭代次数iter_max后，比较每一代最佳路径，并输出飞行时间最短的一代路径，作为最终的最佳路径。具体步骤如图2所示。

4  案例分析

4.1  案例介绍

以湖北省某乡村为例，对“复杂环境下无人机配送”的实际情况进行分析。本文选取的乡村共21户人家有快递配送需求，乡村的配送中心配备飞行速度8 m/s，净载重15 kg，续航时间30 min的无人机k架，分别自配送中心出发，对该21户人家进行快递配送服务。由于当地多为丘陵和山地地形，车辆行驶较为不宜，将其作为研究对象具有一定的代表性，可以使得验证结果更加具有说服力。该21个配送点的需求量如表2所示，根据配送中心及配送点的位置坐标，取所在方形区域的中心为原点，以东为x轴，以北为y轴，建立坐标系如图3所示。

4.2  情景设置

本研究以正北方向为极坐标横轴，顺时针方向为正，建立风向坐标系。其中数字1标注为配送中心，其余数字2至22标注为21个配送点应用MATLAB进行算法编程，设置参数值如下：α=1、β=5、γ=2、ρ=0.5，信息素浓度Q=10，蚂蚁总数m=50，迭代次数MAXGEN=100。针对风速和风向对无人机配送的影响，本研究简单模拟两种情景，分别为：

1）风速6.5 m/s，风向45°。

2）風速6.5 m/s，风向125°。

在无人机飞行过程中，将风沿无人机机体轴系分解为沿无人机飞行方向和垂直于无人机飞行方向，沿无人机飞行方向的速度会对无人机的飞行速度产生直接的影响，垂直与无人机飞行方向的速度会导致无人机偏航，在本研究中暂不考虑。

4.3  路径优化结果分析

有风环境下，风速为6.5 m/s，风向为45°，路径规划图与最优路径迭代示意图如图4、图5所示。其中第一架无人机的路线为配送中心→配送点18→配送点8→配送点19→配送点7→配送点16→配送中心，配送时间为1 689.2 s，配送总路程为9 505.08 m。其与无人机的路径规划详见表3。在该种情况下，四架无人机的飞行路径总和为45 939.35 m，四架无人机的飞行时间分别为1 542.18、1 728.72、1 482.33、1 621.72 s，均未超过最大续航时间1 800 s。

有风环境下，风速为6.5 m/s，风向为125°，路径规划图与最优路径迭代示意图如图6、图7所示。其中第一架无人机的路线为配送中心→配送点3→配送点20→配送点5→配送点18→配送点10→配送点15→配送点14→配送中心，配送时间为1 812.95 s，配送总路程为11 178.14 m。其余无人机的飞行路线如表4所示。在该种情况下，四架无人机的飞行路径总和为43 328.58 m，四架无人机的飞行时间分别为1 688.80、1 744.01、1 674.52、1 463.07 s，均未超过最大续航时间1 800 s。

根据运行的实验结果我们可以得出，在风速相同的情况下，通过实验数据分析与无人机路径规划对比，风向125°相较于风向45°的情况对无人机的阻碍更小，通俗来说就是风向45°时无人机飞行更逆风，而在这种情况下无人机配送的时间更长，配送总里程更长；因此本研究可以得出结论，逆风情况更不利于无人机的飞行，增加物流配送的时间和配送里程。

4.4  环境参数对路径优化的影响分析

为了综合分析风速与风向交互作用下对无人机运输路径的影响，本研究依据目标函数与案例分析的实验结果数据，设定风速分别为0、2、4、6、8 m/s。由于当风速大于8 m/s时，环境相对恶劣，本研究使用的物流无人机无法执行飞行任务，故没有考虑。设定风向从0°到360°，每60°为一间隔，并将参数两两组合，进行35组实验，每组实验算法运行10次并取均值，结果如图8所示。从图中可以看出，在风向保持不变时，无人机配送时间整体呈现随着风速的增大而增大的趋势；当风向在0～60°范围，风速大于6 m/s时，使得无人机顺风时巡航速度对航时的影响大于逆风时巡航速度对航时的影响，导致配送时间缩短；当风向在60°～360°范围时，配送时间随着风速的增大而增大；当风速大于5 m/s时，随着风向角度的增大，配送时间呈现增大的趋势。由此可以得出，在本研究使用的无人机的飞行极限条件范围内，风速越大对无人机飞行的影响越大，配送时间整体呈现增大的趋势；当风速较小时，风向对于无人机飞行的影响可以忽略不计，只有当风速增加到一定程度时，风向角度变化会对无人机飞行时间产生较大影响。此外，当风速过大风向对无人机的阻碍过强时，无人机为了保证能够顺利返航，会减少自身的载重来完成配送。因此，在该系统中，风速和风向会对无人机配送路径的选择造成较大的影响。

5  结  论

无人机配送时效性差、秩序混乱是限制其发展的一大难题，且配送的过程中容易受到环境的影响，使得客户满意度降低。本文在传统路径优化模型的基础上，以运输时间最短为目标，包括无人机配送时间、起飞降落时间、卸货时间，综合考虑影响配送的风速、风向、载重等因素，构建复杂环境下无人机配送路径优化模型。针对环境的复杂性，提出影响无人机运行有关的风速、风向的七种假设情景，使用改良的蚁群算法对模型进行求解，并对无人机配送的优化进行规划；最后通过实例验证了模型的可行性。研究结果表明在风向相同的情况下，系统整体呈现出风速越大，配送越耗时越长的趋势，完成配送任务所需的无人机数量增加；在风速相同的情况下，顺风无人机配送的时间更短。

参考文献：

[1] 宋佳艳，苏圣超.基于改进蚁群优化算法的自动驾驶多车协同运动规划 [J].计算机工程，2022，48（11）：299-305+313.

[2] 赵宏业.基于改进蚁群算法的医疗人力资源应急优化调度模型设计与仿真 [J].电子设计工程，2022，30（22）：20-24.

[3] 毛寿祺，杨平，高迪驹，等.基于细菌觅食-蚁群算法的无人船路径规划 [J].控制工程.

[4] 潘红丽.基于改进粒子群算法的垃圾清运车辆低碳路径规划 [D].南京：南京信息工程大學，2022.

[5] 黄辰.基于智能优化算法的移动机器人路径规划与定位方法研究 [D].大连：大连交通大学，2018.

[6] CARABAZA S P，BESADA-PORTAS E，LOPEZ-OROZCO J A，et al. Ant Colony Optimization for Multi-UAV Minimum Time Search in Uncertain Domains [J].Applied Soft Computing，2017，62：789-806.

[7] 胡丹，黄辉，潘梦莎.改进精英蚁群算法在未知环境下的移动机器人路径规划 [J].工业控制计算机，2022，35（11）：119-122+125.

[8] RIVERA G，CRUZ-REYES L，FERNANDEZ E，et al. An ACO-based Hyper-heuristic for Sequencing Many-objective Evolutionary Algorithms that Consider Different Ways to Incorporate the DM's Preferences [J/OL].Swarm and Evolutionary Computation，2023，76：[2023-02-17].https：//doi.org/10.1016/j.swevo.2022.101211.

[9] NIE H B，WANG F C，ZHAO Y. Efficiency Analysis on the Path Optimization of Ant Colony Algorithm Based on Neural Network Optimization [J].Journal of Residuals Science & Technology，2016，13（6）：25-30.

[10] DORIGO A，BIRATTARI M，STUTZLE T. Ant colony optimization [J].IEEE Computational Intelligence Magazine，2006，1（4）：28-39.

作者简介：张蓓蓓（2002—），女，汉族，湖北十堰人，本科在读，研究方向：无人驾驶航空器系统工程。