中国安全科学学报

变量符号	含义
G	G={n₁，n₂，…，n_n}网格节点坐标集合
n_k	TSP问题的起始和终止节点
S(n_i，n_j)	表示n_i和n_j节点间的路径为风险路径
c_ij	表示n_i和n_j节点间路径的距离
F	节点间的路径距离集合
v	涟漪的传播速度
D_max	涟漪的最大传播范围，等于最大节点间距离
Ω_A	处于激活状态涟漪的集合
Ω_S	处于等待状态涟漪的集合
E	E={e₁_j，e₂_j，…，e_ij}为链接集合
R_n	产生的第n个涟漪，按时间先后顺序产生

变量符号	含义
G	G={n₁，n₂，…，n_n}网格节点坐标集合
n_k	TSP问题的起始和终止节点
S(n_i，n_j)	表示n_i和n_j节点间的路径为风险路径
c_ij	表示n_i和n_j节点间路径的距离
F	节点间的路径距离集合
v	涟漪的传播速度
D_max	涟漪的最大传播范围，等于最大节点间距离
Ω_A	处于激活状态涟漪的集合
Ω_S	处于等待状态涟漪的集合
E	E={e₁_j，e₂_j，…，e_ij}为链接集合
R_n	产生的第n个涟漪，按时间先后顺序产生

节点数量/个	限制链接
5	1—5，2—4
10、11、12	1—5，6—7，3—8
13、14、15	2—3，4—6，1—9
16、17、18、19、20	3—5、4—7、1—6、2—8

节点数量/个	限制链接
5	1—5，2—4
10、11、12	1—5，6—7，3—8
13、14、15	2—3，4—6，1—9
16、17、18、19、20	3—5、4—7、1—6、2—8

节点数量	对比参数	穷举算法	RSA算法	遗传算法 (第1组)	遗传算法 (第2组)
5	路径长度/m	4 920.455 7	4 920.455 7	4 920.455 7	4 920.455 7
平均计算时间/s	0.003 6	0.062 5	0.204 6	0.204 6
10	路径长度/m	6 302.533 4	6 302.533 4	6 302.533 4	6 302.533 4
平均计算时间/s	1.703 1	0.328 1	0.343 7	1.451 6
11	路径长度/m	6 312.800 3	6 312.800 3	6 312.800 3	6 312.800 3
平均计算时间/s	18.904 0	0.3714	0.380 6	1.677 1
12	路径长度/m	—	6 518.413 2	6 995.178	6 518.413 2
平均计算时间/s	>12 h→43 200	0.609 4	0.437 5	1.698 9
13	路径长度/m	—	7 102.741 8	7255.3917	7179.808 6
平均计算时间/s	>12 h→43 200	0.640 6	0.454 7	1.821 5
14	路径长度/m	—	7 551.191 3	7703.8413	8212.586 8
平均计算时间/s	>12 h→43 200	2.625 0	0.447 3	2.162 9
15	路径长度/m	—	7 883.196 6	8 111.321 7	7 969.666 8
平均计算时间/s	>12 h→43 200	3.875 0	0.450 6	1.885 3
16	路径长度/m	—	8 224.882 9	8 290.993 4	8 290.993 4
平均计算时间/s	>12 h→43 200	12.578 1	0.504 2	2.106 1
17	路径长度/m	—	8 295.178 0	8 582.807 7	9 186.072 6
平均计算时间/s	>12 h→43 200	43.328 1	0.486 5	2.096 5
18	路径长度/m	—	8 347.271 1	8 654.3731	8 347.271 1
平均计算时间/s	>12 h→43 200	89.187 5	0.580 9	2.219 3
19	路径长度/m	—	8 424.510 6	9 725.751 1	9947.725 4
平均计算时间/s	>12 h→43 200	311.03 13	0.600 2	2.249 7
20	路径长度/m	—	8 435.145 6	8 727.888 6	8 497.369 1
平均计算时间/s	>12 h→43 200	469.062 5	0.592 3	2.382 3

节点数量	对比参数	穷举算法	RSA算法	遗传算法 (第1组)	遗传算法 (第2组)
5	路径长度/m	4 920.455 7	4 920.455 7	4 920.455 7	4 920.455 7
平均计算时间/s	0.003 6	0.062 5	0.204 6	0.204 6
10	路径长度/m	6 302.533 4	6 302.533 4	6 302.533 4	6 302.533 4
平均计算时间/s	1.703 1	0.328 1	0.343 7	1.451 6
11	路径长度/m	6 312.800 3	6 312.800 3	6 312.800 3	6 312.800 3
平均计算时间/s	18.904 0	0.3714	0.380 6	1.677 1
12	路径长度/m	—	6 518.413 2	6 995.178	6 518.413 2
平均计算时间/s	>12 h→43 200	0.609 4	0.437 5	1.698 9
13	路径长度/m	—	7 102.741 8	7255.3917	7179.808 6
平均计算时间/s	>12 h→43 200	0.640 6	0.454 7	1.821 5
14	路径长度/m	—	7 551.191 3	7703.8413	8212.586 8
平均计算时间/s	>12 h→43 200	2.625 0	0.447 3	2.162 9
15	路径长度/m	—	7 883.196 6	8 111.321 7	7 969.666 8
平均计算时间/s	>12 h→43 200	3.875 0	0.450 6	1.885 3
16	路径长度/m	—	8 224.882 9	8 290.993 4	8 290.993 4
平均计算时间/s	>12 h→43 200	12.578 1	0.504 2	2.106 1
17	路径长度/m	—	8 295.178 0	8 582.807 7	9 186.072 6
平均计算时间/s	>12 h→43 200	43.328 1	0.486 5	2.096 5
18	路径长度/m	—	8 347.271 1	8 654.3731	8 347.271 1
平均计算时间/s	>12 h→43 200	89.187 5	0.580 9	2.219 3
19	路径长度/m	—	8 424.510 6	9 725.751 1	9947.725 4
平均计算时间/s	>12 h→43 200	311.03 13	0.600 2	2.249 7
20	路径长度/m	—	8 435.145 6	8 727.888 6	8 497.369 1
平均计算时间/s	>12 h→43 200	469.062 5	0.592 3	2.382 3

