基于反向拍卖算法的任务导向型货运无人机任务分配研究.pdf

2023年12 月计算机应用文摘第39 卷第2 4期基于反向拍卖算法的任务导向型货运无人机任务分配研究肖岩平,程立鸿,蔡小溪,孙晖（军事科学院系统工程研究院，北京10 0 0 7 1)摘要：目前，我国社会经济明显复苏，物流经济蓬勃发展，货运无人机在物流领域的作用日益凸显。供应链中的运输任务涉及食品、日用品、大宗补给品等物资，因此选择适应任务类型的货运无人机将直接影响物资的运输效率。同时，在优先完成任务的基础上，货运无人机需要对任务执行成本进行有效控制，这将成为货运无人机任务规划的重要考量。关键词：反向拍卖算法；任务分配；货运无人机i=1中图法分类号：V279Research on task allocation of task oriented cargo drones based on(The PLA Academy of Military Science Systems Engineering Institute,Beijing 100071,China)Abstract:At present,Chinas socio-economic recovery is evident,and the logistics economy isflourishing.The role of freight drones in the logistics field is increasingly prominent.Thetransportation tasks in the supply chain involve materials such as food,daily necessities,and bulksupplies.Therefore,choosing a cargo drone that is suitable for the task type will directly affect thetransportation efficiency of the materials.At the same time,on the basis of prioritizing taskcompletion,freight drones need to effectively control task execution costs,which will become animportant consideration in freight drone task planning.Key words:reverse auction algorithm,task allocation,cargo drone利用货运无人机进行任务分配时将面临多种机型和多种运输任务以及不同运输投送对象难以合理匹配的难题1。因此,为提升货运无人机的运输效率,采用多架货运无人机就同一个需求对象和仓库地点进行定点运输的策略，这种运输模式极大提升了货运无人机任务执行的鲁棒性。1货运无人机任务分配问题描述本文将采用反向拍卖算法，以从“蜂群式”货运无人机中优选一架进行前出保障，其余货运无人机将作为该机的替补机,随时待命2 。在任务需求下达后，通过挑选适合执行该任务的货运无人机形成运输编队。通过构建的优选函数对待命货运无人机进行筛选，选择性能最接近任务目标的货运无人机执行任务。在此过程中,挑选的无人机可以是一架，也可以是型号相同的多架，而其余无人机群将继续待命。如果执行任务的无人机中途因故障退出，则继续从剩余文献标识码：Areverse auction algorithmXIAO Yanping,CHENG Lihong,CAI Xiaoxi,SUN Hui导向型的任务分配策略。在运输任务分配场景中，由x；架货运无人机构成货运无人机集合T=1,t2,t3，,t;，有us个货运无人机运输投送任务集合M=m1,m2,m3，,mz l。若货运无人机可以执行其载荷范围内的任何任务，每架货运无人机都可执行X,项运输任务，则X,us，因此各架货运无人机针对可执行的目标任务构成了新的目标任务集合V,=cil,，c i 2,c i s，,c n l。为有效地利用货运无人机资源，实现货运无人机与任务需求的有效对接,每项任务应有针对性地分配给一架潜在目标货运无人机。基于此，可以定义任务与货运无人机的匹配度为：的货运无人机中挑选更接近任务目标的无人机进行任务执行,直到任务完成3。本文以货运无人机对物资需求方进行运输作业为任务场景，将任务需求视为拍卖方，货运无人机则为竞拍方，从而制定任务需求2023 年第 2 4 期Fearning其中,C为适应度常数且取值范围为固定值,F。（c i n）表示第i架货运无人机执行第n项任务的优先值，Goalralue（c i n）表示第n项任务的优先级，UAVscale表示货运无人机的载荷参数指标，Goalcost表示该任务目标的运输量。由式（1)可以看出，当Goalualue（c i n）任务优先级和Goalcost任务目标的运输量一定时,货运无人机的性能指标越接近任务目标的运输量，货运无人机执行任务的优先值就越大。同时，通过反向拍卖算法进入候选集合的货运无人机性能指标均满足任务需求。此时,将决策变量定义为：(O,将目标运输任务cn不分配给运输无人机t;Xi讯=1,将目标运输任务cn分配给运输无人机t;maxearningi=1n=12x,uks.t.i=1VUAVseale(cin)Goalos(cin)Z*=,j=1,3,ki=1Goalvalue(cin)+CFearning其中,式（3）为目标函数，表示货运无人机优先值最大;式（4)一式（6)为约束条件，且式（4)表示货运无人机的编配数量大于目标任务量；式（5）表示货运无人机的限定载荷量不小于目标任务量；式（6)表示每项运输投送任务要分配给一架货运无人机。2货运无人机任务分配方案设计2.1运适应度函数的构建本节基于上述模型，旨在优选模型函数以评估货运无人机的任务执行效能。通过构建这一优选模型函数，可以实现货运无人机任务执行的收益和效能最大化。在了解运输任务需求和货运无人机装备性能的基础上，可以通过构建优选模型函数在货运无人机任务分配过程中选择与目标任务匹配度最高的货运无人机。相应的公式为：FearningMUAV roperm-Coalostnron计算机应用文摘Goalvalue(cin)+C其中，C为适应度常数且取值范围为固定值，Fmm(1)UAVseal-Goalosearning(2)in(3)(4)(5)(6)(7)UAV sedle-Coal.osGoal alue(M)+C85（m）表示货运无人机执行任务的优先值，Goalralue（M）表示任务M的任务优先级，UAVprpery表示货运无人机的性能参数指标,Goalcost表示该任务目标的运输量。由式（8）可以看出，当Goalualue（M）任务优先级和Goalcos任务目标的运输量一定时,货运无人机的性能指标越接近任务目标的运输量，货运无人机执行任务的优先值就越大。同时，通过反向拍卖算法进人候选集合的货运无人机性能指标均满足任务需求，因此Farming(M)0.2.2货运无人机任务分配算法设计本文首先使用反向拍卖算法，按照目标任务需求排列出候选货运无人机集合。接着，设计了算法以筛选出优选值最大的货运无人机，然后将其派遣前出执行任务。(1)拍卖任务为TASKyi，i=1,2,3，,候选货运无人机为 UAVx;,i=1,2,3,.。(2)输人 TASKy：的任务量为TASKeariagey;输人UAVx;的任务载荷为 UAVerigex。(3)若 UAVeariage x TASKerigey,则 UAVx;进人货运无人机候选集合GATHERyi。(4）若 UAVeariagexTASKariage,则切换下一架货运无人机UAVx;，重复步骤（3）。(5)当本轮UAVx；被遍历对比完毕后,生成本轮任务候选货运无人机集合，集合中GATHERy;的货运无人机记为 UAVCATHERy;*,i=1,2,3,。(6)继续下一轮TASKy;的拍卖工作,循环至步骤(2)继续进行拍卖供需双方对接，直至所有任务被遍历完毕。（7）初始化GATHERY：中UAVCATHERy:的参数信息。(8)根据式(4)计算 GATHERy;中 UAVCATHERy的优先值,并按照优先数值的大小对UAVCATHERy:重新排序,得到 GATHER(Y,)。（9)优先选择GATHER(Y）中排列靠前的货运无人机执行任务，直到TASKy；遍历询问完毕。（10)若货运无人机未到达指定位置或者任务未完成,则选择GATHER（Y）中下一架货运无人机执行任务,重复步骤（9）,直到TASKy；遍历询问完毕，任务执行完毕，算法结束。3货运无人机任务分配算例分析(8)在运输作业场景中，货运无人机主要负责执行任86务1、任务2、任务3、任务4、任务5、任务6、任务7 等物资的运输投送任务，如表1所列。由于货运无人机无法对所有物资进行运输，或者说货运无人机作业能力存在一定限制，因此在这里使用货运无人机运输投送系数来表示其实际运输能力。在以任务导向为引导的反向拍卖算法中，任务需求充当拍卖方，可以吸纳满足运输条件的货运无人机集合，实现一项任务由多架货运无人机的对多模式。然后，按顺序遍历候选货运无人机集合，指派最合适的一架或数架货运无人机执行任务。表1运输投送任务需求表任务运输货运无人无人机单次无人任务需求编号投送系数机运输量出行架次机运输量1任务12任务23任务34任务45任务56任务67任务7从表1可以看出，每一项特定任务都有若干型号的货运无人机与之对应，即大量无人机可以集群完成同一项任务，从而显著提升了货运无人机的任务执行能力。如果任务无人机出现故障或发生状况导致无法继续执行任务，或者任务执行进程中断，可以继续挑选候选货运无人机接替任务。通过对任务优先级进行排序以及计算各任务需求下的货运无人机候选集合的优选模型Famig(M)=Goal alue(M)+C，得出每项任务需求下的优选货运无人机。算法实现后，货运无人机与任务需求匹配的情况如表2 所列。从表2 可以看出，任务1可由UAV5来执行运输，而任务5和任务3则可以由UAV11执行运输，任务1和任务2 可以由UAV1或UAV6货运无人机前出执行运输,而任务6 则可以通过UAV13执行运输。至于任务7 中的特种器材，则可由UAV14完成运输任务。计算机应用文摘任务任务单次无人机优先级需求运输量1任务4100 kg2任务3300kg3任务11 000 kg4任务5480 kg5任务21 400 kg6任务6900 kg7任务7120 kg10%10t70%14t100%210kg100%100 kg80%480 kg60%9t40%1 200 kg2023年第2 4期表2 货运无人机任务执行表优选货运候选无人机编号无人机编号1,2,3,4,5,6,7,8,59,10,11,12,13,141,2,3,4,5,6,10,11,12,13,141,6,10,131,2,3,4,5,6,10,11,12,131,6,10,131,6,10,131,2,3,4,6,10,11,12,13,14 101 000 kg101 400 kg210kg1111010111或6111或613144结束语货运无人机的任务分配效率与其空载率成反比100kg关系。任务分配效率的高低是货运无人机能否有效480 kg执行任务的关键。为使目标任务与运输无人机的载900 kg荷更好匹配，提升货运无人机的使用效率，本文利用120 kg反向拍卖算法，针对任务目标要求挑选出能够前出执行任务的货运无人机集合，通过构建货运无人机优选函数模型，根据任务目标需求对货运无人机进行优选，找出与任务目标最匹配的货运无人机，使得货运无人机与任务需求更好地对接，从而在一定程度上提升了货运无人机的任务分配效率。参考文献：1 毛远航.多无人机协同任务分配及安全路径规划研究D.南京：南京信息工程大学,2 0 2 0.2王轩.多无人机任务分配与航路规划算法研究 D.西安：西安电子科技大学，2 0 2 0.3刘永泰.多无人机协同作战任务分配与航路规划研究D.沈阳：沈阳航空航天大学,2 0 19.作者简介：肖岩平（197 6 一）,博士，副研究员,研究方向：野营保障。孙晖（1990 一），博士，助理研究员，研究方向：后勤业务（通信作者）。