Research on a UAV Task Allocation and Path Planning Model Based on Dynamic Payload
-
摘要: 城市末端物流无人机配送受载重与电池容量限制，现有研究多采用固定载重与续航距离约束，难以反映多站点配送中载重递减对能耗计算与回路可行性的影响。针对单配送中心场景，将动态载重能耗计算嵌入任务分配与路径规划，构建以无人机固定使用成本、航程成本、能耗成本和时间窗违反成本之和最小为目标的模型。将该问题抽象为带软时间窗的容量车辆路径问题（capacitated vehicle routing problem with time windows，CVRPTW），按照站点访问顺序逐航段更新无人机剩余载重；将运行过程划分为垂直起飞、水平飞行和垂直降落3个阶段，考虑空气密度随高度变化和起降次数累积，建立动态载重分阶段能耗模型，将回路能耗成本纳入总经济成本。设计两阶段算法求解: 第一阶段设计改进A*算法搜索站点间最短避障路径，设计定向搜索和双向同步扩展策略减少无效搜索，经贪心剪枝形成距离矩阵；第二阶段基于该矩阵，设计改进C-WSA算法合并初始回路，将距离节约值扩展为4项成本的综合经济节约值，构造任务回路。仿真结果表明，模型形成7条可行配送回路，起降能耗占各回路总能耗的22.53%~30.20%。无能耗约束下航程缩短10.92%，但造成回路实际能耗超限不可行；在相同配送回路下，采用等效恒定载重与逐航段动态载重方式计算的总能耗相差16.38%，动态载重计算不可忽略。改进A*算法的搜索时间缩短了73.57%，改进C-WSA算法的总经济成本降低了26.38%~36.64%。Abstract: To capture the effects of payload reduction on energy estimation and route feasibility in multi-stop deliv ery, a joint UAV task allocation and path planning model is developed. The model considers a single-depot scenario and minimizes fixed UAV utilization, travel, energy, and time-window violation costs. The problem is formulated as a capacitated vehicle routing problem with time windows (CVRPTW), in which time-window violations incur additional costs. The remaining payload is updated for each flight segment according to the delivery-station visitation sequence. UAV operations are divided into vertical takeoff, horizontal flight, and vertical landing. A phase-based dynamic-payload energy model accounts for altitude-dependent air density and the cumulative effects of repeated takeoffs and landings. The resulting route energy cost is incorporated into the total economic cost. A two-stage solution method is designed. In the first stage, an improved A* algorithm searches for the shortest obstacle-avoiding paths between stations. Directional search and synchronous bidirectional expansion reduce redundant searches, while greedy pruning is applied to construct the distance matrix. In the second stage, an improved Clarke-Wright savings algorithm (C-WSA) merges the initial routes based on this matrix. The distance-based savings metric is extended to a composite economic savings metric comprising the four cost components. Simulation results show that the model generates seven feasible delivery routes. Takeoff and landing energy accounts for 22.53%—30.20% of the total energy consumption of each route. Removing the energy constraint reduces total travel distance by 10.92% but produces infeasible routes whose energy consumption exceeds the battery capacity. For the same delivery routes, total energy estimates from equivalent constant-payload and segment-wise dynamic-payload calculations differ by 16.38%. This difference indicates that dynamic-payload effects cannot be neglected in energy estimation. The improved A* algorithm reduces search time by 73.57% relative to the conventional A* algorithm. The improved C-WSA reduces total economic cost by 26.38%—36.64% relative to the benchmark algorithms. These results demonstrate the effectiveness of the proposed two-stage solution method.
-
Key words:
- low-altitude logistics /
- UAV delivery /
- path planning /
- improved A* algorithm /
- task allocation
-
图 6 无人机任务分配与路径规划结果（平滑前）
Figure 6. UAV task allocation and path planning results (before smoothing)
图 7 无人机任务分配与路径规划结果（平滑后）
Figure 7. UAV task allocation and path planning results (after smoothing)
图 10 障碍物栅格占比对相关指标的影响
Figure 10. The influence of obstacle grid ratio on related parameters
表 1 无人机相关参数
Table 1. UAV related parameters
参数 取值 无人机空载质量Mu/kg 35 最大载重$ W^{\max} $/kg 15 最大电池容量$ B^{\max} $/(kW·h) 2.5 平飞速度uc/(m/s) 10 垂直起飞速度ut/(m/s) 4 垂直降落速度ul/(m/s) 4 单位架次无人机固定使用费用c1/(元/架次) 2 单位距离无人机维护费用c2/(元/km) 0.5 单位能耗无人机维护费用c3/(元/(kW·h)) 0.2 提前时间惩罚因子γ1/(元/min) 1 延迟时间惩罚因子γ2/(元/min) 1.5 
下载: 导出CSV
表 2 无人机任务分配与路径规划结果
Table 2. UAV task allocation and path planning results
序号 访问序列 初始载重/kg 时间窗违反成本/元 航程成本/元 能耗成本/元 起降能耗占比/% 总经济成本/元 1 wh-n1-n3-n4-n6-n8-wh 14.3 8.95 4.10 0.50 26.63 15.55 2 wh-n18-n27-n2-n5-n7-wh 14.0 5.04 3.62 0.43 29.17 11.08 3 wh-n13-n14-n12-n11-n9-wh 14.4 0.86 4.24 0.48 26.00 7.58 4 wh-n10-n26-n23-n21-wh 10.1 12.16 2.81 0.35 30.20 18.01 5 wh-n28-n19-n17-wh 12.7 0.00 2.81 0.29 27.22 5.01 6 wh-n16-n15-n30-n20-wh 10.1 2.22 4.33 0.46 22.57 8.90 7 wh-n25-n24-n29-n22-wh 13.4 0.00 4.25 0.47 22.53 6.22
下载: 导出CSV
表 3 是否考虑能耗约束的任务分配与路径规划结果
Table 3. UAV task allocation and path planning results with and without the energy constrain
序号 含能耗约束 无能耗约束 访问次序 航程/km 总能耗/(kW·h) 访问次序 航程/km 总能耗/(kW·h) 1 wh-n1-n3-n4-n6-n8-wh 8.19 2.48 wh-n1-n3-n4-n6-n8-n7-wh 8.58 2.77 2 wh-n18-n27-n2-n5-n7-wh 7.23 2.15 wh-n13-n14-n12-n11-n9-n10-wh 8.59 2.69 3 wh-n13-n14-n12-n11-n9-wh 8.47 2.42 wh-n5-n2-n27-n18-wh 6.02 1.78 4 wh-n10-n26-n23-n21-wh 5.63 1.73 wh-n17-n16-n15-n30-n20-wh 9.87 2.82 5 wh-n28-n19-n17-wh 5.61 1.44 wh-n28-n21-n23-n19-wh 4.86 1.49 6 wh-n16-n15-n30-n20-wh 8.66 2.32 wh-n26-n25-n24-n29-n22-wh 8.66 2.59 7 wh-n25-n24-n29-n22-wh 8.50 2.35 合计 52.29 14.88 46.58 14.14
下载: 导出CSV
表 4 不同载重下能耗计算结果
Table 4. Energy consumption estimates from average-payload and dynamic-payload calculations
序号 等效恒定载重 逐航段动态载重 能耗估算差距/% 平飞能耗/(kW·h) 起降能耗/(kW·h) 总能耗/(kW·h) 平飞能耗/(kW·h) 起降能耗/(kW·h) 总能耗/(kW·h) 1 2.20 0.71 2.91 1.82 0.66 2.48 14.82 2 1.92 0.70 2.62 1.52 0.63 2.15 18.12 3 2.12 0.70 2.82 1.79 0.63 2.42 14.34 4 1.41 0.66 2.07 1.21 0.52 1.73 16.36 5 1.31 0.43 1.74 1.05 0.39 1.44 17.28 6 2.20 0.57 2.77 1.79 0.52 2.32 16.45 7 2.22 0.64 2.86 1.82 0.53 2.35 17.74 合计 17.80 14.88 16.38
下载: 导出CSV
表 5 寻路算法对比
Table 5. Algorithm comparison
算法 算法性能 路径节点数 生成节点数 扩展节点数 搜索时间/s 改进A* 107 10 925 5 709 2.297 3 A* 140 13 605 10 451 8.693 5 GA 381 252 682 5 601 002 521.993 7 RRT 121 12 936 13 421 2.373 1
下载: 导出CSV
表 6 任务分配算法对比
Table 6. Comparison of task allocation algorithms
算法 任务架次 总航程/km 总能耗/(kW·h) 时间窗违反成本/元 总经济成本/元 运行时间/s 改进C-WSA 7 52.29 14.88 29.23 72.35 4.24 GA 8 58.34 15.97 49.92 98.28 9.24 ACO 7 50.48 14.56 72.03 114.18 21.07 PSO 8 59.43 16.26 63.09 112.06 13.66
下载: 导出CSV
表 7 栅格分辨率对算法性能的影响
Table 7. The effect of grid resolution on the quality of the solution
栅格分辨率/m 算法性能 路径节点数 生成节点数 扩展节点数 搜索时间/s 50 138 13 816 7 438 4.440 8 100 107 10 925 5 709 2.297 3 200 104 7 793 3 764 1.164 9
下载: 导出CSV
表 8 障碍物栅格占比对算法性能的影响
Table 8. The influence of obstacle grid ratio on the quality of the solution
障碍物栅格占比/% 算法性能 路径节点数 生成节点数 扩展节点数 搜索时间/s 5 107 10 925 5 709 2.297 3 10 124 13 056 6 282 2.421 9 15 136 15 010 7 346 3.892 1 20 154 19 688 9 327 5.396 8
下载: 导出CSV
表 9 站点规模对算法性能的影响
Table 9. The influence of site size on the quality of the solution
站点规模/个 算法性能 路径节点数 生成节点数 扩展节点数 搜索时间/s 30 107 10 925 5 709 2.297 3 60 204 44 579 12 180 10.794 4 90 338 79 080 22 630 31.129 7
下载: 导出CSV
-
[1] 胡文晓, 牟迪, 李智, 等. 低空经济发展的关键技术问题与创新策略[J]. 航空学报, 2025, 46(11): 531539.HU W X, MOU D, LI Z, et al. Key technical issues and innovation strategies for development of low-altitude economy[J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531539. (in Chinese) [2] LI Z, LI S, LU J, et al. Air route network planning method of urban low-altitude logistics UAV with double-layer structure[J]. Drones, 2025, 9(3): 193. doi: 10.3390/drones9030193 [3] 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. doi: 10.1016/j.trc.2015.03.005 [4] RODRIGUES T A, PATRIKAR J, OLIVEIRA N L, et al. Drone flight data reveal energy and greenhouse gas emissions savings for very small package delivery[J]. Patterns, 2022, 3(8): 100569. doi: 10.1016/j.patter.2022.100569 [5] 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. doi: 10.1109/TSMC.2016.2582745 [6] TROUDI A, ADDOUCHE S A, DELLAGI S, et al. Sizing of the drone delivery fleet considering energy autonomy[J]. Sustainability, 2018, 10(9): 3344. doi: 10.3390/su10093344 [7] 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-4): 471-487. [8] WEN X, WU G. Heterogeneous multi-drone routing problem for parcel delivery[J]. Transportation Research Part C: Emerging Technologies, 2022, 141: 103763. doi: 10.1016/j.trc.2022.103763 [9] SHI Y, 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. [10] LIU Y. Routing battery-constrained delivery drones in a depot network: a business model and its optimization-simulation assessment[J]. Transportation Research Part C: Emerging Technologies, 2023, 152: 104147. doi: 10.1016/j.trc.2023.104147 [11] DENG M, YANG Q, PENG Y. A real-time path planning method for urban low-altitude logistics UAVs[J]. Sensors, 2023, 23(17): 7472. doi: 10.3390/s23177472 [12] MA Z, XIONG J, GONG H, et al. Mission planning of UAVs and CAVs based on graph neural network transformer model[J]. IEEE Internet of Things Journal, 2024, 11(24): 40532-40546. doi: 10.1109/JIOT.2024.3451248 [13] 任新惠, 芮钰琪. 基于配送服务模式及路径策略的物流无人机调度模型[J]. 北京交通大学学报, 2024, 48(3): 1-14.REN X H, RUI Y Q. Logistics drone scheduling model based on delivery service modes and routing strategies[J]. Journal of Beijing Jiaotong University, 2024, 48(3): 1-14. (in Chinese) [14] 王飞, 杨清平. 面向多无人机物流配送的双层任务规划方法[J]. 北京航空航天大学学报, 2026, 52(1): 94-103.WANG F, YANG Q P. Two-layer task planning method for multi-UAV logistics distribution[J]. Journal of Beijing University of Aeronautics and Astronautics, 2026, 52(1): 94-103. (in Chinese) [15] LIU Z Y, LI L H, ZHANG X, et al. Considering both energy effectiveness and flight safety in UAV trajectory planning for intelligent logistics[J]. Vehicular Communications, 2025, 52: 100885. doi: 10.1016/j.vehcom.2025.100885 [16] 郭家赫, 高岳林, 柳迎春. 多固定翼无人机的任务分配和路径规划算法[J]. 太原理工大学学报, 2025, 56(2): 348-355.GUO J H, GAO Y L, LIU Y C. Task allocation and path planning algorithms for multi-fixed-wing UAV[J]. Journal of Taiyuan University of Technology, 2025, 56(2): 348-355. (in Chinese) [17] CHIANG W C, LI Y, SHANG J, et al. Impact of drone delivery on sustainability and cost: realizing the UAV potential through vehicle routing optimization[J]. Applied Energy, 2019, 242: 1164-1175. doi: 10.1016/j.apenergy.2019.03.117 [18] 唐伟, 宋笔锋, 曹煜, 等. 微小型电动垂直起降无人机总体设计方法及特殊参数影响[J]. 航空学报, 2017, 38(10): 220972.TANG W, SONG B F, CAO Y, et al. Preliminary design method for miniature electric-powered vertical take-off and landing unmanned aerial vehicle and effects of special parameters[J]. Acta Aeronautica et Astronautica Sinica, 2017, 38(10): 220972. (in Chinese) [19] 赵礼强, 刘雨欣, 王尔申, 等. 基于DMPC-A融合的多无人机路径规划算法[J]. 交通信息与安全, 2025, 43(5): 180-190.ZHAO L Q, LIU Y X, WANG E S, et al. Multi-UAV path planning algorithm based on DMPC-A fusion[J]. Journal of Transport Information and Safety, 2025, 43(5): 180-190. (in Chinese) [20] GE H D, SUN B Y, ZHANG Y L. Intelligent path planning and collaborative exploration for complex environment under microgravity: an improved hybrid A* algorithm and region partitioning[J]. Aerospace Science and Technology, 2026, 168: 111090. doi: 10.1016/j.ast.2025.111090 [21] FADLAH T, SUTARMAN. Clarke and Wright savings algorithm as solutions vehicle routing problem with simultaneous pickup delivery (VRPSPD) [J]. Journal of Physics: Conference Series, 2023, 2421(1): 012045. doi: 10.1088/1742-6596/2421/1/012045 -
点击查看大图
计量
- 文章访问数: 14
- HTML全文浏览量: 10
- PDF下载量: 0
- 被引次数: 0