基于车辆与无人机协同的巡检任务分配与路径规划算法

doi:10.6040/j.issn.1672-3961.0.2024.338

摘要/Abstract

摘要： 为了研究地面车辆与无人机在巡检过程中的最佳任务分配策略及路径规划问题,提出一种两阶段混合式启发算法——改进自适应大邻域搜索(improved adaptive large neighborhood search, IALNS)算法。第一阶段根据待巡检节点的不同需求等级及距离等因素,利用聚类算法对目标节点进行划分;第二阶段采用一种混合式启发算法解决路线调度问题,增加6种新的局部优化算子,引入节点重分配策略,经过迭代得到成本最小的车辆与无人机协同混合路线。对所提算法解和其他算法解进行测试和比较分析,试验数据表明,IALNS算法在解决车辆与无人机协同巡检问题时具有显著优势。

关键词: 路径规划, 车辆与无人机协同模式, 聚类算法, 自适应大邻域搜索, 局部优化

Abstract: To study the optimal task allocation strategy and path planning problem of ground vehicles and unmanned aerial vehicles(UAVs)in the inspection process, an improved adaptive large neighborhood search(IALNS)algorithm—a two-stage hybrid heuristic algorithm—was proposed. In the first stage, a clustering algorithm was used to divide the target nodes according to the different demand levels and distances of the nodes to be inspected. In the second stage, a hybrid heuristic algorithm was used to solve the route scheduling problem. Six new local optimization operators were added, and a node redistribution strategy was introduced. The cooperative hybrid route with the minimum cost for vehicles and UAVs was obtained after iterations. The proposed algorithm solutions and other algorithm solutions were tested and comparatively analyzed, and the experimental data showed that the IALNS algorithm had significant advantages in solving the vehicles-UAVs cooperative inspection problem.

Key words: path planning, vehicles-UAVs cooperative mode, clustering algorithm, adaptive large neighborhood search, local optimization

中图分类号:

TP18

李晓辉,刘小飞,孙炜桐,赵毅,董媛,靳引利. 基于车辆与无人机协同的巡检任务分配与路径规划算法[J]. 山东大学学报 (工学版), 2025, 55(5): 101-109.

LI Xiaohui, LIU Xiaofei, SUN Weitong, ZHAO Yi, DONG Yuan, JIN Yinli. An inspection task assignment and path planning algorithm based on vehicles-UAVs collaboration[J]. Journal of Shandong University(Engineering Science), 2025, 55(5): 101-109.

参考文献