基于实时备降安全约束的无人机风电场巡检路径规划

PDF下载

胡小兵 ¹ , 卢泽 ¹ , 李航 ¹ , 周航 ²

中国安全科学学报 | 安全工程技术 2025,35(2): 28-39

收起

中国安全科学学报 | 安全工程技术 2025, 35(2): 28-39

基于实时备降安全约束的无人机风电场巡检路径规划

全屏

胡小兵¹, 卢泽¹, 李航¹, 周航²

作者信息

¹ 中国民航大学安全科学与工程学院，天津 300300

² 中国民航大学中欧航空工程师学院，天津 300300

胡小兵 (1975—)，男，四川攀枝花人，博士，教授，主要从事计算智能、人工智能理论与方法研究。E-mail：huxb1975@163.com。

周航副教授

Unmanned aerial vehicle wind farm inspection path planning based on real-time potential landing safety constraints

Xiaobing HU¹, Ze LU¹, Hang LI¹, Hang ZHOU²

Affiliations

¹ College of Safety Science and Engineering，Civil Aviation University of China，Tianjin 300300，China

² College of Electronic Information and Automation，Civil Aviation University of China，Tianjin 300300，China

出版时间: 2025-02-28 doi: 10.16265/j.cnki.issn1003-3033.2025.02.0865

文章导航

摘要

收起

为提高无人机(UAV)风机巡检过程的巡检效率和安全性，合理规划无人机巡检路径，提出一种基于实时备降安全约束的无人机巡检路径规划方法。首先，基于风速风向影响下无人机的动态续航能力、航迹备降等约束条件，建立备降区安全性计算模型，评估巡检路径安全性，建立安全约束;然后，针对无人机巡检路径长度的目标函数，提出基于涟漪扩散算法(RSA)特征的最优巡检路径规划方法，依据RSA算法离散式、多智体的方法特点，在安全性约束下有效求解无人机风电场巡检的旅行商问题(TSP)，规划风电场巡检路径;最后，对于不同算法进行对比试验和风电场仿真试验。结果表明：实时备降安全约束模型能够综合不同的风险因素计算出安全路线，提高巡检路径的安全性，RSA算法则能够在保证精确度的条件下快速求解安全约束下的风电场巡检TSP问题，提高巡检路径规划水平。

关键词

实时备降 / 安全约束 / 风电场 / 无人机 (UAV) / 巡检 / 路径规划 / 涟漪扩散(RSA)算法 / 旅行商问题(TSP)

Abstract

收起

In order to improve the inspection efficiency and safety of UAV inspections for wind turbines，a reasonable planning of the UAV inspection path was proposed. A method for UAV inspection path planning based on real-time emergency landing safety constraints was introduced. First，a safety calculation model for emergency landing areas was established. It based on the dynamic endurance capacity of UAV affected by wind speed and direction，as well as constraints such as flight path emergency landing，to assess the safety of the inspection path and establish safety constraints. Then，regarding the objective function of the length of UAV inspection path，an optimal inspection path planning method based on the characteristics of RSA was proposed. This method effectively solved TSP for UAV inspections in wind farms under safety constraints，utilizing the discrete and multi-agent characteristics of RSA algorithm to plan the inspection path for wind farms. Finally，comparative experiments and simulations of wind farms were conducted for different algorithms. results indicated that the real-time emergency landing safety constraint model can comprehensively calculate safe routes by integrating various risk factors，enhancing the safety of the inspection path. RSA algorithm can quickly solve TSP problem for wind farm inspections under safety constraints，improving the level of inspection path planning.

Key words

real-time emergency landing / safety constraint / wind farm / unmanned aerial vehicle (UAV) / inspection / path planning / ripple spreading algorithm (RSA) / traveling salesman problem (TSP)

引用本文

胡小兵, 卢泽, 李航, 周航. 基于实时备降安全约束的无人机风电场巡检路径规划. 中国安全科学学报, 2025 , 35 (2) : 28 -39 . DOI: 10.16265/j.cnki.issn1003-3033.2025.02.0865

Xiaobing HU, Ze LU, Hang LI, Hang ZHOU. Unmanned aerial vehicle wind farm inspection path planning based on real-time potential landing safety constraints[J]. China Safety Science Journal, 2025 , 35 (2) : 28 -39 . DOI: 10.16265/j.cnki.issn1003-3033.2025.02.0865

正文

收起

0 引言

收起

随着我国风电行业的快速发展，风电安全生产及风机巡检成为该领域的核心议题。风电场数量的激增及巡检环境的日益复杂，为巡检工作带来了前所未有的挑战。在当前低空经济蓬勃发展背景下，无人机(Unmanned Aerial Vehicle，UAV)技术作为一种前沿且高效的技术手段，已成为电力行业的重要巡检手段之一^[1]。同时，这也对无人机巡检的安全性提出了更为严格的要求。

目前，该行业多采用风机停机巡检的无人机巡检方式，无人机每单次起飞巡检一台风机，效率低且经济成本较高。为寻求高效率、安全的巡检方式，将无人机巡检路径规划问题等同于一个小型的旅行商问题(Traveling Salesman Problem，TSP)进行研究。TSP作为一个完全组合路径优化问题，一直是计算机算法理论研究的热点话题。在现实工程中，许多优化问题可以建立TSP模型，各种针对该问题的算法也层出不穷^[2]。目前，求解TSP的算法主要分为精确算法和启发式算法2大类，两者的矛盾在于求解效率和求解精度的平衡。精确算法虽能保证求解的精度，但在大规模问题时效率不高。启发式算法能在较短时间内得到可行解，但存在易陷入局部最优、收敛速度较慢等问题。多年来学者们根据TSP问题的特性改进与应用了不同启发式算法，DENG Yanlan等^[3]提出了模拟退火混合细胞遗传算法;EZUGMU等^[4]提出了融合模拟退火的共生生物搜索优化算法;余丽等^[5]提出了遗传禁忌搜索算法;陈科胜等^[6]提出了自适应升温模拟退火算法;刘海龙等^[7]提出了改进融合灰狼优化算法等。在无人机的巡检安全与路径规划结合方面，张树卓等^[8]考虑风力对巡检无人机的影响，构建了在航程约束下无人机在常值风场下的巡检飞行时间代价模型；韩鹏等^[9]结合蚁群算法探究距离和安全双重约束条件下的航路规划方法;王猛等^[10]将时间窗和三维空间作为约束条件，在考虑安全威胁的情况下使用非支配排序遗传算法求解航迹规划问题。但这些研究不适用于风电场的TSP问题模型，并且鲜有对于备降安全约束做出描述的文献研究。

