机巢充电情形下无人机电力巡检路径规划的强化遗传算法

doi:10.3778/j.issn.1002-8331.2407-0323

摘要/Abstract

摘要： 针对以机巢为充电站的无人机电力巡检路径规划问题，以最小化无人机执行任务总时间为目标构建数学模型，设计了一种强化遗传算法来求解该问题。在该算法中，提出了基于贪婪的种群初始化算子和基于split的可行解生成算子，并将遗传算法参数调优过程建模为马尔科夫决策过程，基于强化学习double Q-learning设计了交叉概率和变异概率的动态调优策略。在数值实验中，与Gurobi求解器、经典遗传算法、基于精英保留的遗传算法、差分进化算法的对比结果表明，该算法在求解质量和求解速度方面均具有显著优势；在案例分析中与现有巡检策略进行对比进一步验证了该算法在实际场景中的应用效果。

关键词: 电力巡检, 无人机（UAV）, 充电续航, 路径规划, 双Q学习, 强化遗传算法, 参数调优

Abstract: Aiming at the path planning problem of UAV power inspection with the machine nest as the charging station, a mathematical model is constructed to minimize the total time of UAV task execution, and a reinforcement genetic algorithm is designed to solve the problem. In this algorithm, a population initialization operator based on greed and a feasible solution generation operator based on split are proposed, and the parameter tuning process of genetic algorithm is modeled as a Markov decision process, and a dynamic tuning strategy of cross probability and mutation probability is designed based on double Q-learning. In numerical experiments, the results of comparison with Gurobi solver, classical genetic algorithm, genetic algorithm based on elite retention and differential evolution algorithm show that the algorithm has significant advantages in solving quality and solving speed. At the same time, in the case analysis, the comparison with the existing inspection strategy further verifies the application effect of the algorithm in the actual scene.

Key words: power inspection, unmanned aerial vehicle (UAV), charge and continue flying, route planning, double Q-learning, reinforcement genetic algorithm, parameter tuning

梁晨蕾, 罗贺, 蒋儒浩, 阴酉龙, 林世忠, 王国强. 机巢充电情形下无人机电力巡检路径规划的强化遗传算法[J]. 计算机工程与应用, 2025, 61(23): 316-328.

LIANG Chenlei, LUO He, JIANG Ruhao, YIN Youlong, LIN Shizhong, WANG Guoqiang. Reinforcement Genetic Algorithm for Path Planning of UAV Power Inspection with Nest Charging[J]. Computer Engineering and Applications, 2025, 61(23): 316-328.

参考文献