[1] 邵强, 万力. 多旋翼无人机在输电线路巡检中的运用及发展[J]. 中国新通信, 2019, 21(16): 106. SHAO Qiang, WAN Li. Utilization and development of multi-rotor UAV in transmission line inspection[J]. China New Telecommunications, 2019, 21(16): 106.
[2] ERSUE E, WIENAND S. Method for planning an inspection path for determining areas that are to be inspected: US8059151[P]. 2011-11-15.
[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.
[4] AGATZ N, BOUMAN P, SCHMIDT M. Optimization approaches for the traveling salesman problem with drone[J]. Transportation Science, 2018, 52(4): 965-981.
[5] MARINELLI M, CAGGIANI L, OTTOMANELLI M, et al. En route truck-drone parcel delivery for optimal vehicle routing strategies[J]. IET Intelligent Transport Systems, 2018, 12(4): 253-261.
[6] HA Q M, DEVILLE Y, PHAM Q D, et al. On the min-cost traveling salesman problem with drone[J]. Transportation Research Part C: Emerging Technologies, 2018, 86: 597-621.
[7] YOON J J. The traveling salesman problem with multiple drones: an optimization model for last-mile delivery[D]. Cambridge, UK: Massachusetts Institute of Techno-logy, 2018.
[8] 曹英英, 陈淮莉. 基于集群的卡车与无人机联合配送调度研究[J]. 计算机工程与应用, 2022, 58(11): 287-294. CAO Yingying, CHEN Huaili. Research on truck and drone joint distribution scheduling based on cluster[J]. Computer Engineering and Applications, 2022, 58(11): 287-294.
[9] WANG X, POIKONEN S, GOLDEN B. The vehicle routing problem with drones: several worst-case results[J]. Optimization Letters, 2017, 11(4): 679-697.
[10] WANG Z, SHEU J B. Vehicle routing problem with drones[J]. Transportation Research Part B: Methodo-logical, 2019, 122: 350-364.
[11] 马华伟, 闫伯英. 面向防疫物资分区配送车机协同路径规划问题[J]. 系统仿真学报, 2025, 37(1): 234-244. MA Huawei, YAN Boying. Vehicle routing problem with drones considering zoned distribution of epidemic prevention materials[J]. Journal of System Simulation, 2025, 37(1): 234-244.
[12] SCHERMER D, MOEINI M, WENDT O. A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations[J]. Computers & Operations Research, 2019, 109: 134-158.
[13] LEI D M, CUI Z Z, LI M. A dynamical artificial bee colony for vehicle routing problem with drones[J]. Engineering Applications of Artificial Intelligence, 2022, 107: 104510.
[14] 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.
[15] LIU Y, LIU Z, SHI J M, et al. Two-echelon routing problem for parcel delivery by cooperated truck and drone[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(12): 7450-7465.
[16] TAMKE F, BUSCHER U. A branch-and-cut algorithm for the vehicle routing problem with drones[J]. Transportation Research Part B: Methodological, 2021, 144: 174-203.
[17] ZHANG J, LI Y F. Collaborative vehicle-drone distri-bution network optimization for perishable products in the epidemic situation[J]. Computers & Operations Research, 2023, 149: 106039.
[18] KONG F H, JIANG B. Delivery optimization for collaborative truck-drone routing problem considering vehicle obstacle avoidance[J]. Computers & Industrial Engineering, 2024, 198: 110659.
[19] GU R X, LIU Y, POON M. Dynamic truck-drone routing problem for scheduled deliveries and on-demand pickups with time-related constraints[J] Transportation Research Part C: Emerging Technologies, 2023, 151: 104139.
[20] STODOLA P, KUTĚJ L.Multi-depot vehicle routing problem with drones: mathematical formulation, solution algorithm and experiments[J]. Expert Systems with Applications, 2024, 241: 122483.
[21] LI M, CAI K Q, ZHAO P. Optimizing same-day delivery with vehicles and drones: a hierarchical deep reinforcement learning approach[J]. Transportation Research Part E: Logistics and Transportation Review, 2025, 193: 103878.
[22] JIANG Y, LIU M M, JIA X B, et al. The multi-visit vehicle routing problem with multiple heterogeneous drones[J]. Transportation Research Part C: Emerging Technologies, 2025, 172: 105026.
[23] ZHOU J, YI J, YANG Z Y, et al. A survey on vehicle-drone cooperative delivery operations optimization: models, methods, and future research directions[J]. Swarm and Evolutionary Computation, 2025, 92: 101780.
[24] MAHMOUDI B, ESHGHI K. Energy-constrained multi-visit TSP with multiple drones considering non-customer rendezvous locations[J]. Expert Systems with Appli-cations, 2022, 210: 118479.
[25] SACRAMENTO D, PISINGER D, ROPKE S. An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones[J]. Transportation Research Part C: Emerging Technologies, 2019, 102: 289-315.

相关文章 15

[1]	赵红专,张鑫,张蓓聆,展新,李文勇,袁泉,王涛,周旦. 基于改进人工势场的智能车动态安全椭圆路径规划方法[J]. 山东大学学报 (工学版), 2025, 55(3): 46-57.
[2]	韩毅,刘毅超,关甜,兰理文,汤宁业. 改进A^*和动态窗口法的无人车路径规划[J]. 山东大学学报 (工学版), 2025, 55(3): 16-24.
[3]	张飞凯,夏拥军,秦剑,游溢,彭飞. 基于A^*算法的输电线路组塔施工吊装路径规划方法[J]. 山东大学学报 (工学版), 2024, 54(3): 141-148.
[4]	黄健堃,薛钢,刘延俊,王雨,李厚池,白发刚. 基于改进Bi-RRT算法的机器鱼路径规划方法[J]. 山东大学学报 (工学版), 2024, 54(1): 74-82.
[5]	李兆彬,叶军,周浩岩,卢岚,谢立. 变异萤火虫优化的粗糙K-均值聚类算法[J]. 山东大学学报 (工学版), 2023, 53(4): 74-82.
[6]	赵天怀,王目树,潘为刚,康超,秦石铭,徐飞. 挖掘机智能辅助施工系统设计[J]. 山东大学学报 (工学版), 2023, 53(4): 163-172.
[7]	王雨,刘延俊,贾华,薛钢. 基于强化RRT算法的机械臂路径规划[J]. 山东大学学报 (工学版), 2022, 52(6): 123-130.
[8]	张飞凯,黄永忠,李连茂,秦剑,刘晨. 基于Dijkstra算法的货运索道路径规划方法[J]. 山东大学学报 (工学版), 2022, 52(6): 176-182.
[9]	肖浩,廖祝华,刘毅志,刘思林,刘建勋. 实际环境中基于深度Q学习的无人车路径规划[J]. 山东大学学报 (工学版), 2021, 51(1): 100-107.
[10]	李彩虹,方春,王志强,夏斌,王凤英. 基于超混沌同步控制的移动机器人全覆盖路径规划[J]. 山东大学学报 (工学版), 2019, 49(6): 63-72.
[11]	周风余, 万方, 焦建成, 边钧健. 家庭陪护机器人自主充电系统研究与设计[J]. 山东大学学报 (工学版), 2019, 49(1): 55-65.
[12]	张强. 核环境多关节蛇形机械臂的运动控制系统设计[J]. 山东大学学报 (工学版), 2018, 48(6): 122-131.
[13]	吉兴全,韩国正,李可军,傅荣荣,朱仰贺. 基于密度的改进K均值聚类算法在配网区块划分中的应用[J]. 山东大学学报(工学版), 2016, 46(4): 41-46.
[14]	陈文强1,林琛1,2,陈珂3,陈锦秀1,邹权1,2*. 基于GraphLab的分布式近邻传播聚类算法[J]. 山东大学学报(工学版), 2013, 43(5): 13-18.
[15]	刘彬,张仁津. 一种采用两段粒子群优化的路径规划方法[J]. 山东大学学报(工学版), 2012, 42(1): 12-18.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed