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

徐佳; 袁鸣; 吴思徐; 谭芯; 骆健

doi:10.11959/j.issn.2096-3750.2024.00359

您当前的位置：

首页 >

文章列表页 >

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

理论与技术 | 更新时间：2024-08-16

- 一种针对无人机配送网络的能量自维持调度方案
- An energy self-sustaining scheduling scheme for UAV delivery networks
- 物联网学报 2024年8卷第2期页码：56-70
- 作者机构：
  
  1.南京邮电大学计算机学院,江苏南京 210023
  2.南京邮电大学江苏省大数据安全与智能处理重点实验室,江苏南京 210023
- 作者简介：
  
  [ "徐佳（1980-），男，博士，南京邮电大学教授，主要研究方向为群智感知、无线充电、边缘计算和区块链等。" ]
  [ "袁鸣（1997-），女，南京邮电大学计算机学院硕士生，主要研究方向为路径规划和无线充电。" ]
  [ "吴思徐（1997-），男，南京邮电大学计算机学院博士生，主要研究方向为无线充电传感器网络。" ]
  [ "谭芯（1998-），女，南京邮电大学计算机学院硕士生，主要研究方向为边缘计算。" ]
  [ "骆健（1976-），女，南京邮电大学副教授，主要研究方向为数据挖掘和机器学习。" ]
- 基金信息：
  
  国家自然科学基金项目(62372249;62072254;62272237;62171217;62302236;62372250)
- DOI：10.11959/j.issn.2096-3750.2024.00359
  中图分类号：
- 纸质出版日期：2024-06-10，
  
  收稿日期：2023-02-14，
  
  修回日期：2023-09-15，
- 稿件说明：
移动端阅览
徐佳,袁鸣,吴思徐等.一种针对无人机配送网络的能量自维持调度方案[J].物联网学报,2024,08(02):56-70.

XU Jia,YUAN Ming,WU Sixu,et al.An energy self-sustaining scheduling scheme for UAV delivery networks[J].Chinese Journal on Internet of Things,2024,08(02):56-70.
徐佳,袁鸣,吴思徐等.一种针对无人机配送网络的能量自维持调度方案[J].物联网学报,2024,08(02):56-70. DOI： 10.11959/j.issn.2096-3750.2024.00359.

XU Jia,YUAN Ming,WU Sixu,et al.An energy self-sustaining scheduling scheme for UAV delivery networks[J].Chinese Journal on Internet of Things,2024,08(02):56-70. DOI： 10.11959/j.issn.2096-3750.2024.00359.

摘要

近年来，快递行业需求快速增长，物流配送行业压力剧增。无人机（UAV

unmanned aerial vehicle）配送凭借其人力成本低、灵活方便等特性成为车辆配送的有益补充。然而，无人机配送受续航能力和负载能力等因素的制约，需要低成本且能量自维持的配送和充电调度方案来支持多无人机的协同配送。提出了两阶段的能量自维持的多无人机协同配送及充电调度方案。第一阶段在满足无人机能量和载重容量约束的前提下，最小化能完成区域内所有配送任务所需的无人机数量，并给出对应配送路线。提出了无人机配送调度算法（UDSA

UAV delivery scheduling algorithm），并从理论上证明了UDSA的近似度。第二阶段对具有不同到达时间的无人机进行充电调度，最小化所有无人机的最大充电完成时间。提出了一种具有近似度的无人机充电调度算法（UCSA

UAV charging scheduling algorithm）来求解该问题。仿真实验结果表明，与基准算法相比，UDSA最多可以减少44.17%的无人机数量；UCSA最多可以缩短18.87%的最大充电完成时间。

Abstract

In recent years

the demand of express industry has increased rapidly

and the express industry is under increasing 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 collaborative delivery of multiple UAVs. A two-stage self-sustaining multiple UAV cooperative delivery and charging scheduling 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 second stage aims to schedule the charging of UAVs with different arrival times to minimize the maximum charging completion 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.

关键词

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

Keywords

UAVdelivery schedulingvehicle routing problemwireless charging scheduling

references

HUDSON N, CHAPMAN P, RAMACHANDRAN R. Global express and small parcels[EB]. 2022.

AGATZ N, BOUMAN P, SCHMIDT M. Optimization approaches for the traveling salesman problem with drone[J]. SSRN Electronic Journal, 2015.

GLASER A. Watch Amazon’s prime air make its first public U.S. drone delivery[EB]. 2017.

GROTHAUS M. This is how Google’s project wing drone delivery service could work[EB]. 2022.

