末端无人机物流路径规划研究综述

刘亚京，吕文红，王国娟，梁璐莉

（山东科技大学 交通学院，山东 青岛 266590）

1 引言

近年来，随着物流配送市场需求增大，配送成本升高，给物流配送业带来了极大压力。为满足客户对货物运输更高的要求，各大物流企业相继开展相关研究，试图用更经济、高效的配送方案完成货物运输。无人机凭借自身方便、快捷的特点在物流配送领域占据了一席之地，各大物流企业纷纷加入无人机物流配送的竞争。“干线+支线+末端”三段式空运网是目前物流企业的理想服务场景。由于末端小型无人机本身载重能力、续航能力的限制和物流需求的多样化，造成了整个运输过程成本的增加。合理地规划末端无人机物流配送路径，制定无人机配送方案，对于提高无人机物流配送效率，降低物流企业成本具有非常重要的意义。

2 末端无人机物流路径规划研究现状

2.1 无人机路径规划研究

目前，民用无人机路径规划的研究主要集中在智能避障功能的实现、路径精确跟踪以及多无人机协同路径规划三个方面。

2.1.1 智能避障。近年来，无人机在飞行过程中出现各种碰撞坠毁等事件，解决无人机自主避障问题已经迫在眉睫。马跃涛[1]设计了一种磁感应装置，以检测带电的障碍物，增强对未知环境的适应程度。辛守庭[2]设计的无人机系统能够通过激光雷达获取信息，将信息过滤后发送给无人机，无人机自动绕开障碍物。Allen[3]提出全堆栈动态实时运动框架，采用离线计算范式，依靠最优代价距离运动规划和轨迹平滑实现飞行器的实时规划。Yao等[4]针对无人机在复杂环境下躲避障碍物威胁问题，应用了智能集成诊断系统（Intelligent Integrated Diagnostic System,IIDS），较好地解决了局部极小值问题。Ma[5]和Mannar[6]利用单目视觉检测算法，模拟人眼检测，以确定障碍物位置。吕文红等[7]在井下无人机航迹规划中引入目标点策略，及时对航迹进行修正。张毅[8]提出一种基于双旋Lyapunov 矢量场的无人机避障算法，建立了障碍物回避规则，该算法适用于未知环境下的无人机在线避障。上述研究表明：目前无人机智能避障研究主要集中在设计新型无人机避障系统、运用智能算法规划无人机航迹两个方面，以提高对障碍物距离估计的精度和计算效率，保证无人机作业的安全性和实效性。

2.1.2 路径精确跟踪。路径跟踪系统是无人机系统的重要组成部分，它决定了无人机是否能够按照预设的轨道飞行。陈子昂等[9]提出一种基于曲率圆的无人机路径跟踪制导方法，使用几何方法选择虚拟跟踪点，计算预设路径与实际路径之间最小误差。王勋[10]提出一种基于虚拟力的无人机路径跟踪控制方法，利用虚拟力控制无人机，精确跟踪直线、圆形、变曲率曲线路径。赵述龙[11]采用侧偏距积分法，克服了不同风力和风向对无人机带来的干扰，使用高性能半实物仿真系统验证了提出方法的抗风跟踪性能。程欢[12]研究的四旋翼无人机采用双环控制结构，外环（位置环）采用模型预测控制方法（Model Predictive Control,MPC）以实现位置跟踪，内环（姿态环）采用PID 控制器以实现姿态跟踪。杨 明[13]以部分可观测马尔科夫决策过程（Partially Observable Markov Decision Process,POMDP）为理论框架，建立起无人机路径在线规划模型，采用交互多模型（Interactive Multi-Model,IMM）方法描述无人机移动规律。李秋妮[14]针对多无人机目标轨迹追踪问题设计了目标追踪自适应控制指令，解决了速度与航向角通道系数未知所造成的设计困难，达到了非常好的追踪效果。上述研究的模型实现了对无人机路径的精确跟踪，提高了无人机执行任务的效率。

