无人机在应急物流配送中的任务分配模型构建

（陆军勤务学院，重庆 401331）

1 研究背景

信息基础设施建设的空前部署以及大数据、物联网、人工智能和云计算等新兴技术的不断进步和深化应用，给无人机带来了广阔的应用前景。在技术方面，机载能源技术和基于数字电视（PID）等技术的飞行控制系统是无人机的核心技术，是无人机不可缺少的组成部分［1］；遥感技术、数据链技术、避障技术是无人机关键技术，三者相辅相成；基于全球定位系统（GPS）、地理信息系统（GIS）、热成像、多光谱成像、激光雷达等遥感技术可实现对自身的导航定位和对外界的多角度感知［2］；基于数字数据链（DDL）、战术通用数据链（TCDL）、Quint 网络技术（QNT）数据链等数据链技术，承担着无人机与终端之间信息上传和下达的任务［3］，避障技术则在前两者基础上完成指定避障动作；为满足无人机在侦察、监视、打击、通信、保障、指挥控制等多功能应用，无人机也可以应用载荷技术、区块链、人工智能等拓展技术。

在应用方面，农业领域，无人机开展作物长势监测、作物产量估测、作物病虫害监测和作物田间管理，以及通过施药、浇水等方式实现植物保护［4-5］；测绘领域，无人机通过大比例尺航测、倾斜摄影三维建模等技术，对复杂场景进行大范围、高重叠度、高精度、高分辨率航摄，生成实景三维模型等数据成果［6］；通信领域，无人机通过物理层网络编码技术和自适应调制技术，增强通信系统的兼容性并实现多中继通信，并通过与测绘应用相结合，应对重大突发公共事件应急测绘保障能力得以增强，无人机应急测绘保障和低空摄影测量领域的应用范围得以拓宽［7-8］；军事领域，无人机涉及机动、情报、火力、防护、保障和指挥及控制领域，是提升情报、监视和侦察(ISR)能力和加快包以德循环（OODA 循环）的组成部分，可大幅提高作战效能，新技术新理念将传统侦察无人机向多任务、高时效、网络化方向发展［9-11］。相对而言，当前无人机在物流领域的应用较少，只有小范围试点，但无人机在物流领域有着丰富的应用场景，将成为未来重要发展领域。

2 无人机在物流领域应用的研究综述

近年来，物流无人机的探索开始广泛起来。2013 年电商巨头亚马逊公司首次宣布实施无人机配送计划，并于2017 年实现无人机配送包裹。谷歌公司于2014 年开始实施无人机配送项目开发，实现配送无人机直达目的地并自动完成卸货的功能。我国顺丰速运有限公司（以下简称“顺丰”）从2017 年6 月启动无人机物流配送试点；2017 年2 月京东集团（以下简称“京东”）与陕西省政府达成合作，打造低空无人机通用航空物流网络［12］。至今，配送无人机的兴起还不到10 年，但各种规模的物流企业都或多或少地开始研究配送无人机的应用，上至配送无人机的配送体系和应用模式等宏观研究，下至配送无人机的设计和算法等具体研究。

宏观方面，物流无人机配送体系有两种模式：一种是以京东为代表的“点对多”无人机物流配送模式，拟打造“干线-支线-末端”三级智慧物流航空体系；另一种是以顺丰为代表的“点对点”无人机物流配送模式，着重开展支线无人机的研制与应用［13］。在干线战略层，可采取有人机与无人机混合编队运输模式［14］；在支线战役层和末端战术层，可采取无人机与货车相结合的运输模式，也可以依靠站点模块、集群模块、指控模块和体系支撑模块的组成模块，通过“接收指令—调拨对接—规划路径—编队起飞—编队飞行—目标确认—卸载物资—编队返回”8 个环节的运转流程实现无人机独自配送模式［15］。针对无人机配送体系的特性，要根据配送无人机的使用环境、客户群体属性及其在造型、功能、载重能力、续航时间、安全性等因素设计配送无人机总系统，并根据区域内和区域间等不同层次情况设计配送无人机子系统［16-18］。