因此，笔者拟通过综合考虑无人机在风向风速影响下的有限续航能力，以及备降区域的安全性约束条件，以无人机巡检路径长度作为优化目标，构建TSP优化模型；并依据TSP问题的求解逻辑，设计涟漪扩散算法(Ripple Spreading Algorithm，RSA)，以更好地提高巡检路径求解的效率和精确度，同时确保能够有效规避潜在的安全风险，保障巡检作业的安全顺利进行。

1 基于备降安全的路径规划问题模型

收起

在规划无人机风电场巡检路径时，需要考虑对每台风机不可重复巡检等一系列约束条件，在保证实时备降安全性前提下，为风电场内分布在不同位置的所有风机规划最短的巡检路径，使得在最短时间、最短飞行距离内对规定区域内的所有风机完成巡检。由于在实际无人机巡检过程中情况较为复杂，故做如下假设:

1) 无人机备降的安全距离应由具体的无人机性能决定，常在无人机的基建手册中规定，以保证飞行器的安全备降和可作业时长。并且，由于风电场风速大、风向相对变化小，无人机续航距离应由具体风速风向影响下的航程计算公式计算。

2) 由于风电场规模较大，无人机无法一次起飞完成对风场内所有风机的巡检，需将风机依据无人机续航能力分组，一般6~13台为一组。且无人机沿预定航线飞行，包括上升、巡航和下降3个阶段，故在无人机降落时，规定无人机会先水平飞行到降落点上方，再进行垂直降落。

3) 无人机巡检路径长度仅包括在风机间的飞行路径长度，在实际巡检过程中，无人机还会针对每一台风机进行绕飞巡检，具体绕飞巡检长度根据风机风轮半径进行计算，所以巡检路径规划长度应小于无人机续航的10%。

图1为安全约束前后路径规划的具体示例模型，在模型中将不满足安全约束的路径定义为风险路径，满足安全约束的路径定义为安全路径。对于坐标系中{(0，2)，(3，5)，(3，3)(3，0)(6，4)(5，1)}中6个点生成最短路径，每2点间的距离即为路径成本，其中，1号点为起点，路径需遍历6个点之后回到起点，以完成对所有节点的巡检过程，图1中，所有节点间的路径都满足安全需求，算法计算的最优路径为1-3-2-4-5-6-1，而图2中由于2号点与5号点之间和3号与6号点的路径不满足安全需求，在路径选择时，不能选择风险路线作为路径，故对其进行不可达约束，所生成的最短TSP路径发生了改变，路径为1-2-3-4-5-6-1。

无人机在实时备降安全约束下的巡检路径规划问题可以描述为：无人机需在满足安全性约束的航线上，以最短距离对规定的风机进行绕飞巡检。现给定路网G={N，E}，其中，N={n₁，n₂，…，n_n}为节点集合;n_n为节点个数；E={e_ij

i ∈ N ， j ∈ N

}为链接集合，其中囊括了所有的相连节点间的链接;e_ij为节点i和节点j之间的链接;c_ij为节点i和节点j之间路径距离。是否实际可通行由x_ij∈(0，1)，(i，j)∈G决策变量所决定，表示节点i和节点j之间的链接是否可达，起点和终点定义为同一点n_k。s_ij∈(0，1)，(i，j)∈G为是否是安全路径的决策变量，其取值由安全性约束的计算决定，当s_ij取0时，不能够作为通行路径，即x_ij取0;当s_ij取1时，可作为通行路径，x_ij可以取0或1。

目标函数可以描述为从起点出发遍历所有的节点之后回到终点所经过的距离最短的路径:

$m i n ∑ i ∈ G ∑ j ∈ G ， i ≠ j c i j x i j$

具体的约束条件包括，在最短路径规划中的任一路径都应满足安全性，即每一条路径的安全约束因素s_ij都取1，表示为下式：

(1)

s i j = 1 ， ∀ i ， j ∈ G

在巡检过程中，每台风机只能由一个风机到达，并且每个风机只能到达一个风机，即：

(2)

∑ j ∈ G ， j ≠ i x i j = 1 ， ∀ i ∈ G

(3)

∑ i ∈ G ， i ≠ j x i j = 1 ， ∀ j ∈ G

在求解过程中，避免在求解TSP问题过程中子集合的产生，其表达式为：

(4)

∑ i ∈ S ∑ j ∈ S ， i ≠ j x i j ≤ S - 1 ， ∀ S ∈ V ， S ≥ 2

式中：S为风机集合;|S|为集合S中的元素个数。

无人机每次巡检所消耗的续航里程不可超过无人机的续航能力，见下式：

(5)

∑ i = 0 n ∑ j = 0 n c i j (t) x i j k ≤ E ， ∀ k ∈ K

无人机在受风影响下实际消耗的续航里程，如图3所示，设有2航点i和j，其距离为d_ij，无人机风阻系数和抗风能力分别为α和β，此时风速为v(t)，无人机航向与风向夹角为γ(t)。无人机飞过相同航段，由于风向风速以及飞行方向的不同，无人机所消耗的续航里程也不同。

无人机匀速飞过2航点所需要的时间、无人机在受风影响下实际消耗的续航里程和无人机完成所有巡检任务飞行的总里程，分别见下式：

(6)

Δ t i j = d i j V

(7)

c i j (t) = d i j × 1 - α c o s γ i j (t) × v (t) μ

(8)

D = ∑ k ∈ K ∑ i = 0 n ∑ j = 0 n c i j (t) x i j k

对于不同高度的风速，应用风廓线公式进行计算，其中，V_h表示高度为h处的风速，V_f为参考高度h_f处的风速，α为幂律指数，对于平坦、少树、少建筑的地方，α通常取0.14，其表达式为：