2.1.3 多无人机协同路径规划。在协同搜索背景下，多架无人机同时从同一个基地出发搜索附近的可疑目标以尽快完成搜索任务。多无人机协同路径规划可以有效提高无人机搜索、侦查等任务效率。李松[15]提出问题转换策略，将多无人机搜索问题转换为车辆路径问题，指导多架无人机对目标区域进行协同覆盖搜索。刘文兵[16]采用一种聚类算法和遗传算法进行分布组合的优化算法，建立多旅行商问题（Multiple Traveling Salesman Problem,MTSP）模型。宋雪倩[17]利用基于Dubins路径的A*算法的多无人机协同路径规划方法，保证了路径的光滑和无人机飞行的安全。刘畅等[18]针对多目标群多基地多无人机协同任务规划问题提出了一种周期性快速搜索遗传算法，构建了多无人机协同侦察任务规划决策数学模型。上述研究的模型和算法提高了多无人机任务执行的效率和精确度。

2.2 末端无人机物流路径规划研究

相对于一般民用无人机路径规划，末端无人机物流路径规划在研究中加入了时间窗限制，能够更加精确地安排无人机配送路线；解决资源限制问题，采用新型燃油发电机、新型燃料氢等延长续航里程。另外，提高末端无人机物流配送效率除了考虑更多的影响因素之外，还可以采用其他的方式：物流配送中心选址和物流路径共同优化的方式，建立“配送车+无人机”的新型末端配送模式。

2.2.1 末端无人机物流路径规划约束要素

（1）时间窗限制。受时间窗限制的物流路径问题是指送货的车辆组织合适的行车路线，在满足客户需求的同时，尽可能达到路程最短、时间最少等。由于受顾客最早开始服务时间和最后服务时间的限制，末端无人机物流路径规划除考虑空间方面外，还需要合理安排时间。

末端物流路径规划的时间窗限制应该考虑三种：软时间窗、硬时间窗、混合时间窗。仪孝展[19]采用遗传模拟退火算法求解了带时间窗限制的路径问题，保证物流配送车辆满足行驶距离和车身容量限制的同时，在规定时间段内将货物配送到客户节点，否则接受相应费用惩罚。刘澜[20]在研究路径问题时，充分考虑了软时间窗对配送业务的影响，将时间惩罚成本作为优化目标之一，并与VRP结合，提出了带软时间窗的车辆路径问题（Vehicle Routing Problem with Soft Time windows,VRPSTW）。侯同娟[21]在乳制品冷链物流配送选址与路径优化问题研究中加入了软时间窗限制，允许物流配送中出现延时情况，提高了物流整体服务质量。史昊[22]结合医药配送中客户对收货时间区间要求严格程度不同，提出软硬时间窗共存的配送路径优化问题，并对无时间窗、单一时间窗与软硬时间窗共存三种情况进行求解比较。研究表明：最优成本、路径数大致与时间窗要求的严格程度成正比。

（2）续航里程限制。传统锂电池无人机受电池容量的限制，续航里程较短，尤其在搭载重物的情况下，飞行时间一般不超过30min。中通快递为应对偏远地区配送问题，研发出第一代末端无人机物流配送系统—普罗米修斯1600A 油电混合物流无人机，创新采用燃油发电机对无人机进行供电，既保留了电动无人机的稳定、安全，同时又提供满载最长1.5h的续航时间[23]。韩国液态氢专家MetaVista 配合智能能源燃料电池动力模块，创造了无人机试飞达10小时50分钟的新记录[24]。燃料氢电池比普通的电池续航能力更长，液态氢及其储存罐重量非常的小，不会为无人机带来很大负担。解决末端无人机的续航里程限制，延长续航时间，充分利用无人机进行末端配送，能够降低整个运输过程的成本。

2.2.2 新型末端无人机物流配送模式

（1）“配送中心+配送路径”共同优化的模式。石梓涵[25]在无人机物流路径规划研究中采用重心法对物流站点进行设计的同时应用遗传算法设计最优路径，选择合适的配送中心位置和最优的无人机配送路径，降低了物流成本。