微观方面，无人机应用主要研究任务分配和航迹规划两大类问题，而任务分配和航迹规划是相互耦合的，通常可以共同探讨。这两大类问题通常需要通过算法求解，常用的传统算法有整数线性规划、模拟退火算法等，如今可以结合现代启发式、群智能算法进行求解，如遗传算法、粒子群算法、蚁群算法和鱼群算法等。传统算法中，有采用局部搜索与动态规划相结合的算法求解有无人机参与的旅行商任务分配模型［19］；有考虑多目标问题，提出应用线性权重法将其转化为单目标无人机任务规划问题，再通过与实数编码的烟花算法相结合的混合算法求解多目标无人机任务分配问题［20］；有提出用Grid-GSA 进行无人机航迹规划，即应用栅格法构建环境模型，为相应栅格赋予概率，再通过引力搜索算法实现对返航点数量和位置的寻优［21］。现代算法中，有针对无人机多目标任务分配问题，提出在量子蚁群算法快速搜索的基础上，融合克隆选择算法的交叉和克隆复制因子来提高算法的全局搜索能力，避免搜索过程过早陷入收敛问题［22］；有综合考虑“货车+无人机”配送模式、多批次拣选、多配送批次、带时间窗等因素的任务分配模型，通过PVRPTW-D遗传算法进行求解［23］；有提出用混合种群RRT 无人机航迹规划方法以解决航迹的最优问题，在基于环境势场的快速扩展随机树（RRT）算法的基础上，通过引入自优化种群和协同优化种群改善航迹段，使算法同时具有局部和全局寻优能力［24］；有基于协同粒子群算法和协同函数、协同变量相结合的算法以联合探讨任务分配与航迹规划问题［25］；有为避免异构无人机协同任务分配产生“死锁”现象，基于多类型基因编码的改进遗传算法进行任务分配，并采用Dubins 路径协调方法生成无人机最小转弯半径的可飞航迹［26］。

综上所述，目前无人机在配送体系方面已经设计出3 层架构，在战略层使用大型无人机进行远距离运输，在战役层使用中型无人机进行中短程运输，在战术层使用小型无人机进行近距离配送，而且在配送体系的每个层级中也探讨了相对应的应用流程和实现基础。比如在战术层中，小型无人机可以结合货车进行协同配送，目前较为常见的协同配送方式是货车配送内部需求点，无人机配送外部需求点，无人机配送完一个需求点后回到货车取货进行下一个配送任务。无人机在配送体系、应用流程和选址设计等方面的研究已较为成熟，并总结出无人机在配送中涉及无人机数据链系统、无人机飞行控制导航系统、无人机自主控制技术三大关键技术，然而，大多数研究只建立了应用无人机的物流配送体系、应用流程和分析其带来的好处，并没有与物流其他环节相结合深刻阐述总体上的变革，这将不能解决局部最优而非全局最优的问题。在无人机任务分配的研究中，主要探讨基于燃料补给点模式和基于无人机-货车联合配送模式两大类，国内外相关文献主要成果包括多旅行商问题模型、混合整数线性规划模型和多种运输工具配送模型等，其主要目标包括完成配送任务时间最小、配送成本最低或无人机参与数量最少等。无人机在航迹规划中主要探讨的是环境建模和航迹求解，环境建模主要涉及二维空间和三维空间，目前较为流行的技术方法是栅格图、拓扑图、Voronoi 图法等；航迹求解可使用传统的Dijkstra 算法和基于Dijkstra 改进的A 算法或现代群智能算法，以满足隐蔽性、安全性和飞行器限制等目标。无人机微观方面研究包含大量基于传统算法和现代智能算法的模型，但却忽略了较为重要的一个影响参数——无人机载重量。