[1] 隋宇, 宁平凡, 牛萍娟, 等. 面向架空输电线路的挂载无人机电力巡检技术研究综述[J]. 电网技术, 2021, 45(9): 3636-3648.
SUI Y, NING P F, NIU P J, et al. A review of power inspection technology of mounted unmanned aerial vehicles for overhead transmission lines[J]. Power System Technology, 2021, 45(9): 3636-3648.
[2] 蒋丽, 王洪艳, 梁昌勇, 等. 农村地区卡车与无人机协同配送路径优化[J]. 计算机工程与应用, 2023, 59(14): 306-314.
JIANG L, WANG H Y, LIANG C Y, et al. Optimization of truck and drone collaborative distribution route in rural areas[J]. Computer Engineering and Applications, 2023, 59(14): 306-314.
[3] 许菱, 杨林超, 朱文兴, 等. 农村电商物流下无人机与车辆协同配送路径优化研究[J]. 计算机工程与应用, 2024, 60(1): 310-318.
XU L, YANG L C, ZHU W X, et al. Study on optimization of cooperative distribution path between UAVs and vehicles under rural e-commerce logistics[J]. Computer Engineering and Applications, 2024, 60(1): 310-318.
[4] LUO Y H, YU X, YANG D S, et al. A survey of intelligent transmission line inspection based on unmanned aerial vehicle[J]. Artificial Intelligence Review, 2023, 56(1): 173-201.
[5] 颜瑞, 陈立双, 朱晓宁, 等. 考虑区域限制的卡车搭载无人机车辆路径问题研究[J]. 中国管理科学, 2022, 30(5): 144-155.
YAN R, CHEN L S, ZHU X N, et al. Research on vehicle routing problem with truck and drone considering regional restriction[J]. Chinese Journal of Management Science, 2022, 30(5): 144-155.
[6] REED S, CAMPBELL A M, THOMAS B W. The value of autonomous vehicles for last-mile deliveries in urban environments[J]. Management Science, 2022, 68(1): 280-299.
[7] 戴永东, 黄政, 高超, 等. 多目标优化最低代价无人机机巢选址方法研究[J]. 重庆大学学报, 2023, 46(6): 136-144.
DAI Y D, HUANG Z, GAO C, et al. A UAV nest deployment method with multi-target optimization and minimum cost[J]. Journal of Chongqing University, 2023, 46(6): 136-144.
[8] 靳晓洁, 石建迈, 伍国华, 等. 无人机基站部署问题综述: 模型与算法[J]. 控制理论与应用, 2022, 39(12): 2219-2232.
JIN X J, SHI J M, WU G H, et al. Review of the UAV base station deployment problem: models and algorithms[J]. Control Theory & Applications, 2022, 39(12): 2219-2232.
[9] 王文豪, 殷旅江, 鄢曹政, 等. 基于文献计量和知识图谱的电动车辆路径问题研究综述[J]. 计算机工程与应用, 2024, 60(2): 46-62.
WANG W H, YIN L J, YAN C Z, et al. Review of research on electric vehicle routing problem based on bibliomerics and knowledge mapping[J]. Computer Engineering and Applications, 2024, 60(2): 46-62.
[10] 庄鹤林, 夏小云, 李康顺, 等. 电动汽车路径规划模型与算法研究进展[J]. 系统仿真学报, 2024, 36(2): 320-337.
ZHUANG H L, XIA X Y, LI K S, et al. Research advances on electric vehicle routing problem models and algorithms[J]. Journal of System Simulation, 2024, 36(2): 320-337.
[11] ZHOU B H, ZHAO Z. Multi-objective optimization of electric vehicle routing problem with battery swap and mixed time windows[J]. Neural Computing &Appliactions, 2022, 34(10): 7325-7348.
[12] ERDOGAN S, MILLER-HOOKS E. A green vehicle routing problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(1): 100-114.
[13] KUCUKOGLU I, DEWIL R, CATTRYSSE D. The electric vehicle routing problem and its variations: a literature review[J]. Computers & Industrial Engineering, 2021, 161: 107650.
[14] CHEN Y N, XUE J H, ZHOU Y M, et al. An efficient threshold acceptance-based multi-layer search algorithm for capacitated electric vehicle routing problem[J]. IEEE Transactions on Intelligent Transportation Systems, 2024, 25(6): 5867-5879.
[15] LIN B, GHADDAR B, NATHWANI J. Deep reinforcement learning for the electric vehicle routing problem with time windows[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(8): 11528-11538.
[16] CATAY B, SADATI I. An improved matheuristic for solving the electric vehicle routing problem with time windows and synchronized mobile charging/battery swapping[J]. Computers & Operations Research, 2023, 159: 106310.
[17] MAMCINI S. The hybrid vehicle routing problem[J]. Transportation Research Part C: Emerging Technologies, 2017, 78: 1-12.
[18] CHAO W, RONG L, YAN S, et al. Accelerating two-phase multiobjective evolutionary algorithm for electric location-routing problems[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(9): 9121-9136.
[19] HUNG Y, MICHAILIDIS G. A novel data-driven approach for solving the electric vehicle charging station location-routing problem[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(12): 23858-23868.
[20] ROCHA Y, SUBRAMANIAN A. Hybrid genetic search for the traveling salesman problem with hybrid electric vehicle and time windows[J]. Computers & Operations Research, 2023, 155: 106223.
[21] KARAKATI? S. Optimizing nonlinear charging times of electric vehicle routing with genetic algorithm[J]. Expert Systems with Applications, 2021, 164: 114039.
[22] JIA Y H, MEI Y, ZHANG M J. Confidence-based ant colony optimization for capacitated electric vehicle routing problem with comparison of different encoding schemes[J]. IEEE Transactions on Evolutionary Computation, 2022, 26(6): 1394-1408.
[23] SONG Y J, OU J W, SUGANTHAN P N, et al. Learning adaptive genetic algorithm for earth electromagnetic satellite scheduling[J]. IEEE Transactions on Aerospace and Electronic Systems, 2023, 59(6): 9010-9025.
[24] MOU J H, GAO K Z, DUAN P Y, et al. A machine learning approach for energy-efficient intelligent transportation scheduling problem in a real-world dynamic circumstances[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(12): 15527-15539.
[25] LIANG Z Y, LIU M, ZHONG P S, et al. Application research of a new neighbourhood structure with adaptive genetic algorithm for job shop scheduling problem[J]. International Journal of Production Research, 2023, 61(2): 362-381.
[26] LI R, GONG W Y, LU C. A reinforcement learning based RMOEA/D for bi-objective fuzzy flexible job shop scheduling[J]. Expert Systems with Applications, 2022, 203: 117380.
[27] CUI Y B, HU W, RAHMANI A. A reinforcement learning based artificial bee colony algorithm with application in robot path planning[J]. Expert Systems with Applications, 2022, 203: 117389.
[28] TAN Z P, TANG Y, LI K S, et al. Differential evolution with hybrid parameters and mutation strategies based on reinforcement learning[J]. Swarm and Evolutionary Computation, 2022, 75: 101194.
[29] HONG J L, SHEN B, PAN A Q. A reinforcement learning-based neighborhood search operator for multi-modal optimization and its applications[J]. Expert Systems with Applications, 2024, 246: 123150.
[30] SUN J Y, LIU X, BACK T, et al. Learning adaptive differential evolution algorithm from optimization experiences by policy gradient[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(4): 666-680.
[31] WANG T, FU L Y, WEI Z X, et al. Unmanned ground weapon target assignment based on deep Q-learning network with an improved multi-objective artificial bee colony algorithm[J]. Engineering Applications of Artificial Intelligence, 2023, 117: 105612.
[32] ZHOU H, QIN H, CHENG C, et al. An exact algorithm for the two-echelon vehicle routing problem with drones[J]. Transportation Research Part B: Methodological, 2023, 168: 124-150.
[33] 高云飞, 胡钰林, 刘鸣柳, 等. 多无人机输电线路巡检联合轨迹设计方法[J]. 电子与信息学报, 2024, 46(5): 1958-1967.
GAO Y F, HU Y L, LIU M L, et al. Joint multi-UAV trajectory design for power line inspection[J]. Journal of Electronics & Information Technology, 2024, 46(5): 1958-1967.
[34] ELEFTHERIADIS P, GIAZITZIS S, LEVA S, et al. Transfer learning techniques for the Lithium-Ion battery state of charge estimation[J]. IEEE Access, 2024, 12: 993-1004.
[35] CHEN R H, YANG B, LI S, et al. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem[J]. Computers & Industrial Engineering, 2020, 149: 106778.
[36] TANG H T, XIAO Y, ZHANG W, et al. A DQL-NSGA-III algorithm for solving the flexible job shop dynamic scheduling problem[J]. Expert Systems with Applications, 2024, 237: 121723.
[37] MICHALIS M, CHARALAMBOS M, STELIOS T, et al. Benchmark set for the IEEE WCCI-2020 competition on evolutionary computation for the electric vehicle routing problem[D]. Nicosia: University of Cyprus, 2020.