配送中心是整个物流网络优化节点的核心，在末端无人机物流路径优化过程中，需要将上级配送中心位置的选择和路径优化问题综合考虑。马帅[26]研究的物流配送中心选址及路径协同优化问题（Location-Routing Problem,LRP），既满足了配送中心的最优数量和容量，又可以确定配送车辆的最优路径，是LAP 问题和VRP 问题的集成。侯同娟[21]构建了乳制品冷链物流配送选址—路径优化问题的双层规划模型，上层确定最佳配送中心选址,下层确定最优配送路径，使乳制品冷链物流达到整体系统最优。刘聪[27]针对O2O药品配送选址—路径问题，设计了双层的遗传—蚁群求解算法，采用Halton 序列和记忆库操作对上层遗传算法进行改进。

（2）“配送车+无人机”末端配送模式。针对无人机和货车的最优路由调度问题，国内外一些研究提出了一种新型物流配送模式，在末端无人机物流配送中引入经典车辆路径问题，无人机和配送车合作的形式配送，有效释放人力，同时弥补无人机单独配送在耐力方面的缺陷。

Chase C.Murray[28]将传统旅行推销员问题转变为“飞行伙伴旅行推销员问题”（Flight Partner Traveling Salesman Problem ,FPTSP），运用整数线性规划方法解决无人机与货车协同工作时的最佳客户分配问题。梅赛德斯·奔驰[29]宣布了一款“无人机配送车”概念车—Vision Van，其货舱中不仅拥有自动化的货架和货箱，车顶还带有两架无人机设备，以提升配送效率。UPS[30]在实践中实现了这一概念，已经宣布通过修改其传统的配送卡车，使其实现与无人机交互，成功测试了无人机与卡车的协同配送。Ferrandez[31]等人研究了卡车和无人机协同交付系统中的时间效率和能量效率，考虑将一辆货车携带多架无人机，无人机分别从卡车上发射进行访问，并在访问完成后返回卡车。周浪[32]在研究农村电商配送时，采用“配送车+无人机”模式，充分发挥配送车载重量大和无人机配送速度快的优势。研究表明：采用“无人机+配送车”的方式进行末端配送，能够减少车辆投入和车辆运行距离，延长无人机配送效率，提高末端物流配送的效率。

3 末端无人机物流路径规划存在的问题

3.1 末端无人机物流配送续航里程较短

目前市场上的无人机主要采用锂聚合物电池，续航能力一般在20—30min之间，充电时间超过一个小时，限制了无人机的飞行时间和飞行距离[33]。当电池能量不足时，无人机很难完成飞行，如果没有及时进行能量补给，无人机可能会在中途坠毁。小米无人机在正式发布的当晚直播试飞，直播途中突然摇晃下坠，最终炸机坠落，小米官方解释是电量不足，无人机自动返航[34]。

目前以太阳能作为能量驱动的无人机开始应用，但此类无人机不能全天候进行配送。同时，太阳能电池本身自重较大，很难再装载大批量的配送货物。

末端无人机物流的路径规划主要是合理规划无人机的配送路径，用最少的耗时，最少的耗能，最少的路程来实现节约物流成本的目的。若末端小型无人机的续航里程能够延长，则单次飞行配送的货物会更多，节省回飞充电的时间和路程，降低路径规划的难度，节约配送成本。

3.2 配送回路总数过多

目前，国内外应用于配送的无人机载重一般在15kg 以下[35]。无人机每次携带一定重量的任务从配送中心飞出，由于携带任务重量不同，难以进行合理搭配，导致无人机非满载配送，同一批待配送的货物下无人机的回路总数增加，加大了运输成本投入，延长了货物配送时间。如果能够合理装载货物，充分利用无人机配载容积，提高无人机的利用率，再根据任务目的地进行路径规划，合理安排配送路线，对提高配送效率，降低物流成本具有非常重要的意义。

3.3 地面仓库加大了路径规划的难度