从宏观和微观两方面的分析中可以看出，无人机在物流配送领域的普适性研究已较为完善，然而要想真正发挥无人机在物流领域的优势，必须结合具体场景进行具体模型设计。以军事领域为例，远程战略投送和支线战役车辆运输等方式已广泛使用，并且能解决中长距离的物资保障问题，但末端“最后一公里”的物资配送能力仍难以满足物资按时按量到达需求点。在应急物流中，环境复杂、物资保障具有不可预测性，导致物资的变化量远远超过其预测量，这进一步增强了末端“最后一公里”的应急保障特性。在2020 年新冠疫情期间，一架直径1.2 m 的无人机装载着送检标本从浙江省新昌县人民医院自动飞向县疾控中心，实现了24 h不间断、全方位、全天候配送，迈出了无人机在我国医药应急物流配送中的第一步。部分物流企业在疫情期间采取无人机进行无接触应急物流配送，发现配送效率能提升了60%～70%。现代物流中较为关键的是“最后一公里”配送问题，大多数物品往往积压在离最终用户很近的配送中心，普通物品由于配送人员、配送工具不足造成的积压而导致的价值损失可能很小，但急需品一旦没按时到达，则会造成难以估量的损失。无人机的应用，将能解决目前应急物流配送中所面临的高时效性、高安全性和高精确性等瓶颈问题。为解决“最后一公里”点多、线长、面广的应急物流配送问题，采用小型配送无人机（以下简称“配送无人机”或“无人机”）将成为未来可行且高效的一种配送方式。

3 无人机在应急物流配送中的应用创新

应急物流采用无人机的配送方式总的来说有三方面优势：一是能够跨越各类障碍、快速响应应急需求，实现精确高效保障；二是成本低、应急能力强，能实现不间断作业；三是约束条件少、适应高难任务，能实现配送过程零伤亡率。为了更好地在“最后一公里”应用配送无人机，就必须在仓库中配置适当的配送无人机，这将会引发仓库布局和运作模式等一系列改革。

目前，仓库的运作模式有4 种（以取货为例）：叉车取货、堆垛机系统取货、穿梭车取货和AGV 小车自动取货［27］。从总的来看，可分为两大类：“货到人”模式和“人到货”模式。随着人工智能等新兴技术的发展，未来仓库的运作模式将趋于“货到人”模式的半智能出库，而本研究认为未来仓库将可结合配送无人机实现完全无人出库。本研究在穿梭车取货背景下，采取结合配送无人机进行物资配送的方式，则无人机与穿梭车的停放空间可以搭配设置在货架上，以增大物资存储的面积利用率和空间利用率。先根据实际情况设定具体的货架层数，然后将货架在空间上分为3 个区域，由下至上依次为物资存储区、穿梭车与无人机存储区、预留区，其空间布局见图1。物资存储区与一般货架相似，预留区是为了应对穿梭车数量与无人机数量未来增长的需要，而穿梭车与无人机存储区是将一台穿梭车与一架无人机搭配存储，穿梭车存放在空间底部、无人机悬挂在空间顶部，这样无人机在进行配送物资装载时可以直接通过穿梭车进行接洽，这使得存放与出库在同一空间得到实现。出库时，穿梭车将物资从物资存储区的储位运到穿梭车与无人机存储区的所属储位中，通过模块化设计好的接口直接与无人机接洽，然后搭载着无人机到达无人机起飞场所，无人机起飞进行配送作业后，穿梭车返回进行下一任务或在储位等待接收无人机返回入库。这种新方式的使用，将可以实现分拣、出库的全自动化，即不需要人参与任何分拣、出库作业。

图1 完全无人出库模式下的仓库空间布局

仓库改革完成后，配送无人机的存储、装载物资和起飞等环节将可实现无缝对接，在宏观方面能更好地满足应急物流配送的高效性。接下来就要从微观方面进行具体探讨。无人机配送应急物资，一般是通过无人机直接将物资从后勤供应点运往单个前线需求点，即配送无人机的保障目标是单个前线需求点。虽然此方式保障个别需求点的速度较快，但配送任务完成最迟的需求点却耗时太久，导致整个前线地区部队的整体联合效益降低。传统无人机任务分配也有对总时间进行优化的模型，但却没有考虑载重量会影响无人机最大飞行速度。所以，本研究将基于载重量参数，使用两种算法对照地去优化配送无人机的任务分配，以使得整个前线区域的最迟配送完成总时间最短。

