考虑能耗分段的物流无人机调度模型

doi:10.3778/j.issn.1002-8331.2104-0348

摘要/Abstract

摘要： 无人机由于自身性能，能耗是限制其配送范围的重要因素之一。针对现有研究粗略限制无人机飞行距离或时间，导致实际运行中无人机电池电量不足而无法完成所有配送任务或安全返回回收点问题，提出能耗分段模型，精确计算物流无人机在配送过程的能耗，可以保障实际配送方案的实施。研究中根据无人机有效载荷、电池电量以及配送过程构建能耗分段模型。将有效载荷与两点距离作为每段能耗的决策变量，目标为总配送路长最小，采用改进差分进化算法对模型求解。运用标准算例集场景进行测试。结果表明考虑能耗分段相较于不分段模型，能耗减小7%~23%，路长平均缩短11.9%。单配送中心多需求点问题中，考虑能耗分段模型可以既保证配送方案可行，又提高了无人机货物交付效率，高效完成配送任务。

关键词: 无人机配送, 能耗分段, 改进差分算法, 物流调度

Abstract: Due to its own performance, energy consumption is one of the important factors limiting unmanned aerial vehicle（UAV） distribution range. According to the existing research, the flight distance or time of UAV is roughly limited, it leds to the problem of the battery power of on-board UAV in actual operation is insufficient and it can not complete all the distribution tasks or return to the recovery point safely. A segmented energy consumption model is proposed to accurately calculate the energy consumption of logistics UAV in the delivery process, it can guarantee the implementation of the actual delivery plan. Firstly, a segmenting energy consumption model is built according to the UAV payload, battery capacity and distribution process. Secondly, the distance between the payload and the two points is taken as the decision variable of energy consumption for each segment, and the goal is to minimize the total distribution route length. The improved differential evolution algorithm is used to solve the model. Finally, the standard case set scenario is used to tested. The results show that compared with the non-segmented model, the energy consumption is reduced by 7%-23% and the road length is shortened by 11.9% on average considering segmented model. In the problem of single distribution center and multiple demand points, considering the segmented model of energy consumption can not only ensure the feasibility of the distribution scheme, but also improve the efficiency of UAV cargo delivery and efficiently complete the distribution task.

Key words: UAV distribution, energy consumption segmentation, improved difference algorithm, logistics scheduling

任新惠, 武彤. 考虑能耗分段的物流无人机调度模型[J]. 计算机工程与应用, 2022, 58(21): 301-308.

REN Xinhui, WU Tong. Logistics Unmanned Aerial Vehicles Scheduling Model Considering Energy Consumption Segmentation[J]. Computer Engineering and Applications, 2022, 58(21): 301-308.

参考文献

[1] JEONG H Y，SONG B D，LEE S.Truck-drone hybrid delivery routing：payload-energy dependency and no-fly zones[J].International Journal of Production Economics，2019，214：220-233.
[2] 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.
[3] KIM S J，LIM G J.Drone-aided border surveillance with an electrification line battery charging system[J].Journal of Intelligent & Robotic Systems，2018，92：657-670.
[4] KIM S J，LIM G J.A hybrid battery charging approach for drone-aided border surveillance scheduling[J].Drones，2018，2（4）：38.
[5] HONG I，KUBY M，MURRAY A T.A range-restricted recharging station coverage model for drone delivery service planning[J].Transportation Research Part C：Emerging Technologies，2018，90：198-212.
[6] YUREK E E，OZMUTLU H C.A decomposition-based iterative optimization algorithm for traveling salesman problem with drone[J].Transportation Research Part C：Emerging Technologies，2018，91：249-262.
[7] OLIVARES V，CORDOVA F，SEPúLVEDA J M，et al.Modeling internal logistics by using drones on the stage of assembly of products[J].Procedia Computer Science，2015，55：1240-1249.
[8] DUKKANCI O，KARA B Y，BEKTA T.Minimizin genergy and cost in range-limited drone deliveries with speed optimization[J].Transportation Research Part C：Emerging Technologies，2021，125（4）：102985.
[9] ZENG Y，XU J，ZHANG R.Energy minimization for wireless communication with rotary-wing UAV[J].IEEE Transactions on Wireless Communication，2019，18（4）：2329-2345.
[10] ZHANG J，CAMPBELL J F，DONALD I I，et al.Energy consumption models for delivery drones：a comparison and assessment[J].Transportation Research Part D：Transport and Environment，2021，90：102668.
[11] MACRINA G，DI PUGLIA PUGLIESE L，GUERRIERO F，et al.Drone-aided routing：a literature review[J].Transportation Research Part C：Emerging Technologies，2020，120：102762.
[12] TORABBEIGI M，LIM G J，KIM S J.Drone delivery scheduling optimization considering payload-induced battery consumption rates[J].Journal of Intelligent & Robotic Systems，2020，97（3）：471-487.
[13] 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.
[14] MURRAY C C，RAJ R.The multiple flying sidekicks traveling salesman problem with variable drone speeds[J].Transportation Research Part C：Emerging Technologies，2020，120：102813.
[15] TROUDI A，ADDOUCHE S A，DELLAGI S，et al.Sizing of the drone delivery fleet considering energy autonomy[J].Sustainability，2018，10（9）：3344.
[16] LIU Y，LIU Z，SHI J，et al.Two-echelon routing problem for parcel delivery by cooperated truck and drone[J].IEEE Transactions on Systems，Man，and Cybernetics：Systems，2020，99：1-16.
[17] D’ANDREA R.Guest editorial can drones deliver?[J].IEEE Transactions on Automation Science & Engineering，2014，11（3）：647-648.
[18] 邬开俊，王铁君.基于改进差分进化的车辆路径优化算法[J].计算机工程与应用，2013，49（13）：17-20.
WU K J，WANG T J.Vehicle routing problem algorithm based on improved differential evolution[J].Computer Engineering and Applications，2013，49（13）：17-20.