物流配送中心相当于一个临时仓库，客户所需要的货物在此周转，再进行配送，具有集成化、规范化、现代化的特点。目前国内外在研究末端无人机物流路径规划时，都以地面仓库作为无人机配送中心。末端小型无人机在完成一次配送之前必须进行垂直上升、水平飞行、垂直下降运动，这样在进行路径规划时必须考虑无人机携带货物起飞的耗能，加大了末端无人机物流路径规划的难度。如果在规划时忽略垂直起飞的耗能，则实际飞行中，无人机可能会因能量不足而中途坠落，不能按照预设轨迹飞行。如果能够建立一个空中配送中心，无人机携带货物直接从配送中心进行水平飞行，在末端无人机物流路径规划时将不用考虑垂直方向起飞的能耗问题，降低末端无人机物流路径规划的难度。

4 末端无人机物流路径规划发展趋势

4.1 基于智能算法的无人机物流路径规划

末端无人机物流配送路线需要依靠智能算法计算总体飞行路径，不同环境条件下的路径规划算法也有所不同。将全局算法和虚拟力场法结合、环境建模技术与路径规划算法相结合能够设计出适用于特殊环境的无人机物流配送路径。

运用全局算法中的A*算法，在出发点和到达点之间设计一条预设路径，同时采用虚拟力场法进行避障，走出障碍区域之后，再按照预设路径飞行。环境建模技术中的栅格法和蚁群算法结合，栅格法模拟三维无人机飞行空间，模拟蚁群进行试验，将模拟蚁群走的路线应用到实际环境中。以上两种混合算法的应用，能够节省末端无人机物流配送的成本，降低危险系数，具有非常高的实用性。

4.2 满足续航里程约束的基础上进行路径规划

4.2.1 配送车携带充电桩场景下的路径规划。目前在无人机物流配送中，“配送车+无人机”模式的应用越来越多，无人机从配送车上发射，向客户配送货物，完成任务后自动返回货车，进行下一项任务，如图1。2018年深圳科卫泰研制了一款车载无人机仓库系统，能够在移动环境中，辅助无人机精准起降，并根据要求实现充电换电功能。配送车携带无人机和若干货物从配送中心出发，按照预设路径配送，到达站点1 之后，无人机出发完成站点2 的配送任务，配送车继续行驶,完成站点3 的配送任务，最后无人机在站点3 处回到配送车，落入配送车载仓库平台，此时，无人机可以进行无线充电，配送车携带无人机继续行驶，当无人机有配送任务时，继续完成任务，如此循环，直至完成整个配送过程。

图1 “配送车+无人机”配送概念模型

4.2.2 地面巡逻式移动充电站场景下的路径规划。美国允许在边远地区销售移动汽油[36]，根据这一模式，无人机物流公司可以推出移动式充电站。充电站的便利性对无人机物流的应用有很大影响，“巡逻式移动充电站”具有高度灵活性，满足无人机充电需求。开展无人机配送的公司在配送区域内放置若干台移动充电站，构成一个移动充电网络，每台充电站有固定路线，两次经过某一地点的时间间隔固定，方便无人机搜索充电。移动充电站上方设有无线充电平台，当配送无人机自身电量低于某值时，根据系统信息就近寻找移动充电桩充电，充电完成后，继续进行下一项配送任务。当移动充电站自身电量不足20%时，按照预先设置的路线返回仓库充电，充电完成后继续进行巡逻任务。

4.2.3 建立无线充电信号基站场景下的路径规划。华为在2017年提出了“创新城市”[37]这一概念，支持无线充电的信号基站。发展无人机物流的公司和移动公司合作，利用现有信号塔为无人机无线充电，实现不同企业间的互利共赢。建立无线充电信号基站后，进行无人机物流路径规划时，将充电基站作为固定的客户，每一条配送路径中，必须保证有一个充电基站，在此基础上实现路径最优。无人机每次飞行携带若干个任务，在几个任务之间安排无人机飞往充电基站进行充电，设定充电停留的时长，充电结束后继续飞行，完成剩下的任务。这种方法将充电作为一个任务，放入整体中一起规划，相比配送车携带移动充电桩这种场景，无人机不再进行搜索，寻找充电位置，降低了系统的复杂程度，达到无人机物流配送要求。

今后末端无人机物流路径规划研究应该在保证续航里程基础上进行，能够降低路径规划难度，避免无人机因续航里程不足而坠毁，提高无人机物流的安全性，降低整个运输过程的成本。