基于枚举法的变电站巡检机器人巡视路线优化

2021-02-24 06:25张永涛于倩倩肖智彬孙秋芹徐雯俐
浙江电力 2021年1期
关键词:路线聚类变电站

张永涛,于倩倩,肖智彬,孙秋芹,张 轲,徐雯俐

(1.国网河南省电力公司周口供电公司,河南 周口 466000;2.国网湖南省电力有限公司检修公司,长沙 410004;3.湖南大学 电气与信息工程学院,长沙 410082;4.国网山西省电力公司晋城供电公司,山西 晋城 048000)

0 引言

变电站设备分布较广,且数量众多,在高温、大负荷运行和新设备投入运行前以及大风、雾天、冰雪、冰雹、雷雨后,巡视任务尤其繁重,适宜采用巡检机器人代替运维人员对设备进行巡检[1-2]。变电站巡检机器人除了用于日常巡视外,还可以实现远方状态识别、远方异常确认、缺陷定点跟踪等一系列功能[3]。巡检机器人的使用不仅有利于提高运维人员的效率和质量,还可以降低运维人员的劳动强度和工作风险[4],有效保障设备安全可靠运行[5-6]。机器人巡检是智能和无人值守巡检技术的发展方向,具有广阔的发展空间和应用前景[7-8]。

目前,变电站巡检机器人的巡视路线通常是在确定机器人生产厂家后,由工作人员根据实际情况进行规划[9]。生产厂家主要考虑的是巡检道路的修建成本以及目前变电站的可利用空间,通常未考虑最佳巡视路线的规划问题[10]。

合理的路径规划不但要求其能够遍历所有巡检点,还需要满足最短路径和最短作业时间。变电站巡检机器人巡视路线优化问题与图论中“中国邮递员问题”相似,该问题的求解分为构造欧拉图和求解欧拉回路两部分。连通图中,节点所连接边的个数称为该节点的度。构造欧拉图就是解决变电站巡检路线拓扑结构图中度为奇数节点的配对问题。

构造欧拉图的方法主要有求最小生成树的算法、奇偶点图上作业法以及最小权完美匹配算法。通过构造最小生成树解决节点的配对问题,其方法主要有如下2 类[11-12]:

(1)在连通图的奇点处作出标记,使用避圈法或破圈法求连通图的最小生成树,将与奇点相连的边尽可能多地保留下来,在奇点处添加重复边,完成奇度节点的配对。

(2)去掉连通图中度为偶数的节点,使用避圈法或破圈法求剩余节点的最小生成树,可以得到奇度节点的配对方案。

上述方案中最小生成树的总权数最小,但节点配对需要的只是该最小生成树的一部分,不能保证取出的几段权数之和最小[12]。

奇偶点图上作业法则通过选择距离最近的两奇度数节点进行配对,重复上述步骤对剩余节点进行配对[13],或去掉已配对节点的关联边后,对剩余节点进行配对[14],但配对完成后还需要采用判优准则进行验证,以调整配对方案。奇偶点图上作业法通俗易懂,当拓扑图较复杂时,计算量也很大。

最小权完美匹配算法对待配对节点的数量没有要求,计算速度快,但应用于巡检机器人巡视路线优化问题,对节点进行配对优化时会出现节点重复配对的现象,准确度不高[11,15]。从研究现状来看,巡检路线图中奇度节点的配对优化方法仍待进一步研究。

本文根据变电站巡检机器人巡视路线图中节点配对问题的特点,将枚举法应用于巡视路线优化,具有优化速度快,准确率高等优点,最后将枚举法推广到多巡检区域奇度节点配对。

1 模型建立

某220 kV 变电站巡检路线如图1 所示,为研究方便,将巡检道路划分为主干道和支路;为了提高算法的优化效果,对原巡检道路进行补充,以形成更多的回路。

图1 某220 kV 变电站巡视路线

以某支路为例,优化前、后的巡视路线如图2 所示。优化前,巡视路线总长度为4b+a,优化后,路线总长度为2b+3a,即当b>a 时,对原道路进行改造;当b

图2 支路优化前后巡视路线

通过分析巡检路线的特征,对巡检路线进行简化,减少参与计算的路径,简化后的结果如图3 所示。图中包括新增道路的位置,度为奇数的节点位置以及各段路线的距离。

图3 机器人巡检主道路

2 优化算法

巡检路线优化首先需要将度为奇数的节点进行配对。当待配对节点数量为4 个时,有3 种配对方法,可以手动计算进行选择;当待配对节点数量为6 个时,有15 种配对方法;当拓扑图中有n 个奇数度节点时,奇数度节点两两配对的方案共有(n-1)×(n-3)×(n-5)…×1 种。

本文将枚举法应用于巡检机器人全局巡检路径规划,可以快速解决奇度节点的最优配对问题,枚举法的算法思想如下:

(1)找出连通图中度为奇数的节点,依次进行编号。

(2)将第一个节点依次与后面的节点进行配对,每进行一次配对,应隐藏参与配对的节点,并对剩余节点重新编号。

(3)判断剩余待配对节点的个数,当剩余节点数量大于4 时,重复步骤2,直至完成所有配对;当剩余节点数量为4 个时,给出剩余节点的3 种配对方案。

(4)节点配对时,应记录两节点之间的最短距离,最后可得到所有的配对方案以及重复巡检路线长度。

枚举法得到的配对方案中,每个节点与其他节点均有一次配对机会。8 节点配对优化问题的优化流程如图4 所示。

采用MATLAB 语言编写枚举法算法,输入奇度节点之间的最短距离矩阵,可得到所有的优化配对结果及重复路线长度。