(9)

V h = V f h h f α

2 安全性约束

收起

安全性约束主要强调无人机在巡检过程中，当遇到影响无人机运行安全的众多要素时，如气象要素、地理要素和通信要素等^[11]，能够在安全时间内降落到备降区域，从而避免动态环境中未知意外导致的无人机损坏，及无人机损坏带来的意外伤害和财产损失，将无人机整个巡检过程保持在可控的飞行范围之内。针对无人机的飞行习惯和飞行规则，提出一种基于三维空间内的飞行路径到不规则图形备降区域内距离最近点的计算方法，其基本流程如图4所示。

2.1 备降区的定义

在备降区的算法设计中，规定无人机在巡检航线的任一位置都具有在备降航程之内的备降区域供无人机进行紧急备降，则将该路线定义为安全路线。同时在实际备降过程中优先选择最近的备降区域进行紧急备降。备降区范围在实际规划时，由于风电场多位于复杂自然环境中，备降区的选择受限于地形与成本，应依据风场的地形特征，实地勘测选定的开阔地带(如平地、公路、草地)作为备降区域。图5展示了稻田风场地形中的宽敞道路，并设为备降区域，供巡检无人机备降。

鉴于备降区形态和面积的不规则性，将其细分为若干面积均衡的小三角形，以实现高效的几何建模与安全性精细计算。如图6所示，在python中使用scipy库的Delaunay函数对输入的不规则图形进行三角剖分^[12]，并提取三角形栅格化后的每个小三角形的顶点坐标。通过将不规则图形进行三角剖分，简化了复杂区域的计算难度，为无人机备降区的安全性评估提供了更为精确的数学基础。

2.2 路径安全性判断原理

安全距离的计算即无人机沿规划路径飞行时，能否在安全时间内返回至备降区域。鉴于无人机尺寸与飞行速度的差异，对安全距离的需求也不同。

由于路径理论上由无限多个点组成，直接计算将增加数据的冗杂度，所以保障安全性的前提下，采用路径点云提取方法简化处理。假设2航点间距离为L，以d作为路径点云间距，即在距离为L的线段上每隔d间距提取一个路径点进行到备降区域的安全距离计算。在此过程中，优先评估与当前路径点距离较近的备降区域，一旦满足备降条件即终止当前计算，并继续对下一路径点执行相同流程，路径点云提取策略如图7所示。

有关路径点到备降点的距离f，提出以下计算方法:假设路径点为p，在xy平面内的投影点为p'，首先判断p'是否在备降区域内，路径点的集合为V={p₁，p₂，…，p_n}，备降区域三角形的集合为S={g₁，g₂，…，g_n}，若计算p'(x，y)是否在三角形区域g₁内，设g₁的3个顶点分别为A(x₁，y₁)，B(x₂，y₂)，C(x₃，y₃)对平面内任意一点都有：

(10)

p' = A + u · (C - A) + v · (B - A)

假设:v₀=C-A，v₁=B-A，v₂=P-A

计算：

(11)

u = ((v 1 · v 1) (v 2 · v 0) - (v 1 · v 0) (v 2 · v 1)) ((v 0 · v 0) (v 1 · v 1) - (v 0 · v 1) (v 1 · v 0))

(12)

v = ((v 0 · v 0) (v 2 · v 1) - (v 0 · v 1) (v 2 · v 0)) ((v 0 · v 0) (v 1 · v 1) - (v 0 · v 1) (v 1 · v 0))

若u≥0，v≥0，u+v≤1，则p'点位三角形g₁内部，在取‘=’时，p'点位于三角形边界上，在文中也判断为位于三角形内部，则路径点p₁到备降区g₁的距离为f=h，否则p₁则位于三角形g₁之外。重心坐标法如图8所示。

若p'点位于三角形之外，则计算p'点到三角形g₁最近的那条边的距离，依据平面内到直线的距离公式，点到AB、BC、CA的距离分别为：

(13)

d A B = | (x 2 - x 1) (y 1 - y) - (x 1 - x) (y 2 - y 1) | (x 2 - x 1) 2 + (y 2 - y 1) 2

(14)

d B C = | (x 3 - x 2) (y 2 - y) - (x 2 - x) (y 3 - y 2) | (x 3 - x 2) 2 + (y 3 - y 2) 2

(15)

d C A = | (x 1 - x 3) (y 3 - y) - (x 3 - x) (y 1 - y 3) | (x 1 - x 3) 2 + (y 1 - y 3) 2

(16)

d m i n = m i n (d A B ， d B C ， d A C)

路径点p₁到备降区g₁的距离为p₁的高度h加上点到三角形的最短距离d_min，即f=h+d_min。当安全距离为m时，若两航点间任一路径点到备降点的f>m，则该2航点间的路径s_ij取0即为风险路径;若2航点间的路径点所对应的所有f<m，则该2航点间的路径s_ij取1即为安全路径。对路径点V={p₁，p₂，…，p_n}依次进行到备降区的距离计算，其中，点集V所对应的距离集合为F={f₁，f₂，…，f_n}，并依次判断路径的安全性。

3 RSA设计

收起

3.1 基于RSA求解TSP问题的的算法设计

RSA是一种启发式优化算法^[13]，它通过模拟涟漪在水面上的扩散过程进行搜索，涟漪以相同的速度扩散，优先到达最近的节点，然后新的节点将会产生新的涟漪继续扩散。这一优化原理可以具体地应用于解决TSP问题，其自适应、并行化、基于多智体的算法特点，能够有效地适用于中小规模TSP问题的求解和局部最优解的搜索，提高算法的鲁棒性，为产生全局最优路径提供理论性保证。

将RSA应用于求解TSP问题，根据TSP问题特性设计微观智体的行为(即节点如何产生涟漪)和宏观终止条件(即涟漪接力赛何时结束)，其基本流程如图9所示。

针对实时备降安全约束条件下的风机节点间路径巡检规划问题，旨在通过融合风机节点与备降节点的安全性评估机制(基于第3节阐述的安全性计算原理)，对潜在巡检路径进行安全性分析。在确保所有路径均满足实时备降安全要求前提下，采用RSA算法优化路径规划策略，具体实施流程概述如下，流程中使用的符号说明见表1。