正北方网. 京东物流智能配送机器人在内蒙古送出首单[EB]. 2018.

North News. JD logistics intelligent delivery robot delivers first order in inner mongolia[EB]. 2018.

中通研究院. “末端+支线”无人机运营场景成本分析[EB]. 2022.

Zhongtong Research Institute. Cost analysis of “terminal+branch” UAV operation scenario[EB]. 2022.

MURRAY C C, CHU A G. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[J]. Transportation Research Part C: Emerging Technologies, 2015, 54: 86-109.

MATHEW N, SMITH S L, WASLANDER S L. Planning paths for package delivery in heterogeneous multirobot teams[J]. IEEE Transactions on Automation Science and Engineering, 2015, 12(4): 1298-1308.

MOURELO FERRANDEZ S, HARBISON T, WEBER T, et al. Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm[J]. Journal of Industrial Engineering and Management, 2016, 9(2): 374-388.

POIKONEN S, GOLDEN B. Multi-visit drone routing problem[J]. Computers & Operations Research, 2020(113): 104802.

ROBERTI R, RUTHMAIR M. Exact methods for the traveling salesman problem with drone[J]. Transportation Science, 2021, 55(2): 315-335.

WU G H, FAN M F, SHI J M, et al. Reinforcement learning based truck-and-drone coordinated delivery[J]. IEEE Transactions on Artificial Intelligence, 2023, 4(4): 754-763.

ERMAĞAN U, YıLDıZ B, SALMAN F S. A learning based algorithm for drone routing[J]. Computers & Operations Research, 2022, 137: 105524.

GU Q C, FAN T J, PAN F, et al. A vehicle-UAV operation scheme for instant delivery[J]. Computers & Industrial Engineering, 2020, 149: 106809.

GENTILI M, MIRCHCANDANI P B, AGNETIS A, et al. Locating platforms and scheduling a fleet of drones for emergency delivery of perishable items[J]. Computers & Industrial Engineering, 2022, 168: 108057.

DORLING K, HEINRICHS J, MESSIER G G, et al. Vehicle routing problems for drone delivery[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017, 47(1): 70-85.

CHENG C, ADULYASAK Y, ROUSSEAU L M. Drone routing with energy function: formulation and exact algorithm[J]. Transportation Research Part B: Methodological, 2020, 139: 364-387.

CHOI Y, SCHONFELD P. Optimization of multi-package drone deliveries considering battery capacity[C]. Transportation Research Board 97th Annual Meeting, [S.l.:s.n.], 2017

SONG B D, PARK K, KIM J. Persistent UAV delivery logistics: MILP formulation and efficient heuristic[J]. Computers & Industrial Engineering, 2018, 120: 418-428.

TAKICI E. Solving location and routing problem for UAVs[J]. Computers & Industrial Engineering, 2016, 102: 294-301.

SHI Y H, LIN Y, LI B, et al. A bi-objective optimization model for the medical supplies’ simultaneous pickup and delivery with drones[J]. Computers & Industrial Engineering, 2022, 171: 108389.

DJI. Spreading wings s900[EB]. 2022.

FLYNT J. How much weight can a drone carry?[EB]. 2017.

BAZGAN C, HASSIN R, JERME M. Approximation algorithms for some vehicle routing problems[J]. Discrete Applied Mathematics, 2005, 146(1): 27-42.

KOULAMAS C, KYPARISIS G J. Makespan minimization on uniform parallel machines with release times[J]. European Journal of Operational Research, 2004, 157(1): 262-266.

ARKIN E M, HASSIN R , LEVIN A. Approximations for minimum and Min-max vehicle routing problems[J]. Journal of Algorithms, 2006, 59(1): 1-18.

HOFRI M. A probabilistic analysis of the Next-Fit Bin packing algorithm[J]. Journal of Algorithms, 1984, 5(4): 547-556.

ZONKE IED. SF ARK 40[EB]. 2023.

CAVALIERE F, BENDOTTI E, FISCHETTI M. An integrated local-search/set-partitioning refinement heuristic for the Capacitated Vehicle Routing Problem[J]. Mathematical Programming Computation, 2022, 14(4): 749-779.

LI R, HUANG H C. On-line scheduling for jobs with arbitrary release times[J]. Computing, 2004, 73(1): 79-97.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于无人机的物联网空基中继鲁棒优化

边缘智能驱动的高能效无人机自主导航算法研究

基于深度强化学习的无人机数据采集和路径规划研究

基于无人机的物联网无线通信的潜力与方法