一种针对无人机配送网络的能量自维持调度方案  

An energy self-sustaining scheduling scheme for UAV delivery networks

作　　者：徐佳[1,2] 袁鸣 吴思徐 谭芯 骆健[1,2] XU Jia;YUAN Ming;WU Sixu;TAN Xin;LUO Jian(School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China;Jiangsu Key Laboratory of Big Data Security and Intelligent Processing,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

机构地区：[1]南京邮电大学计算机学院,江苏南京210023 [2]南京邮电大学江苏省大数据安全与智能处理重点实验室,江苏南京210023

出　　处：《物联网学报》2024年第2期56-70,共15页Chinese Journal on Internet of Things

基　　金：国家自然科学基金项目(No.62372249,No.62072254,No.62272237,No.62171217,No.62302236,No.62372250)。

摘　　要：近年来,快递行业需求快速增长,物流配送行业压力剧增。无人机(UAV, unmanned aerial vehicle)配送凭借其人力成本低、灵活方便等特性成为车辆配送的有益补充。然而,无人机配送受续航能力和负载能力等因素的制约,需要低成本且能量自维持的配送和充电调度方案来支持多无人机的协同配送。提出了两阶段的能量自维持的多无人机协同配送及充电调度方案。第一阶段在满足无人机能量和载重容量约束的前提下,最小化能完成区域内所有配送任务所需的无人机数量,并给出对应配送路线。提出了无人机配送调度算法(UDSA, UAV delivery scheduling algorithm),并从理论上证明了UDSA的近似度。第二阶段对具有不同到达时间的无人机进行充电调度,最小化所有无人机的最大充电完成时间。提出了一种具有近似度的无人机充电调度算法(UCSA, UAV charging scheduling algorithm)来求解该问题。仿真实验结果表明,与基准算法相比,UDSA最多可以减少44.17%的无人机数量;UCSA最多可以缩短18.87%的最大充电完成时间。In recent years,the demand of express industry has increased rapidly,and the express industry is under increas‐ing pressure.The unmanned aerial vehicle(UAV)delivery has become an effective supplement to vehicle delivery due to its low human cost,flexibility and convenience.However,UAVs are often limited by factors such as endurance and load capacity,requiring a low-cost and energy self-sustaining scheduling scheme for delivery and charging to support collab‐orative delivery of multiple UAVs.A two-stage self-sustaining multiple UAV cooperative delivery and charging schedul‐ing scheme was proposed.The first stage aims at finding the delivery routes of UAVs to complete all delivery tasks in the region such that the number of UAVs was minimized under the energy and load capacity constraints of UAVs.The UAV delivery scheduling algorithm(UDSA)was proposed,and the approximation of UDSA was proved theoretically.The sec‐ond stage aims to schedule the charging of UAVs with different arrival times to minimize the maximum charging comple‐tion time of all UAVs.An approximate UAV delivery scheduling algorithm(UCSA)was proposed to solve the problem.The simulation results show that,compared with the benchmark algorithm,UDSA can reduce the number of UAVs by 44.17%at most,and UCSA can reduce the maximum charging completion time by 18.87%at most.

关 键 词：无人机 配送调度 车辆路由问题 无线充电调度 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]