目前国内小型配送无人机最典型的是多旋翼无人机，其中最常用的是四旋翼和六旋翼无人机。四旋翼无人机的巡航速度为36 m/h，飞行速度范围在30 km/h～54 km/h，最大起飞重量16 kg，有效载荷10 kg，留空时间2 h，可在海拔4 000 m的高度上作业。六旋翼无人机的巡航速度为30 m/h，飞行速度范围在30 km/h～43km/h，最大起飞重量24 kg，有效载荷24 kg，留空时间2 h，可在海拔6 000 m 的高度上作业［28］。根据文献所述，小型无人机载重与最大飞行速度近似呈线性关系，故可将飞行范围中的最大值作为空载时的最大飞行速度，将飞行范围中的最小值作为满载时的最大飞行速度［29］。为得到配送无人机飞行速度V 与其载重量Z 的关系，本研究综合考虑多种无人机在常见环境下的飞行数据，最终采用空载时60 km/h 的飞行速度和满载（10 kg）时40 km/h 的飞行速度这两组数据，可得：

4 配送无人机应急任务分配建模

本研究针对部队较为需求的物资——弹药，进行配送无人机应急任务分配建模。从1 个供应点出发，出动N 架配送无人机对M个需求点实施弹药配送，每架配送无人机在保障一个需求点后，可根据具体情况分析是否在已完成配送任务的需求点j 出发，继续保障其他需求点。每个需求点的位置和弹药需求情况已知，每个需求点最多受两架无人机保障，每架无人机最多前往两个需求点。虽然配送无人机前往两个需求点的任务分配会导致某些需求点配送时间延长，但能缩短整个联合区域的最迟保障总时间。下面就对总时间这个目标进行讨论优化。

4.1 模型假设

（1）每架无人机从后勤供给点出发,沿着某一条飞行路线把所装载的所有物资配送给前线需求点。由于每个飞行路径只考虑一架配送无人机，故不考虑编队设计。

（2）每架无人机的载重量是有限制的，所运载的物资补给总重量不能超过该范围。为了简化问题,假设所有配送无人机型号相同，拥有相同的载重能力。同时不考虑物资种类对飞行的影响。

（3）不考虑配送无人机在各个目标部队位置处的转向角约束，也不考虑航迹规划。

（4）不考虑其他影响最大飞行速度的因素，且配送无人机都以最大飞行速度进行配送。

4.2 符号说明

（1） 集合。M为配送无人机集合，且M={1,2,…,i,…,n}；N为需求点集合，且N={1,2,…,k,…,n}；W为配送无人机出发点集合，包括后勤供应点和中转需求点，且W={1,2,…,j,…,n}，当j=1 时为后勤供应点，当j>1 时为中转需求点。

（2）参数。dijk为第i架配送无人机从第j个配送无人机出发点到第k个需求点的距离；tmax为配送无人机的最长飞行时间；aijk为第i架配送无人机从第j个配送无人机出发点到第k个需求点的载重量(zi)；amax为配送无人机的最大载重量；zk为第k个需求点的物资需求重量；为第i架配送无人机载重从第j个配送无人机出发点到第k个需求点的最大飞行速度。

（3）决策变量。xijk为0 至1 变量，当第i架配送无人机从第j个配送无人机出发点到第k个需求点时等于1，否则等于0。

4.3 数学模型

