基于改进Fleury算法的无人机巡线路径规划
束庆霏，蔡佳澄，王思凡，肖美岑，何杨阳，陈宇晨
（国网江苏省电力有限公司张家港供电公司，江苏 张家港 215600）
近年来，在国家数字新基建、能源互联网等战略需求驱动下，无人机业务迎来跨越式的发展。其中，无人机智能巡线是重点项目。张家港市电网目前共有输电线路1 711 km，配电线路6 473 km，全社会用电量、工业电量均名列全省乃至全国前茅。面对如此庞大的体量，无人机自主巡线的必要性得到了大大提高［1-4］。无人机巡线的关键技术有很多，如：超低空飞行、超视距巡检、自主避障、路径规划、远程自主精准降落技术、抗电磁干扰能力、数据安全策略等［5-9］。本文主要研究无人机巡线路径规划问题。
当前国内外学者多用启发式算法进行路径规划。启发式算法是一种基于直观或经验的局部优化算法ADDIN，由大自然的运行规律或者从具体问题的经验和规则中总结而出。在无人机路径规划中，启发式算法通过计算当前位置到目标点的代价值来进行路径选择，当总代价全局最小时，可认为当前路径为全局最优路径。常用的启发式算法有模拟退火算法、虚拟力法、A*算法、势场法、遗传算法等。李游等［10］综合利用最短距离算法，动态规划算法和A*算法，提出了一种智能航线算法模型，可实现变电站复杂条件下的航线规划。Linhui Cheng［11］等建立了多基地、可充电续航多无人机道路巡逻任务分配模型，提出了一种time-priority immune clonal selection 算法，得到最优任务点序列，并采用时间优先法对任务点序列进行划分。实验结果表明，与粒子群优化算法和改进的动态规划蚁群算法相比，该算法得到的巡线时间大大减少。崔敬魁［12］利用遗传算法和蚁群算法寻得符合条件的最优巡线路径。李成雷等［13］基于RRT-connect（快速搜索随机树）算法设计了无人机飞行最优路径，经验证，路径长度接近理论最优值。
除了启发式路径规划，也有其他方法用于无人机的路径规划。赵甜甜等［14］利用百度导航设计了自动巡航机器人。施孟佶等［15］研究了双无人机协同巡检方案。韦立富等［16］基于三维激光点云数据，构建模型，生成航线，并评估高危区，设置禁飞区，最终生成可自动往返的飞行路线。Hu等［17］采用北斗导航系统为无人机巡线提供路径规划。曾懿辉等［18］首先通过人工巡检，记录关键轨迹的经纬坐标和无人机飞行俯仰角，当自主巡线时，便可以遵照预定的轨迹和飞行俯仰角进行航拍。陈洪亮等［19］采用基于关键坐标点的路径规划算法对配电网线路进行规划，确保了无人机巡线的高效性和安全性。
上述研究工作大多因地制宜，研究了当地电网的无人机巡线路径规划，很多并没有结合实际的线路坐标。本文基于张家港市电网典型线路的杆塔经纬坐标，根据图论知识，结合中国邮递员问题的研究方法，采用改进的Fleury 算法进行路径规划。
本文基于图论和中国邮递员问题的研究方法，对张家港市电网的典型输配电线路进行无人机巡线路径规划。
1.1 数据处理
由于杆塔坐标具有保密性，本文征求到8条典型线路的杆塔坐标用于研究。数据为Excel 形式，包含了杆塔名称、杆塔经纬坐标等信息，可利用python 语言的pandas 库读取Excel，并通过编程得到线路的平面分布图和线路长度。
杆塔线路分为主线和支线，某些支线又会分出新的支线，所以不能按顺序将所有的点连接组成线路。本文采用矩阵理论，设gps是初始值为n×n的零矩阵，n为此线路的杆塔数量。两次遍历所有杆塔，若杆塔i、j间存在线路，则记gps（i，j）=1。张家港市输配电线路的杆塔数量大多在100～200，计算量不是很庞大，大概几秒就能遍历结束。
识别杆塔间是否存在线路的方法如下：太字甲线35-1-14-1-3 号是杆塔编号样例，其中，太字甲线为线路名称，“35”为主线第35 号杆塔，“1-14”为由主线35号杆塔分支出来的第一条支线的第14 号杆塔，“1-3”为由支线14 号杆塔分支出来的第一条支线的3号杆塔。相邻编号的杆塔在地理位置上也是相邻的，支线的编号包含了分支节点编号，因此可通过正则表达式识别出是否存在线路的相邻杆塔。
同样，设置n×n的初始零矩阵D，遍历两次杆塔坐标，记D（i，j）=Ds，Ds为两杆塔之间的距离。已知两点的经纬坐标，求两点之间的距离，计算方法如下。
假设地球是一个完美的球体，半径为6 371.004 km，记为R。若以0°经线为基准，两点的经纬坐标分别为（X1，Y1）和（X2，Y2），则可通过地球表面任意两点的经纬度计算出两点的地表距离Ds（忽略前地球表面地形带来的误差）。张家港市地处北纬31°43′12″—32°02′，东经120°21′57″—120°52′，可用式（1）、式（2）计算。
式中：π为圆周率。
1.2 模型建立
1.2.1 建模目标
本文的模型旨在建立一套算法流程，工作人员从PMS3.0系统导出杆塔坐标信息，放入模型后自动运行，最后导出近似最优的巡线路径。算法只能得到近似最优路径，因为实际最优路径需遍历所有情况，计算机算力达不到。而得到近似最优耗时较短，适用于所有的简单线路和复杂线路，具有较好的应用价值。
1.2.2 算法理论
无人机巡线需遍历一条线路的主线和所有支线，属于行遍性问题。典型的行遍性问题有中国邮递员问题：邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，希望选择一条行程最短的路线。解决行遍性问题，需参考图论里的欧拉图和Fleury算法。
欧拉图：G是一个由点集和边集构成的无向图，经过G的每条边的迹叫做G的Euler迹；
闭的Euler 迹叫做Euler 回路；
含Euler 回路的图叫做Euler图。直观地讲，Euler图就是从一顶点出发每边恰好通过一次最后回到出发点的图，即不重复地行遍所有的边再回到出发点。
根据Fleury算法可得：
1）∀v0∈V(G)，令W0=v0。
2）假设迹Wi=v0e1v1…eivi已经选定，则按下述方法从E-{e1，…，ei}中选取边ei+1。
ei+1和vi相关联。
除非没有别的边可选择，否则ei+1不是Gi=G-{e1，…，ei}的割边。所谓割边是一条删除后使连通图不再连通的边。
3）当第2步不能再执行时，算法停止。
本文研究的无人机巡线问题与中国邮递员问题相近，但有以下不同点：邮递员需回到起点，而无人机可以使用移动车载平台，将车载平台直接停在巡线路径终点；
邮递员的投递路径具有约束性，必须是两个城镇之间存在道路才能同行，无人机可在任意两个杆塔之间飞行。因此，本文对Fleury 算法进行改进，添加随机选择的元素，并采用python 编程，得到近似最优的无人机巡线路径。
1.2.3 模型假设
1）一架无人机每次只巡一条线路，不考虑多条线路一起巡视的情况。
2）无人机续航里程大于整个巡线里程。张家港市大多数线路的长度小于15 km，满足无人机的续航里程（见表1），个别线路较长（最长达20.10 km），可采用移动机载平台，充电后再继续巡航，或采用人工巡线和无人机巡线结合的方式。
3）整个飞行过程畅通无阻，不考虑线路通道周围的阻碍和两杆塔直线空间内的阻碍。张家港市全境地势平坦，无山岭阻碍无人机飞行，线路通道的障碍主要有树木障碍、交叉线路、路灯障碍等，无人机的感知系统可实现自主避障。
4）飞行环境是无风环境，无人机匀速飞行。
5）无人机感知系统（见表1）正常，可始终保持跟踪导线飞行。
6）无人机定位系统（见表1）正常，可准确定位目标杆塔。
张家港在役无人机的部分参数见表1，部分缺失数据厂家未提供。
表1 张家港在役无人机参数Table 1 Parameters of in-service UAV in Zhangjiagang
1.2.4 算法流程
1）根据杆塔经纬坐标得到线路分布的平面二维图。
2）设置n×n的初始零矩阵gps，遍历所有杆塔，若两杆塔i、j之间存在线路，则标记gps（i，j）=1。
3）设置n×n的初始零矩阵D，遍历所有杆塔，计算两杆塔i、j之间的地表距离Ds，令D（i，j）=Ds。
4）遍历所有杆塔得到线路的起点和终点。
5）设置空白路径route，线路的起点（或终点）作为路径起点，并设置当前杆塔位置state，state初始值为路径起点，以state 为基准，遍历所有的杆塔。
若遍历到杆塔i与杆塔state之间存在线路，即gps（state，i）=1，则将杆塔i加入路径route，对于存在支线的线路节点，设置随机选择，并将选择支线的概率设置大一点，选择支线的概率是选择主线概率的2～3 倍，因为对于大部分线路，优先巡完支线再回到主线继续巡线是一个比较好的选择。同时将gps（state，i）和gps（i，state）更新为0，将当前杆塔位置state更新为i。
若遍历完所有杆塔，不存在与杆塔state 相连的杆塔，则搜寻state 附近的杆塔，该杆塔需满足条件：有其他杆塔与之相连。搜寻1～3 个与杆塔state 距离最近的杆塔，并随机选择其中一个杆塔i，加入路径route，同时将gps（state，i）和gps（i，state）更新为0，将当前杆塔位置state更新为i。
6）重复步骤5 的运算，直至gps的所有元素和为0，即无人机巡完所有线路。
7）计算路径的里程。
8）重复步骤5、6、7，迭代更新无人机巡线里程最短的路径，将其作为近似最优巡线路径，并导出每一步路径规划。
本节选取张家港市电网8条典型线路进行路径规划研究。其中简单线路3条，复杂线路5条。
2.1 简单线路分析
简单线路图的特点是支路较少，支线较短，能够明显看出主线位置，杆塔数量一般不超过100，见表2。
表2 简单线路Table 2 Simple lines
对于大德线，如图1所示，在支线端点随机选择时，直接选择最近的杆塔，运行结果较为理想，近似最优路径里程为4.179 km，比实际线路长度3.814 km 多出9.5%。从路径规划来看，大多是从主线分支节点先巡支线，再回到主线。也有从支线直接飞往另一支线，再回到主线，如：大德线51-1-0-1-1 号→大德线53-1-1 号→大德线53号。
图1 大德线线路示意图Fig.1 Diagram of Dade line
对于攀华线（见图2），在支线端点随机选择时，直接选择最近的杆塔，运行结果较为理想，近似最优路径里程为6.497 km，比实际线路长度4.944 km 多出31.4%。从路径规划来看，从主线分支节点先巡支线，再回到主线。攀华线有一条较长的支线，若将线路的终端（右上角）作为巡线起点，近似最优路径里程为6.538 km，比实际线路长度多出32.2%。主线巡线顺序不连续，巡完较长的支线后，无人机飞至线路首端继续巡线，如：攀华线6-1-7号→攀华线1号。巡完主线，再飞往与之不相邻的支线，如：攀华线6号→攀华线21-1-21-1-1 号。尽管两种巡线路径差异很大，但是巡线里程差不多，一般将线路首端作为巡线起点即可。
图2 攀华线线路示意图Fig.2 Diagram of Panhua line
对于永旺线（见图3），在支线端点随机选择时，直接选择最近的杆塔，运行结果较为理想，近似最优路径里程为2.68 km，比实际线路长度2.215 km 多出20.9%。从路径规划来看，大多是从主线分支节点先巡支线，再回到主线。永旺线近似一个闭环，可巡完所有主线再巡首端的支线，如：永旺线31号→永旺线2号→永旺线2-1-1号。
图3 永旺线线路示意图Fig.3 Diagram of Yongwang line
综上，对于简单线路的路径选择，在支线端点随机选择时，直接选择最近的杆塔运行结果较为理想，路径大多沿着按主线顺序巡线，产生分歧主要在于不同的支线巡线方法。有时从某一支线端直接飞往另一支线，路径较优；
大多数情况是从支线端直接飞回主线继续巡线，路径较优。简单线路的杆塔数量、实际长度、计算长度及其误差见表2。
2.2 复杂线路分析
复杂线路的特点是支线较多，支线长短不一，有的无法明显识别出主线位置，如万新线、太字甲线；
有的支线过长，如跃进线、万江甲线、王巷甲线。复杂线路的杆塔数量一般超过100，有的（如太字甲线）高达200多，见表3。
表3 复杂线路Table 3 Complex lines
对于万新线（见图4），在支线端点随机选择时，直接选择最近的杆塔，运行结果较为理想，近似最优路径里程为7.45 km，比实际线路长度5.731 km 多29.9%。由于万新线支线部分较为复杂，近似成H 状，支线和主线里程差不多，所以路径选择时，可能会跳过某一段主线，主线的巡线顺序不连续，如：万新线9-1-15号→万新线26号，万新线41号→万新线37号。
图4 万新线线路示意图Fig.4 Diagram of Wanxin line
对于跃进线（见图5），在支线端点随机选择时，直接选择最近的杆塔，运行结果较为理想，近似最优路径里程为10.083 km，比实际线路长度7.469 km 多34.9%。从路径选择来看，主线的巡线顺序基本连续，无人机巡完2条较长的支线再回到主线。近似最优的路径也有一定概率存在重复巡线现象，如：跃进线4号→跃进线3号→跃进线4号→跃进线5号，由于地理位置限制，这是不可避免的。
图5 跃进线线路示意图Fig.5 Diagram of Yuejin line
对于万江甲线（见图6），在支线端点随机选择时，直接选择最近的杆塔，运行结果较为理想，近似最优路径里程为8.632 km，比实际线路长度6.851 km 多25.9%。万江甲线存在3 条较长的支线，巡线过程中，无人机直接从支线的一端飞往另一条支线，如：万江甲线49-1-9-1-1号→万江甲线70-1-12-1-1 号，无人机巡完2 条支线后再继续巡主线。因此，主线巡线顺序也是不连续的。
图6 万江甲线线路示意图Fig.6 Diagram of Wanjiang A-line
对于王巷甲线（见图7），在支线端点随机选择时，直接选择最近的杆塔，运行结果较为理想，近似最优路径里程为18.613 km，比实际线路长度14.883 km 多25%。王巷甲线线路分布非常不规则，无人机巡线不完全按照主线顺序飞行，有时会从某一支线端部直接飞往另一支线，如：王巷甲线64-1-2-1-7 号→王巷甲线56-1-5 号；
甚至从主线直接飞往与之不相连的支线，如：王巷甲线71 号→王巷甲线64-1-4 号，王巷甲线84 号→王巷甲线78-1-2 号。主线巡线顺序也不连续，如：王巷甲线64号→王巷甲线67号。
图7 王巷甲线线路示意图Fig.7 Diagram of Wangxiang A-line
对于太字甲线（见图8），在支线端点随机选择时，直接选择最近的杆塔，运行结果较为理想，近似最优路径里程为17.545 km，比实际线路长度13.367 km 多31.2%。太字甲线线路分布也非常复杂，无人机飞行规律与王巷甲线类似，可能从某一支线端直接飞往另一支线端，如：太字甲线54-2-1 号→太字甲线35-2-1 号；
可能从主线飞往与之不相连的支线，如：太字甲线24 号→太字甲线35-1-14-1-3 号；
可能从支线飞往与之不相连的主线，如：太字甲线66-1-5号→太字甲线70号。
图8 太字甲线线路示意图Fig.8 Diagram of Taizi A-line
综上，复杂线路的路径选择中，在支线端点随机选择时，直接选择最近的杆塔，运行结果较为理想。复杂线路杆塔数量更多，节点也更多，需经过更多次的迭代，程序运行时间更长。复杂线路的路径规划没有明显规律，一切随机应变，程序的运行结果已是较好的选择。复杂线路的杆塔数量、实际长度、计算长度及其误差见表3。
2.3 算法评价
以往的研究大多将无人机巡线路径规划当作旅行商问题，即无人机遍历每个目标点的最短路径［11-12，20-22］，并未考虑到目标点之间是否存在线路。因此，可遍历所有的杆塔，但不能完全覆盖杆塔之间的线路。
本文基于中国邮递员问题的研究方法，即无人机遍历每个目标点和相应目标点间线路的最短路径。根据本文模型，无人机可近似最优地巡视完所有的杆塔和线路。由于线路分布并非欧拉图，多余巡线不可避免，本方法的误差为10%～30%，已较为理想。
本文针对张家港市电网的典型线路进行了无人机巡线路径规划。基于图论知识，结合中国邮递员问题的研究方法，采用改进的Fleury 算法，添加随机元素（主线分支节点随机，支线端点随机），得到近似最优的无人机巡线路径。根据程序运行结果得出以下结论。
1）本文的算法程序在导入由PMS3.0系统获取的杆塔坐标信息后，可很快得到近似最优路径，简单便捷，实用性强，容错率高，适用于所有的简单线路和复杂线路。经验证，程序运行出的巡线里程一般比实际里程多出10%～30%，效果较为理想。
2）对于简单线路，支线较少且长度较短，巡线路径一般按照主线杆塔顺序，遇到主线分支节点，一般先巡完支线再回到主线继续巡线，偶尔会从某一支线飞往另一支线。
3）对于复杂线路，支线较多且长短不一，巡线不完全按照主线杆塔顺序，可能出现以下状况：从支线端直接飞往另一支线端，从主线飞往不相邻的支线，从支线飞往不相邻的主线。
若线路过长，则需要两台甚至更多的无人机来完整地巡完一条线路，本文的程序无法自动分割线路供多个无人机巡线。对此，可参照多邮递员问题：邮局有k（k≥2）位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的时间最早，这将是下一步研究工作的重点。
猜你喜欢巡线支线主线支线飞机替换战略的经济性分析民用飞机设计与研究(2020年4期)2021-01-21小型无人机在电网运检维护工作中的应用设备管理与维修(2020年2期)2020-03-24出没风波里，踏浪去巡线广西电业(2020年11期)2020-03-23人物报道的多维思考、主线聚焦与故事呈现活力(2019年17期)2019-11-26更加突出主线 落实四个到位 推动主题教育取得实实在在成效当代陕西(2019年15期)2019-09-02无人机在电力巡线中的应用模式研究无人机(2018年1期)2018-07-05数字主线中国计算机报(2017年44期)2017-12-11支线机场建设项目经济效益评价中国工程咨询(2017年11期)2017-01-31高压巡线四旋翼机器人反步自适应控制的研究电测与仪表(2016年16期)2016-04-12下沉和整合 辽宁医改主线中国卫生(2014年9期)2014-11-12