步骤1：初始化路网，给定TSP问题的网格节点坐标集合G、起始网格点n_k及不满足安全约束的风险路径S(n_i，n_j)，并计算出节点间的路径距离集合F。

步骤2：初始化各涟漪状态，设置涟漪的扩散速度v=minc_ij和涟漪的最大传播范围D_max=maxc_ij，并开始记录每个节点的涟漪信息，即表中8~9行，涟漪R₁从起点开始，通过网格向外扩散涟漪范围随时间增加，跟踪记录每个节点上新触发的涟漪数量和其对应的涟漪编号R_n，根据其涟漪半径和网络链接情况触发新的涟漪，更新涟漪的状态和路径信息，包括涟漪的半径，到达每个节点的总代价等。

步骤3：在涟漪扩散过程中由于将S(n_i，n_j)的距离视为无穷大，从而不选择其作为步进路径，检查涟漪是否已经覆盖了所有节点或超出了节点最大传播范围D_max，如超过则涟漪停止。

步骤5：算法会不断检查是否已经找到了覆盖所有节点的路径，当覆盖了所有节点并且路径当涟漪传播到达终止节点n_k时，记录下涟漪的传播路径。

步骤5:检查是否存在2个涟漪在网络链接的中间相遇。如果2个涟漪在链接的中间相遇，并且它们的涟漪节点数之和等于网络节点数加1，并且它们的涟漪半径之和大于或等于链接的2个节点之间的距离，那么说明发现了一条完整的TSP路径。

步骤6:将所有 TSP 路线和成本存储到Result 结构体中，取路径成本最小路线输出为TSP路径。

3.2 算法示例

图10为RSA求解安全约束下TSP问题的具体示例。RSA的涟漪接力赛从1号点处的涟漪R₁开始，R₁依次到达节点3、4、2、5，并依次触发新的涟漪(R₂、R₃、R₄、R₅)，R₁消失，因为它已经到达了与1号点相连的所有节点。产生的涟漪继续扩散，R₂到达节点2，在节点2处触发新的涟漪R₆，R₆应到达节点1、3、5，但由于这条路径已经到达过节点1和3，故无法在节点1和3处触发新的涟漪，又因为限制了节点2和节点5之间的链接，R₆也无法在节点5处触发新的涟漪，R₆将继续到达节点4触发新的涟漪。节点4产生的涟漪将到达节点5触发新的涟漪，节点5产生的涟漪将继续扩散到达节点1从而生成一条完整的TSP路径，即1-3-2-4-5-1。在涟漪的扩散过程中，涟漪不会到达路径中记录的节点和不满足安全约束的节点，且每到达一个节点，都会使路径的节点数减1，直至遍历所有节点后，最后一个节点产生的涟漪将会回到原点。在涟漪扩散的求解过程中，会有多个涟漪同时进行扩散从而计算最优路径，直至计算完所有路径之后，将停止扩散，但会优先输出最优路径。文中共有60条安全TSP路径，其中最短路径为1-2-3-5-4-1。

3.3 算法的最优性和复杂性分析

对于求解TSP的RSA的最优性和复杂性，有如下理论保证。

定理1：从起点出发，最先遍历所有节点回到起点的涟漪所经过的路径具有最优性。

证明:RSA通过恒定的涟漪扩散速度v扩散，在TSP问题中，节点间的链接长度是一定的，根据RSA优化思想，每个节点产生的涟漪都会同时进行扩散，它们总是先到达最近的节点，即使有些链接被限制，但路径搜索原理仍然一致。节点位置、链接长度和扩散速度是一定的，首先遍历所有节点回到起点的涟漪所经过的路径必定是经过TSP的最短路径，定理1得证。

定理2：RSA会对解空间进行优化。

证明:RSA在寻优过程中，不同的涟漪进行扩散会计算出不同长度的TSP路径，但总会优先输出最优的路径，如定理1所证，当该路径输出后，算法继续计算可能路径的子问题，若子问题的路径长度计算值达到最优解长度，但仍未生成完整的TSP路径，将停止对于该子问题的计算，即只计算是否存在由于最优解长度的解，从而缩小搜索的解空间。RSA寻优过程如图11所示，以该网格点的3条TSP路径为例，在计算图11a路径网格的TSP路径时，会优先输出图11b中的1号路径，并记录路径长度，从而在计算第2、3号路径时，由于路径长度大于1号路径，则不会计算完整的TSP路径，从而缩小搜索的计算量，定理2得证。同时在与穷举算法对比时，该定理也为RSA算法的计算更优性提供了保证。

定理3：RSA的计算复杂度为O(n_I×n_e×n_T)，其中，n_atu为涟漪通过路网中链接的平均时间。

证明:在RSA中，涟漪通过在链接上进行扩散，并通过对比涟漪和链接的长度，来决定是否产生新的涟漪。假设网格G拥有n_I个节点，每个节点平均有n_e条链接相连，每个涟漪平均花费n_atu个模拟时间通过一条边，其中起点最多可以产生n_e个涟漪。终点与起点为同一点，并且不会再次产生涟漪，其他每个节点产生涟漪的数量不会超过n_e。那么基于RSA的路径寻优过程会执行n_e×n_T+(n_I-1)×n_e×n_T次计算，其计算复杂度为O(n_I×n_e×n_T)。

4 算法测试分析

收起

4.1 大规模随机对比试验

假设每组平均拥有N个节点，其中每2个节点相连。选取穷举算法和遗传算法进行对比试验。3种算法在相同的网络中运行，综合对比得到的TSP路径长度、运算效率，并提出以下对比条件^[14]。

1) 完全随机网络。定义网格的节点数量和结构信息，依据网格生成理论，随机生成固定数量的节点，供2种算法进行试验。

2) 网格状网络。该矩形网络拥有行和列，每个节点只与其周围的节点相连，路径长度定义为实际的空间距离。

3) 规定限制链接。试验在安全约束下进行，将限制风险链接，在3种算法中均给出限制链接，并在算法试验规定限制链接禁止通行。在测试中使用节点总数N={5，10，11，12，13，14，15，16，17，18，19，20}。

