“最后一公里”配送的分布式多无人机的任务分配和路径规划

      1 引言

      2014年习近平总书记在党的群众实践大会中指出“最后一公里”的内容与指导意见，其宗旨是要积极主动解民难、排民忧、顺民意.基于此背景下，“最后一公里”在物流交通领域的应用与研究主要有：快递配送与路径规划，共享单车选址与定量分析，仓库设置与布局等。

      本文从快递配送与路径规划角度出发，利用提出的两种算法，获得分布式无人机编队与运输车联合协作的最优分配方案与路径.分布式无人机(unmanned aerial vehicle，UAV)编队取送货物，是利用多个UAV通过分布式计算获得理想的分配方案后向指定区域对物品进行配送与拾取.近年来，随着物流业的高速发展，UAV的应用极大地提高货物配送效率与准确性，并降低配送成本，为用户提供更好的服务与体验，它成为解决“最后一公里”交付问题的新型运作模式.因此，研究UAV的任务分配与路径规划具有重要意义。

      2011年，美国Matternet公司在多个国家与地区研究UAV交付医疗用品与标本的项目[1]；2013年，亚马逊宣布UAV交付计划，并于2015年提出终端配送30分钟交付准则[2]；2014年，谷歌启动Wing-UAV交付项目，其特点在于配送过程中使用消息、面部识别、远程控制等技术，使配送更加准确[3]；2016年，澳大利亚的DHL公司成功测试使用UAV运送小包裹[4]；2017年，亚马逊为UAV内置集成定位系统与降落伞，使包裹能够安全准确着陆且不易损坏[5]；2018年，中国企业饿了么宣布第一批送餐UAV正式投入商业运营[6]；此外，UAV更多的应用在电力巡线、搜索及救援、遥感测绘、农业作业等放，并且如图1(a)所示，且国内的一些企业掌握的控制技术已达世界领先[7].UAV的配送作业在国内的广州、宁波、上海等地已投入使用，图1(b)为运输车与UAV的联合操作和自助取货。

      运输车与UAV联合操作步骤有：1)根据文中提出的区块链式拍卖算法进行任务分配成本核算，运输车将获得适宜的位置停靠为UAV进行货物配载与指令设置；2)UAV按分配方案进行取送货物，并根据设置的路径规划方法完成飞行避碰操作；3)UAV到达指定智能存放柜卸载或取货后返回运输车，存放柜对配送的货物进行信号标记并产生编号与二维码，同时发送给取货人，取货人凭借货物编号或二维码来完成自助取货；4)当最后一个UAV完成配载后，运输车驶向下一停靠位置，未收回的UAV将追赶或跟随运输车，二者在下一停靠点集合，并继续完成货物配取工作；5)取货任务在第一次配送任务完成后开始执行，最大程度上减少UAV携带货物追赶或跟随运输车的情况.

      在研究常见的任务分配问题时，其计算方法通常是利用带有市场机制的拍卖算法.该算法原理是将逐层的拍卖奖励作为回报映射给拍卖者，最后使所有拍卖的产品获得总收益最大，若中途有人放弃，则会在现有的任务层取消并继续拍卖，最后把决策中心系统的计算结果分配给每个出价人，使拍卖者在当前层总回报奖励最高，即分配总成本最低.市场机制条件，拍卖算法具有灵活性好，鲁棒性强和可伸缩性等优点，因此在任务分配的研究中受到广泛关注与使用[8].然而，禁忌搜索算法，人工神经网络，遗传算法等也可处理任务分配问题[9]，但此类算法很难适应动态市场机制[10]，只能处理特定约束的分配任务.在对市场机制下的有限通信，时间约束，组合拍卖，异构代理等此类具有动态限制特性的问题处理时，启发式算法需要对约束拆解并重新迭代计算，其求解灵活性弱于拍卖算法[11]。

      

      图1 无人机的用途及其与运输车的联合操作和自助取货

      UAV路径规划是在确定任务分配方案和取送货物的初末位置基础上，对分布式UAV编队进行路径控制，并确保UAV飞行路径合理与安全.在求解路径规划时，需考虑UAV面临的约束，其中包括：距离约束，地形成本、雷达威胁、UAV间的碰撞等.多个体协作的任务分配与路径规划问题通常称为任务计划问题，此类问题解决方案是基于任务计划系统(mission planning system，MPS)来完成计算的.由于任务分配实施和路径规划均参考彼此的输出，MPS中易存在信息耦合或输出不对称现象，导致任务计划解决方案成本过高或计算不准确的现象发生[11].考虑到MPS的不足，许多文献提出新的策略来提升MPS性能.其中主要有：Edison等[12]在飞行路径的曲率约束下使用遗传算法，将协作UAV的任务分配和轨迹生成合并在一起。Zhu等[13]提出了基于改进的自组织映射神经网络的动态任务分配和路径规划算法，用于多个自动水下机器人.Yao等[14]提出了一个多阶段任务计划框架，该框架是基于环境中障碍物的估计来处理信息耦合.Jose等[15]提出了多机器人巡逻作业的任务分配与路径优化。

      据上述文献可知，在求解任务计划的问题上，要么在执行任务分配前花大量计算资源来检查所有可行路径与方案，要么在两阶段求解时发生信息耦合，得到计算结果不准确或计算成本偏高的方案.为提升任务计划结果的有效性，通常方法是再次重新计算，即重复运行任务计划算法，直到计划结果足够好为止，该情况会导致计算成本线性升高，耗时过长，不符合实际作业需求。