式（2）为问题的目标函数，求整个前线区域完成任务的总时间最短。式（3）为求每个路径的飞行时间。约束（4）是保证每个需求点最多可通过两种路径保障物资需求。约束（5）是保证每个配送无人机最多到达两个需求点即完成任务。约束（6）是保证每个配送无人机的续航能力能完成配送任务。约束（7）是保证每个需求点的物资需求量刚好被满足。约束（8）是确保决策变量xijk为0 至1 变量。约束（9）是保证每架配送无人机的载重量不超过其载重上限。

4.4 模型求解算法

排序算法的基本思路是：配送任务完成最快的配送无人机保障最慢的需求点，次快的配送无人机保障次慢的需求点。依此类推，得到缩减的最迟配送任务完成时间。

贪婪算法的基本思路是：从问题的初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。根据贪婪算法的思路，先求需求点N的配送任务完成时间最多能缩减多少，即通过定下一个载重量变化值，不断从保障需求点2 到N-1 中的配送无人机拿出一架进行载重量迭代。因为载重量有上限且每架无人机保障的需求点物资需求量不一样，故每架无人机的迭代次数是不一样的；每次迭代得到的结果不仅要考虑原先路径的配送时间减少多少，还要考虑新增路径的配送时间，若新增路径的配送时间比没迭代前的原先路径配送时间还长，则此方案放弃。最终在遍历所有载重量和所有无人机中转保障需求点N后，得到需求点N完成配送任务的新时间。将需求点N所耗的新时间与需求点N-1 所耗的时间进行比较：若需求点N 所耗的新时间大于需求点N-1 所耗的时间，则此需求点N所耗的新时间即为整个前线区域新的最迟配送任务完成总时间；若小于需求点N-1 所耗的时间，将需求点N-1 重复需求点N的步骤，但在无人机的迭代中将不能再使用保障需求点N的无人机，即保障需求点N的无人机放入禁忌表。按上述步骤逐一循环，最终得到一个新的最迟配送任务完成总时间，其算法流程如图2 所示。

图2 贪婪搜索算法流程

5 算例分析

5.1 算例构建

下面以我方一个后勤供应点派出10 架配送无人机对10 个前线需求点进行物资配送任务为背景，先设计一组相同载重量变化值的实验，以观察比较两种算法之间的不同之处；再设计5 组不同载重量变化值的迭代实验，以观察不同载重量变化值对完成任务的总时间和配送无人机配送路径的影响。

采用MATLAB 2017 版本进行算例分析，将所有需求点的弹药需求重量设置在5 kg～10 kg，并且所有需求点之间在x轴方向的取值范围不超过10 km，在y 轴方向的取值范围也不超过10 km，最终确定了所有需求点在横坐标［30,40］和纵坐标［25,35］范围内。供应点的位置根据最近距离优先的方式，选在（0，30）的位置上。实验采取相同的配送无人机，其飞行速度和载重量的关系如前文模型假设。下面根据需求点数量为10 时得到一组初始解时间。为了与接下来算法的结果作对比，将这组初始解时间由快到慢排序，并将供应点编号为1，需求点根据配送任务完成的快慢程度编号为2 到11，具体数据见表1，其网络拓扑图如图3 所示。

表1 算例的初始解

图3 算例的初始配送网络

为能更好地分析比较不同结果的好坏程度，我们使用时间缩减率来代替最迟配送任务完成时间进行比较。公式如下：

5.2 两种算法之间的结果比较

为直观比较两种算法的优劣，实验采取载重量变化值为0.1 时进行比较，两种算法所得的结果如表2 所示。

表2 算例采用两种算法得到的完成任务所需时间比较单位：h

采用排序算法得到的无人机任务分配将使整个前线区域的配送任务完成总时间减少至0.925 742 510 h，时间缩减率只达到1.6%；而采用贪婪搜索算法得到的无人机任务分配不仅使初始解中配送任务完成的最迟时间降至比第二迟时间还低，还将原先第二迟时间进一步缩减，使得整个前线区域的配送任务完成总时间减少至0.859 388 154 h，时间缩减率达到约8.7%，其网络拓扑图如图4 所示。

图4 算例基于贪婪搜索算法的配送网络