穷举法是一种精确算法，其会枚举所有解空间从而找到最优解，但其计算复杂度和空间复杂度较高，不适用于大规模的TSP问题。遗传算法是一种群体性算法，具有一定的自组织、自适应和自学习性，可以同时处理多群体中的多个个体，但对于好的初解具有一定依赖性。实际应用中，种群大小和迭代次数的选择对算法性能和解决问题的质量有很大影响，因此，需要在效率和解的质量之间权衡，选取2种参数的遗传算法进行对比，2组参数分别设定为：第1组:初始化种群数目N=200，染色体基因维数为L=31，最大进化代数G=1 000;第2组:初始化种群数目N=400，染色体基因维数为L=31，最大进化代数G=2 000。具体的对比组数设置见表2。

对比试验结果见表3。并增加了15和20个节点的以RSA解为初值的遗传算法试验，且没有优化计算所得的路径长度，仍为7 883.196 6和8 435.145 6m，和RSA算法的结果一致。

4.2 测试结果分析

1) 在所有试验中，随着节点数量增加，迭代次数的规模增大，穷举法计算量会呈指数级增长，在12个节点时由于计算量的巨幅增加，导致穷举法无法在12h内输出运算结果，因此，穷举法只适用于小规模的TSP问题。遗传算法则随着节点数量的增多，输出的最短路径开始变得不稳定，不能保证求解理论最优解，算法在多次试验中只能在一定的误差范围内找到尽可能好的解，算法后期迭代收敛性较差，可能是迭代到一定程度种群多样性较低。

2) 就求解最优路径而言，穷举法和RSA都能够求解出相同的最优TSP路径，且RSA能够进行较大规模TSP问题的计算。而遗传算法则不能保证结果最优性，在小规模试验时可以求解出与其他2种算法相同的最优路径，但随着问题规模的增大，试验结果不能保持稳定。

3) 在以RSA结果为初值的遗传算法求解过程中，基础数据不变的情况下，遗传算法求解的最优路径长度没有发生改变，并且在小规模的问题中穷举法能保证求解理论最优解，这2种试验结果皆证明了RSA解的最优性。

4) 就平均计算时间(Computational Time，CT)而言，问题规模对所有3种方法都会产生影响，都会引起CT增加。穷举法受问题规模影响最大，RSA相较于遗传算法受节点影响较大，但在小规模计算中仍能保持优于遗传算法的计算速度，遗传方法的CT虽随问题规模变化较慢，但结果也逐渐不稳定。

5) 在限制链接的情况下，会更加限制遗传算法和穷举法的计算速度，而对RSA的影响很小，这与3种算法的基本求解逻辑有很大关系。

6) 通过试验对比也可以得出结论，RSA更适用于无人机续航约束、安全条件约束下的中小规模无人机巡检路径规划问题，该算法能够保证无人机巡检的最优路径规划，同时由于无人机续航条件的约束，一般的巡检问题规模(大多在6~13台)应在RSA的最速计算范围内，并且RSA的算法原则，也更有利于设定实时备降安全的链接限制约束。

4.3 仿真试验

以天津某风电场为测试算例，风电场高程数据来自航天飞机雷达地形测绘数据，高程数据栅格精度为20m。数据地理空间范围为E117.2 ~ E117.5，N39.3 ~ N39.6，高度为海拔0~ 100m。测试当日8:00—11：00时段内风向为22.5°，风速为8m/s，11：00—15：00时段内风向为25°，风速为9m/s，依据风廓线公式计算80m高处的最高风速分别为10.7和12m/s。选取抗风能力为7级、有效航程为90~100km的大型油电无人机作为测试无人机，根据风向风速的模拟值，可算出无人机续航里程R=76 km，航迹路线里程范围最大约束为7.6km。依据航程约束，将风机按照所处位置分成2组，分时段进行巡检规划，并设置安全返航距离为300m。该风电场采用风轮直径80m，78m高的塔架V90(3MW)机组，共有22台风电机，14个备降点。第1组10台风机、6个备降点、8:00—11：00时段内巡检;第2组12台风机、8个备降点、11：00—15：00时段内巡检。

通过栅格化风机、备降点位置及高程信息的风电场高程数据完成风电场整体数学模型的建立^[15]，由于备降区域在实际选取过程中，应具体到单位m来规定范围，故在本试验的模型建立过程中，通过GIS转换工具，依据风机和备降中心点的坐标将其度分秒经纬度转换为具体的以米为单位的xy平面如图12所示。其中，H表示风电场中设置的备降点，在本试验中根据地理信息系统数据，对备降区域进行了具体的形状规定，图中黑色圆点表示风电场中无人机巡检不同风电机时的所在位置，黑色连线为依据路径安全性判断计算出的风险路径。

对文中改进的RSA在Matlab软件中编程，基于试验设定的参数进行求解。算法在主频为2.60 GHz的Intel Core i7-10750H中央处理器、Windows 10操作系统的环境下运行，通过运行本文设计的算法求解基于所建立模型的风电场在安全约束下路径规划问题，巡检方案如图13、图14所示(第2组数据穷举法无法计算路径)。

试验结果表明：安全约束条件对风险路径具有安全性限制，在路径的计算过程中可避免选择风险路径作为巡检路径，从而满足实时备降的安全约束条件。改进后的RSA能够在满足实时备降约束的条件下，短时间内求得无人机风电场巡检的最优路径，并计算路径长度以满足无人机续航的需求。在与穷举法和遗传算法的对比求解过程中可以看出，风机节点的增多会大大增加穷举算法的计算量，影响遗传算法的稳定性，致使2种算法无法稳定地计算出最优路径，而RSA能在较短的求解时间内稳定求得最优路径。因此，文中提出的RSA对于无人机巡检路径规划问题的计算效率和结果质量提升方面是有效的。

5 结论

收起

1) 从无人机巡检的安全风险、飞行特性和操作原则等角度总结出的实时备降安全性计算原理，有助于评估无人机巡检过程中备降安全性，综合不同的风险因素计算出安全路线。