图4 节点配对优化流程

3 优化结果分析

以220 kV 变电站为例,巡检区域可划分为220 kV 设备区、110 kV 设备区、主变压器(以下简称“主变”)设备区、电容器设备区。目前,巡检机器人分区域进行作业。考虑到变电站设备区的大小、巡检点的数量、电池续航能力以及变电站内检修作业的开展情况,一个巡检任务通常巡检1~2 设备区[3,16]。

在不考虑巡检机器人续航能力的情况下,优化前巡检机器人巡视动态路线如图5 所示:巡检机器人从充电房出发,依次完成主变及电容器设备区、110 kV 设备区、220 kV 设备区的巡检任务,最后返回充电房。

采用枚举法对待配对节点进行匹配优化,得到配对结果为:A-C,B-D,E-G,F-H,连接上述节点,增加重复行驶路线,新的连通图为欧拉图。

图5 优化前巡检动态路线

利用Fleury 算法求解欧拉回路的步骤如下[6]:

(1)连通图G 中,v 代表点,e 代表线,任取G 中一顶点v0,令P0=v0。

(2)假设沿Pi=v0e1v1e2v2…eivi走到顶点vi,从E(G)-{e1,e2,…,ei}中选择的ei+1应满足:ei+1与vi相关联;除非无别的边可供选择,否则ei+1不应该是Gi=G-{e1,e2,…,ei}中的桥。

(3)当步骤2 不能再进行时算法停止。

待配对节点的配对结果及优化后动态巡检路线如图6 所示。

图6 优化后巡检动态路线

优化后,巡检机器人巡视路线从1 020 缩短至833 m,降低了18.3%,证明了枚举法应用于巡检机器人全站全巡路线优化问题的有效性。

巡检结果的分析方法包括三相设备数据对比、与历史数据对比、同相设备之间数据对比等[3]。从巡检路线图来看,优化前的巡检路线,一个设备区巡检结束后,即可查看巡检结果;优化后,需要整个变电站的巡检任务结束后,才能对优化结果进行比较分析。

4 枚举法的推广应用

基于枚举法的6 节点、8 节点配对优化算法,基本可以满足目前变电站的使用需求,当更多的节点需要进行配对时,可以对算法进行改进或采用分区域配对优化的方案。分区域配对方案的实施包括奇度节点聚类分析、奇度节点分区域配对优化、采用判优准则验证配对结果三部分。

某变电站巡检路线的拓扑结构如图7 所示[4],图中简化了独立的不闭合路线,增加巡检道路以形成更多的回路。图中标注了各段巡检道路的长度、奇度节点的位置。

图7 巡检路线简化拓扑结构

4.1 奇度节点聚类分析

图7 中待配对的节点数量为12 个,以节点r为坐标原点,建立直角坐标系,得到待配对节点的坐标如图8 所示。

将待配对节点从上往下、从左往右进行排序,采用MATLAB 中K-means 函数对上述样本进行聚类。K-means 聚类算法的一般步骤为:

(1)初始化

图8 待配对节点空间位置

输入数据集X,该数据集有n 个样本,输入聚类类别K。在n 个样本中随机选取K 个样本作为初始聚类中心(也称为Means)。设置迭代终止条件,如最大循环次数或者聚类中心收敛误差值。

(2)计算距离并进行聚类分组

计算n 个样本与K 个中心点之间的距离,将数据样本分配到最接近的聚类中心。

(3)更新聚类中心

根据聚类分组中的样本,重新计算每个聚类的中心点。

(4)迭代直至收敛

反复执行步骤2 和步骤3 直至满足终止条件。

K-means 聚类算法需要提前知道数据的分类,具有计算简便、速度快等优点。聚类类别选择2,可得到聚类结果为:2,2,1,1,1,2,2,1,1,1,2,2。因此,将待配对节点根据其所在区域划分为区域1 和区域2,如图9 所示。区域1包括待配对节点c,e,f,g,h,i;区域2 包括待配对节点n,o,p,r,s,t。

4.2 奇度节点分区域配对优化

输入区域1 和区域2 待配对节点的最短距离矩阵,采用枚举法进行配对优化,各节点的配对结果为:c-e,f-g,h-i,n-o,p-r,s-t,各节点的配对方案如图9 所示。

4.3 采用判优准则验证配对结果

配对成功与否的验证方法为:将欧拉图中重复行驶路线求和,如果小于总长度的一半则为可行解;如果欧拉图中每个闭合回路重复路线的长度都小于该闭合回路总长度的一半,则为最优解。

采用上述判优准则对配对结果进行验证,如表1 所示。

图9 待配对节点优化结果

表1 奇度节点配对结果验证

表中各闭合回路重复路线占比均小于50%,说明先通过聚类算法对节点分类,再采用枚举法对奇度节点进行配对的方案是可行有效的。

5 结语

本文根据生产实际中变电站巡检路线简化图中奇度节点的数量、节点的配对规律,将枚举法应用于节点配对优化,求解欧拉回路得到某220 kV 变电站巡检机器人全站巡检最佳路线。针对待配对节点较多的情形,本文采用聚类算法对待配对节点进行分类,对奇度节点分区域进行优化,最后采用判优准则验证了上述方案的可行性。

猜你喜欢
路线聚类变电站
最优路线
『原路返回』找路线
基于K-means聚类的车-地无线通信场强研究
关于变电站五防闭锁装置的探讨
画路线
超高压变电站运行管理模式探讨
基于高斯混合聚类的阵列干涉SAR三维成像
找路线
220kV户外变电站接地网的实用设计
基于Spark平台的K-means聚类算法改进及并行化实现