5.3 载重变化量不同对贪婪算法结果的影响

实验采取5 组载重量变化值，分别为0.1、0.3、0.4、0.5、0.7，基于贪婪搜索算法所得的结果见表3。载重量变化值为0.4 时，时间缩减率为8.7%。载重量变化值为0.5 时，无人机3 增加了载重量却仍与载重量变化值为0.1 时的时间相同，故这种方式使得整个前线区域的配送任务完成总时间仍减少至0.859 388 154 h，时间缩减率仍为8.7%。载重量变化值为0.3 时，这种方式使得整个前线区域的配送任务完成总时间减少至0.863 088 966 h，时间缩减率为8.2%。载重量变化值为0.7 时，所有无人机任务分配中只有无人机3 需要多载2.1 kg 物资在保障需求点4 后前往需求点11，虽然导致原先配送任务完成的最迟时间降到了和载重量变化值为0.3时一样的0.863 088 966 h，但由于原先第二迟时间0.873 048 308 h 大于调整后的最迟时间，并且其需求点没有其他无人机进行二次保障，所以这种方式使得整个前线区域的配送任务完成总时间减少至0.873 048 308 h，时间缩减率为7.2%。

表3 算例基于贪婪搜索算法得到的不同载重下完成任务所需时间 单位：h

观察发现，载重量变化值为0.3 和0.7 时，需求点11 完成配送任务的时间都缩减至0.863 088 966 h，可得到需求量变化值为2.1 的时候是保障需求点11的一个次优解；载重量变化值为0.1、0.4 和0.5 时，3 组数据得出的时间缩减率一样，可得到这一次随机分配的10 个需求点中，载重量变化值为2 的时候即可得到一个次优解；当载重量变化值再进一步往小于0.1 的方向减少时，可能会产生更优的结果。

6 结论

目前，无人机在物流领域的应用只停留在理论和小范围试点阶段，但已有研究表明无人机在物流领域有着丰富的应用场景和发展前景，而且针对物流领域较为关键的配送环节，应急物流配送存在的诸多瓶颈问题难以较好地改善，而无人机的精确保障、快速反应、不间断作业和零伤亡率等特性有利于突破应急物流配送中所面临的高精确性、高时效性、高安全性等瓶颈问题［30-31］。本研究以物资配送为基础，提出依靠无人机进行应急物流配送，先设想了应用配送无人机引发的仓库空间布局和运作模式的改革，然后建立了配送无人机的任务分配模型，在考虑载重量会影响最大飞行速度的基础上，应用贪婪搜索算法推导出配送无人机进行双目标应急配送的较优解，与原来供应点用配送无人机只保障一个需求点目标相比，总时间缩减率可达7%～8%，对未来实际应用配送无人机进行各种物资应急物流配送具有一定的参考价值；最后在进行结果分析时，将载重量变化值设置不同大小，发现并非设置越小越好，而是要根据空间内具体的配送网络设置相应的载重量变化值。

随着配送无人机的机体技术发展，其续航能力和载重量将可满足多目标中转需求，接下来可进一步研究基于载重量参数的配送无人机多目标中转任务分配。随着配送无人机信息技术的发展，其应用场景不仅仅局限于常规的应急物流，还可运用于某些特殊场景，例如海岛场景，由于海岛分散且需求量不大，用运输船配送物资需要经过多次中转和装卸，导致配送成本较高而且费时较长，甚至导致出现“错漏串”等问题，而使用无人机进行海岛物资配送能有效降低物流成本和提高配送的齐套能力，且结合本研究探讨的无人机任务分配模型还可以进一步提高配送效率。在偏远地区场景中，由于终端用户离物流中心距离较远且基础建设较差，物流配送成本高于收益，所以许多偏远地区用户的物品需要几周的配送时间甚至没有快递服务，而无人机的点对点配送能有效解决应急物流在偏远地区的瓶颈问题，将分配和派送等多个环节简化为“一键”实施，实现跨越式精准保障。