2) 针对安全约束下的TSP问题，结合涟漪扩散算法多智体同时扩散的算法特性，能够实现对TSP问题的有效求解，能够避免在求解过程中陷入局部最优，同时，降低运算的冗余度，有利于准确、高效的规划实时备降安全约束下无人机风电场巡检的最优路径。

3) 文中研究重点在于飞行路径规划和飞行过程中的安全考量，而在风机的具体巡检流程方面，仅作了初步探讨，未来需要深入研究。

基金

收起

国家自然科学基金青年科学基金资助(62201577)
天津市自然科学基金资助(23JCQNJC00230)
天津市自然科学基金资助(23JCQNJC00080)
中央高校基本科研业务费(3122019057)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

刘智勇, 赵晓丹, 祁宏昌, 等. 新时代无人机电力巡检技术展望[J]. 南方能源建设, 2019, 6(4): 1-5.

LIU

Zhiyong

, ZHAO

Xiaodan

, QI

Hongchang

, et al. Prospect of UAV power inspection technology in new era[J]. Southern Energy Construction, 2019, 6(4): 1-5.

[2]

高珩, 鲍鹏. 旅行商问题求解算法综述[J]. 软件导刊, 2009, 8(11): 67-68.

[3]

DENG

Yanlan

, XIONG

Juxia

, WANG

Qiuhong

. A hybrid cellular genetic algorithm for the traveling salesman problem[J]. Mathematical Problems in Engineering, 2021, 2021(2):DOI:10.1155/2021/6697598.

[4]

EZUGWU

E A

, ADEWUMI

O A

, FRINCU

E M

. Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem[J]. Expert Systems With Applications, 2017, 77: 189-210.

[5]

余丽, 陆锋, 杨林. 交通网络旅行商路径优化的遗传禁忌搜索算法[J]. 测绘学报, 2014, 43(11): 1197-1203.

, LU

Feng

, YANG

Lin

