An energy self-sustaining scheduling scheme for UAV delivery networks

XU Jia; YUAN Ming; WU Sixu; TAN Xin; LUO Jian

doi:10.11959/j.issn.2096-3750.2024.00359

您当前的位置：

首页 >

文章列表页 >

An energy self-sustaining scheduling scheme for UAV delivery networks

Theory and Technology | 更新时间：2024-08-16

- An energy self-sustaining scheduling scheme for UAV delivery networks
- Chinese Journal on Internet of Things Vol. 8, Issue 2, Pages: 56-70(2024)
- 作者机构：
  
  1.南京邮电大学计算机学院,江苏南京 210023
  2.南京邮电大学江苏省大数据安全与智能处理重点实验室,江苏南京 210023
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(62372249;62072254;62272237;62171217;62302236;62372250)
- DOI：10.11959/j.issn.2096-3750.2024.00359
  CLC：
- Received：14 February 2023，
  
  Revised：2023-09-15，
  
  Published：10 June 2024
- 稿件说明：
移动端阅览
徐佳,袁鸣,吴思徐等.一种针对无人机配送网络的能量自维持调度方案[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

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 .

Views

216

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Analysis of UAV positioning accuracy based on OTFS-ISAC

Robust optimization of air based relay for internet of things based on UAV

Research on power efficient autonomous UAV navigation algorithm: an edge intelligence driven approach

Research on the UAV-aided data collection and trajectory design based on the deep reinforcement learning

Potential and methods of wireless communications for Internet of things based on UAV

Related Author

WU Huici

GONG Zijun

JIANG Fan

LEI Ting

TAO Xiaofeng

Jijun ZHAO

Cunxi CHANG

Zhongcheng WEI

Related Institution

National Engineering Research Center of Mobile Network Technologies, Beijing University of Posts and Telecommunications

Department of Broadband Communication, Peng Cheng Laboratory (PCL)

IOT Thrust, The Hong Kong University of Science and Technology

School of Information and Electrical Engineering, Hebei University of Engineering

Hebei Key Laboratory of Security and Protection Information Sensing and Processing

⁰