. A hybrid algorithm for traveling salesman problem in road network[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(11): 1197-1203.

[6]

陈科胜, 鲜思东, 郭鹏. 求解旅行商问题的自适应升温模拟退火算法[J]. 控制理论与应用, 2021, 38(2): 245-254.

CHEN

Kesheng

, XIAN

Sidong

, GUO

Peng

. Adaptive temperature rising simulated annealing algorithm fortraveling salesman problem[J]. Control Theory and Applications, 2021, 38(2): 245-254.

[7]

刘海龙, 雷斌, 王菀莹, 等. 求解TSP问题的改进融合遗传灰狼优化算法[J]. 计算机仿真, 2023, 40(9): 333-338.

LIU

Hailong

, LEI

Bin

, WANG

Wanying

, et al. Improved fused genetic grey wolf optimization algorithm for solving TSP[J]. Computer Simulation, 2023, 40(9): 333-338.

[8]

张树卓. 计及风场的输电线路无人机巡检路径规划研究[D]. 济南: 山东大学, 2021.

ZHANG

Shuzhuo

. Research on UAV path planning of transmission line inspection considering wind field[D]. Jinan: Shandong University, 2021.

[9]

韩鹏, 张冰玉. 基于改进蚁群算法的无人机安全航路规划研究[J]. 中国安全科学学报, 2021, 31(1): 24-29.

HAN

Peng

, ZHANG

Bingyu

. Safety route planing of UAV based on improved ant colony algorithm[J]. China Safety Science Journal. 2021. 31(1):24-29.

[10]

王猛, 王道波, 王博航, 等. 基于改进NSGA-II的多无人机三维空间协同航迹规划研究[J]. 机械与电子, 2021, 39(11): 73-80.

WANG

Meng

, WANG

Daobo

, WANG

Bohang

, et al. Three-dimensional multi -UAV cooperative path planning based on an improved NSGA-II algorithm[J]. Machinery & Electronics, 2021, 39(11): 73-80.

[11]

韩鹏, 赵嶷飞. 基于飞行环境建模的UAV地面撞击风险研究[J]. 中国安全科学学报, 2020, 30(1): 142-147.

HAN

Peng

, ZHAO

Yifei

. Study on ground impact risk of UAV based on flight environment[J]. China Safety Science Journal, 2020, 30(1): 142-147.

[12]

曾薇, 孟祥旭, 杨承磊, 等. 平面多边形域的快速约束Delaunay三角化[J]. 计算机辅助设计与图形学学报, 2005, 17(9): 1933-1940.

ZENG

Wei

, MENG

Xiangxu

, YANG

Chenglei

, et al. Fast constrained delaunay triangulation for planar polygonal domains[J]. Journal of Computer-Aided Design & Computer Graphics, 2005, 17(9): 1933-1940.

[13]

Xiaobing

, WANG

Ming

, LEESON

M S

, et al. Deterministic agent-based path optimization by mimicking the spreading of ripples[J]. Evolutionary Computation, 2016, 24(2): 319-46.

[14]

胡小兵, 袁莉燕, 李航, 等. 基于涟漪扩散算法的应急疏散路径优化方法研究[J]. 交通运输系统工程与信息, 2024, 24(1): 253-261.

Xiaobing

, YUAN

Liyan

, LI

Hang

, et al. Optimization of emergency evacuation route based on ripple-spreading algorithm[J]. Journal of Transportation Systems Engineering and Information, 2024, 24(1): 253-261.

[15]

王永峰, 徐莹, 王涛. 基于数字高程模型制作山区坡度分级栅格数据[J]. 测绘与空间地理信息, 2014, 37(12): 36-38.

WANG

Yongfeng

, XU

Ying

, WANG

Tao

. Mapping slope graded map of mountainous area based on digital elevation model[J]. Geomatics & Spatial Information Technology, 2014, 37(12): 36-38.

2025年第35卷第2期

PDF下载

509

224

引用本文

BibTeX

文章信息

doi: 10.16265/j.cnki.issn1003-3033.2025.02.0865

接收时间：2024-09-10
首发时间：2025-07-05
出版时间：2025-02-28

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-09-10
修回日期：2024-11-12

基金

国家自然科学基金青年科学基金资助(62201577)

天津市自然科学基金资助(23JCQNJC00230)

天津市自然科学基金资助(23JCQNJC00080)

中央高校基本科研业务费(3122019057)

作者信息

¹ 中国民航大学安全科学与工程学院，天津 300300

² 中国民航大学中欧航空工程师学院，天津 300300

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/zgaqkxxb/CN/10.16265/j.cnki.issn1003-3033.2025.02.0865

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT

变量符号	含义
G	G={n₁，n₂，…，n_n}网格节点坐标集合
n_k	TSP问题的起始和终止节点
S(n_i，n_j)	表示n_i和n_j节点间的路径为风险路径
c_ij	表示n_i和n_j节点间路径的距离
F	节点间的路径距离集合
v	涟漪的传播速度
D_max	涟漪的最大传播范围，等于最大节点间距离
Ω_A	处于激活状态涟漪的集合
Ω_S	处于等待状态涟漪的集合
E	E={e₁_j，e₂_j，…，e_ij}为链接集合
R_n	产生的第n个涟漪，按时间先后顺序产生

变量符号

含义

G={n₁，n₂，…，n_n}网格节点坐标集合

n_k

TSP问题的起始和终止节点

S(n_i，n_j)

表示n_i和n_j节点间的路径为风险路径

c_ij

表示n_i和n_j节点间路径的距离

节点间的路径距离集合

涟漪的传播速度

D_max

涟漪的最大传播范围，等于最大节点间距离

Ω_A

处于激活状态涟漪的集合

Ω_S

处于等待状态涟漪的集合

E={e₁_j，e₂_j，…，e_ij}为链接集合

R_n

产生的第n个涟漪，按时间先后顺序产生

节点数量/个	限制链接
5	1—5，2—4
10、11、12	1—5，6—7，3—8
13、14、15	2—3，4—6，1—9
16、17、18、19、20	3—5、4—7、1—6、2—8

节点数量/个

限制链接

1—5，2—4

10、11、12

1—5，6—7，3—8

13、14、15

2—3，4—6，1—9

16、17、18、19、20

3—5、4—7、1—6、2—8

节点数量	对比参数	穷举算法	RSA算法	遗传算法 (第1组)	遗传算法 (第2组)
5	路径长度/m	4 920.455 7	4 920.455 7	4 920.455 7	4 920.455 7
平均计算时间/s	0.003 6	0.062 5	0.204 6	0.204 6
10	路径长度/m	6 302.533 4	6 302.533 4	6 302.533 4	6 302.533 4
平均计算时间/s	1.703 1	0.328 1	0.343 7	1.451 6
11	路径长度/m	6 312.800 3	6 312.800 3	6 312.800 3	6 312.800 3
平均计算时间/s	18.904 0	0.3714	0.380 6	1.677 1
12	路径长度/m	—	6 518.413 2	6 995.178	6 518.413 2
平均计算时间/s	>12 h→43 200	0.609 4	0.437 5	1.698 9
13	路径长度/m	—	7 102.741 8	7255.3917	7179.808 6
平均计算时间/s	>12 h→43 200	0.640 6	0.454 7	1.821 5
14	路径长度/m	—	7 551.191 3	7703.8413	8212.586 8
平均计算时间/s	>12 h→43 200	2.625 0	0.447 3	2.162 9
15	路径长度/m	—	7 883.196 6	8 111.321 7	7 969.666 8
平均计算时间/s	>12 h→43 200	3.875 0	0.450 6	1.885 3
16	路径长度/m	—	8 224.882 9	8 290.993 4	8 290.993 4
平均计算时间/s	>12 h→43 200	12.578 1	0.504 2	2.106 1
17	路径长度/m	—	8 295.178 0	8 582.807 7	9 186.072 6
平均计算时间/s	>12 h→43 200	43.328 1	0.486 5	2.096 5
18	路径长度/m	—	8 347.271 1	8 654.3731	8 347.271 1
平均计算时间/s	>12 h→43 200	89.187 5	0.580 9	2.219 3
19	路径长度/m	—	8 424.510 6	9 725.751 1	9947.725 4
平均计算时间/s	>12 h→43 200	311.03 13	0.600 2	2.249 7
20	路径长度/m	—	8 435.145 6	8 727.888 6	8 497.369 1
平均计算时间/s	>12 h→43 200	469.062 5	0.592 3	2.382 3

节点数量

对比参数

穷举算法

RSA算法

遗传算法
(第1组)

遗传算法
(第2组)

路径长度/m

4 920.455 7

平均计算时间/s

0.003 6

0.062 5

0.204 6

路径长度/m

6 302.533 4

平均计算时间/s

1.703 1

0.328 1

0.343 7

1.451 6

路径长度/m

6 312.800 3

平均计算时间/s

18.904 0

0.3714

0.380 6

1.677 1

路径长度/m

—

6 518.413 2

6 995.178

6 518.413 2

平均计算时间/s

>12 h→43 200

0.609 4

0.437 5

1.698 9

路径长度/m

—

7 102.741 8

7255.3917

7179.808 6

平均计算时间/s

>12 h→43 200

0.640 6

0.454 7

1.821 5

路径长度/m

—

7 551.191 3

7703.8413

8212.586 8

平均计算时间/s

>12 h→43 200

2.625 0

0.447 3

2.162 9

路径长度/m

—

7 883.196 6

8 111.321 7

7 969.666 8

平均计算时间/s

>12 h→43 200

3.875 0

0.450 6

1.885 3

路径长度/m

—

8 224.882 9

8 290.993 4

平均计算时间/s

>12 h→43 200

12.578 1

0.504 2

2.106 1

路径长度/m

—

8 295.178 0

8 582.807 7

9 186.072 6

平均计算时间/s

>12 h→43 200

43.328 1

0.486 5

2.096 5

路径长度/m

—

8 347.271 1

8 654.3731

8 347.271 1

平均计算时间/s

>12 h→43 200

89.187 5

0.580 9

2.219 3

路径长度/m

—

8 424.510 6

9 725.751 1

9947.725 4

平均计算时间/s

>12 h→43 200

311.03 13

0.600 2

2.249 7

路径长度/m

—

8 435.145 6

8 727.888 6

8 497.369 1

平均计算时间/s

>12 h→43 200

469.062 5

0.592 3

2.382 3