考虑通行时间的大量变电站巡视路径两阶段规划.pdf

第 38 卷 第 2 期2023 年 4 月Vol.38 No.2Apr.2023电力学报JOURNAL OF ELECTRIC POWER文章编号：1005-6548（2023）02-0110-07 中图分类号：TM743 文献标识码：B 学科分类号：47040DOI：10.13357/j.dlxb.2023.012开放科学（资源服务）标识码（OSID）：考虑通行时间的大量变电站巡视路径两阶段规划卫春峰，殷展，陈冠，陈东（国网上海嘉定供电公司，上海 201800）摘要：大量变电站站间巡视路径受地理条件和交通拥堵影响较大，针对其巡视路径规划问题，考虑实际工作场景先划分巡视范围给各个巡视小组，同时巡视路径应充分考虑通行时间的影响，建立了巡视范围划分模型和巡视线路模型，采用两阶段规划求解最优巡视路径。第一阶段基于通行时间最短采用改进 K-Means算法将大量变电站划分给各个巡视小组，第二阶段对各个巡视小组的变电站基于多起点贪心算法生成最优巡视路径，并提出了提升算法寻优能力和效率的措施。算例结果表明所提算法具有较好的收敛性和寻优能力，以通行时间最短为目标将大幅节省巡视人员路程时间，具有较好的实用价值，能够有效减少变电站巡视人员每轮的通行时间，提高工作效率。关键词：变电站；站间巡视；路径规划；地理条件；巡视范围划分；改进 K-Means算法；通行时间；多起点贪心算法Two Stage Planning of Patrol Routes for a Large Number of Substations Considering Traffic TimeWEI Chunfeng，YIN Zhan，CHEN Guan，CHEN Dong（State Grid Shanghai Jiading Power Supply Company，Shanghai 201800，China）Abstract：The patrol path between a large number of substation stations is greatly affected by geographical conditions and traffic congestion.Aiming at the problem of patrol path planning，considering that the patrol scope is first divided to each patrol group in practical work，and the patrol path should fully consider the influence of travel time，the patrol scope division model and the patrol line model are established，and then the two-stage planning is used to solve the optimal patrol path.In the first stage，based on the shortest travel time，a large number of substations are divided into various inspection groups by using the improved K-Means algorithm.In the second stage，the substations of each inspection group are based on the multi-start greedy algorithm to generate the optimal inspection path，and the measures to improve the optimization ability and efficiency of the algorithm are proposed.The result of the example shows that the proposed algorithm has good convergence and optimization ability.Taking the shortest travel time as the goal will greatly save the distance time of the patrol personnel.It has good practical value and can effectively reduce the travel time of each round of the substation patrol personnel and improve the work efficiency.Key words：transformer substation；interstation patrol；path planning；geographical conditions；patrol scopes di 收稿日期：2022-10-16作者简介：卫春峰（1989），男，硕士，工程师，研究方向为配电网规划、可靠性分析、新能源消纳，；殷展（1982），男，硕士，高级工程师，主要研究配电线路；陈冠（1983），男，硕士，工程师，主要从事继电保护工作；陈东（1968），男，助理工程师，主要从事电力运维工作。引文格式：卫春峰，殷展，陈冠，等.考虑通行时间的大量变电站巡视路径两阶段规划 J.电力学报，2023，38（02）：110-116.DOI：10.13357/j.dlxb.2023.012.第 2 期卫春峰，等：考虑通行时间的大量变电站巡视路径两阶段规划vision；improved K-Means algorithm；traffic time；muti starting points greedy algorithm0 引言 变电站巡视是电力企业运维人员的重要工作内容1-2，按照路径合理地将每个变电站分配给各组巡视人员可大幅减少站与站之间的车程，节省运维人员路程时间，提高巡视工作质量。变电站巡视划分问题不仅要考虑各变电站之间的直线距离，还要考虑河流、山川等地理条件约束3，同时还要考虑火车路径、高速公路等对地面通行的不利影响。目前城市变电站巡视主要的通行工具为工程车、轿车等。跨越火车路径、高速公路的高架或者下穿隧道往往由于建造成本高而较少，这些地点往往是交通堵塞点，对于城市变电站巡视路径规划结果有较大影响。因此变电站巡视路径规划应充分考虑实际站间通行时间的影响。目前已开展的变电站巡视路径规划主要集中在单一站内各设备的巡视路径规划4-7，对于大量变电站站间巡视路径规划的研究较少。由于站内巡视不需要考虑实际交通情况，所以路径规划以考虑总路程数最小为目标，但对于大量变电站巡视路径规划则以总通行时间最小为目标函数更加合理。同时考虑到大量变电站巡视需要多组巡视人员分工完成，因此大量变电站巡视规划应重点解决考虑通行时间最短的巡视范围划分，接着对各个范围内变电站形成最优巡视路径。路径规划算法问题是典型的旅行商问题（Travelling Salesman Problem，TSP），目前已有基于图论和智能算法求解该模型的相关研究成果8-11。文献 4 采用粒子群算法求解最优巡视路径，文献 12 对比了遗传算法、模拟退火算法和蚁群算法求解最短巡视路径的效率，在变电站数量增多时蚁群算法的寻优能力强于遗传算法和模拟退火算法。对于大量变电站巡视范围划分可以采用 K-Means聚类算法13-15，但是该算法中两点之间采用直线距离来衡量，需要对算法进行改进以满足实际需求。将各个变电站划分到各个小的变电站集合后，由于变电站数量相对减少可以采用贪心算法求解最优巡视路径16，变电站数量较少时通过贪心算法求解的巡视路径与最优巡视路径较为接近或相等。在采用贪心算法求解最优巡视路径时，起始点的选择对于最终的路径方案具有较大影响，为了提高寻优能力需要对贪心算法进行优化。针对大量变电站需要多组巡视人员分工完成的情况，本文采用两阶段巡视路径规划算法，第一阶段首先将所有城市变电站划分给各个小组，第二阶段针对各个小组生成最优巡视路径。首先建立了基于总通行时间最短的变电站巡视范围划分模型，约束条件考虑了各个巡视小组的巡视站点数量限制，同时建立了考虑通行时间最短的各小组巡视路径规划模型。接着分别采用改进 K-Means聚类算法和多起点贪心算法求解两阶段的模型。1 巡视路径规划模型 1.1巡视范围划分模型对于同一巡视小组，其所分配的各个变电站之间通行时间应该尽量短，同时各个巡视小组的总体通行时间尽量短。本文以各巡视小组所分配站到其巡视范围中心点的通行时间最短为目标函数，使相互之间通行时间较短的变电站尽量分给同一巡视小组，如式（1）所示：min f1=i=1Kpj Jit(pj，zi).（1）式中，K 为巡视小组的数量；Ji为划分给第 i巡视小组的变电站集合；pj为 Ji中的第 j个变电站；zi为 Ji中的通行中心变电站，即以该变电站为中心到集合中各变电站的通行时间之和最小；t（pj，zi）函数为变电站 pj到通行中心变电站 zi之间的通行时间。约束条件为各个巡视小组的巡视变电站数量上下限约束，且各小组巡视的变电站数量之和等于总变电站数量，如式（2）、式（3）所示。Nmin Ni Nmax.（2）i=1KNi=Nsub.（3）111第 38 卷电力学报式（2）、式（3）中，Ni为第 i巡视小组的巡视变电站数量，Nmin和Nmax为各小组巡视变电站数量的下限与上限，Nsub为所有变电站数量。1.2各小组巡视路径模型对于各个巡视小组，以考虑通行时间最短为巡视路径规划目标，如式（4）所示：min f2=pj，qj Jit(pj，qj).（4）式中，f2为各个巡视小组以所分配的某一变电站为起点，对所分配的所有变电站巡视一次所需的通行时间；pj和qj为该巡视小组所分配的变电站集合Ji中的变电站；t(pj，qj)为变电站pj到变电站qj的通行时间。约束条件为任意变电站都被巡视且只巡视一次，如式（5）所示：X(pj)=1 ，pj Ji.（5）式中，X(pj)为变电站pj的巡视次数。2 两阶段巡视路径算法 2.1基于改进 K-Means的巡视范围划分算法在变电站巡视范围划分的实际问题中，对传统 K-Means聚类算法进行如下改进：1）考虑变电站之间通行时间约束，坐标上直线距离近的两个变电站可能由于地形或火车线路等因素导致通行较长，将传统算法以距离为划分标准改为以实际通行时间为标准。2）考虑各个巡视小组所分配的变电站数量的上下限约束，设置聚类中变电站数量约束。在聚类迭代过程中若某聚类中变电站数量已经达到上限，则将剩余的变电站到该聚类中心的通行时间临时设置为无穷大，使剩余变电站可分配至其他聚类。3）每次迭代过程中，变电站计算顺序对于聚类结果有较大影响，为了提高全局最优寻优能力，新生成聚类中心后对变电站顺序随机打乱。2.2基于多起点贪心算法的最优路径算法对于各小组分配到的变电站求解最优巡视路径问题，由于变电站数量相对较少，遗传算法、粒子群算法等智能算法本身编程较为复杂，在变电站数量增多时才能体现出算法的优势。如果直接采用枚举法求解最优巡视路径，则可能的排列组合数量为变电站数量Nsub的阶乘Nsub！，变电站数量增加时组合数量急剧上升17-18。介于以上两类算法之间的是贪心算法求解 TSP 问题，该算法原理和实现较为简单，具有寻优能力强、算法效率高的特点。需要对贪心算法求解 TSP 问题改进的是：1）采用两点之间通行时间来取代两点之间的距离；2）贪心算法分别以各个变电站作为起始站点生成巡视路径，然后对比选取总通行时间最短的路径作为最优巡视路径。2.3两阶段巡视路径算法流程变电站与变电站之间的通行时间可以采用地图导航软件基于同一时刻所计算得到的时间为依据。但是考虑到大量变电站相互之间通行时间需要统计Nsub(Nsub-1)次，统计工程量巨大，同时通行时间较远的变电站距离直接设置为无穷大反而能够提高聚类算法的收敛性，可以只计算各个变电站距离其最近的2Nsub/K个变电站的通行时间，即只需统计Nsub 2Nsub/K次，其余变电站之间的通行时间统一设置为无穷长时间，工作量接近于原来的2/K。基于改进 K-Means算法和多起点贪心算法的两阶段巡视路径算法流程如下：1）开始第一阶段生成最优巡视范围划分。设置巡视小组数量 K和各个小组巡视变电站数量的下限Nmin和上限Nmax，设置各个变电站的坐标和相互之间的通行时间t(pj，qj)。2）从变电站集合P=p1，p2，pNsub中初始随机选择 K 个变电站作为初始通行中心变电站位置。设置聚类评价函数初值f1为无穷大，确定评价函数收敛精度。设 c和cmax分别为迭代次数和迭代次数上限，令c=1。3）如果从某变电站pj（j=1，2，Nsub）到通行中心变电站zi*的通行时间小于到其原通行中心变电站zi的通行时间，即t(pj，zi*)t(pj，zi)，i=1，2，K，且i i*时，那么将变电站pj分配到第i*个变电站的聚类中。112第 2 期卫春峰，等：考虑通行时间的大量变电站巡视路径两阶段规划4）经过上述步骤，Nsub个变电站都已经分配到各个巡视范围中，按照式（1）计算评价函数值f1。5）如果|f1 或者c=cmax，则算法收敛或迭代结束，K个巡视范围划分完成，并转向步骤 8）；否则转向步骤 6）。6）按照变电站位置重新计算K个变电站聚类的中心坐标，选取与该聚类中心最近的变电站作为新的通行中心变电站zi。7）为跳出局部最优解，随机打乱Nsub个变电站节点的顺序。令c=c+1，转到步骤 3）。8）开始第二阶段生成最优巡视路径，令i=1。9）对第 i个巡视范围内的变电站采用基于评价函数f2的多起点贪心算法求解最优巡视路径。以各个变电站为起点，每次寻找通行时间最近的变电站为下一巡视点，直到遍历所有变电站，再比较不同起点生成的巡视路径，选取总通行时间最短的路径为该巡视范围最优路径。10）若i K，令i=i+1，返回步骤9），否则转到步骤11）。11）输出各个巡视划分范围内的最优巡视路径。算法的流程如图 1所示。3 算例分析 3.1仿真算例本文算例涉及到 85座变电站信息，变电站的相对位置分布如图 2所示，图中蓝色实线为高铁线路，玫红色虚线为省际高速公路，对通行时间有较大影响。共设置 8个巡视小组，每组巡视变电站 911 座。以 MATLAB R2012a 为编程环境，i5-9600KF 处 理 器 的 台 式 电 脑 为 运 行 环 境，设 置 改 进 K-Means算法迭代 800次。为了与传统以最短路径为目标的巡视路径规划进行对比，定义了两个不同方案，比较两方案的总通行距离和总通行时间：方案一，变电站巡视范围划分和各范围内最优路径规划只考虑站间距离，不考虑通行时间；方案二，变电站巡视范围划分和各范围内最优路径规划都考虑实际通行时间，不考虑站间距离。3.2仿真结果分析在算法收敛性方面，在方案二第 43 次迭代时得到第一阶段最优巡视范围划分。算法收敛性如图 3 所示，两阶段算法共计耗时 8.8 s生成最优巡视路径，算法整体寻优能力强、效率较高。方案一和方案二的第一阶段巡视范围划分如图 4和图 5所示，图 4中方案一的巡视范围划分出现了跨越高铁线路和省际高速公路的情况，如巡视范围 3、7和 8，各巡视范围与方案二相比更加趋近于圆形。图 5中方案二各个巡视范围没有出现跨越高铁线路或者省际高速公路的情况，如巡视范围 4和 8沿着高铁线路隔岸划分，巡视范围划分较为合理，部分巡视范围沿着高铁线路呈现细长形，如巡视范围 4。方案一和方案二的第二阶段各巡视范围最优巡视路径分别如图 6和图 7所示，图 6中方案一巡视路径出现了 4次跨越高铁线路或高速公路的情况，分别为变电站 58变电站 61、变电站 48变电站 39、变电站 39变电站 42、变电站 30变电站 34，这将大大增加通行时间。图 7中方案二各巡视路径均没有出现跨越高铁线路或高速公路的情况，将节省大量通行时间。图 1算法流程图Fig.1Algorithm flow chart113第 38 卷电力学报对具体数据而言，方案一和方案二的总通行距离和总通行时间如表1所示。在通行距离方面，方案二比方案一总通行距离短7.248 km，减少3.6%的路程。虽然方案一以最短距离为目标进行两阶段的计算，但是由于巡视范围的形状相对较圆导致巡视路径中出现较远折返的情况，如图6中变电站18变电站20；而图7中方案二巡视范围 4虽相对狭长却未出现巡视路线远距离折返的情况。在总通行时间方面，方案二比方案一节省了1.79 h，减少 12.2%的通行时间，主要原因为巡视路线没有跨越交通拥堵的路段，每年进行多轮巡视时将节省大量通行时间。图 2变电站分布图Fig.2Substation distribution map图 3第一阶段算法收敛性Fig.3Algorithm convergence of Stage I图 4方案一巡视范围划分Fig.4Division of patrol scopes of Scheme 1图 5方案二巡视范围划分Fig.5Division of patrol scopes of Scheme 2114第 2 期卫春峰，等：考虑通行时间的大量变电站巡视路径两阶段规划4 结论 针对大量变电站巡视路径规划问题，本文首先建立了巡视范围划分模型和各小组路径规划模型，接着采用两阶段规划求解最优巡视路径。第一阶段基于通行时间最短采用改进 K-Means算法将大量变电站划分给各个巡视小组，第二阶段对各个巡视小组的变电站基于多起点贪心算法求解最优巡视路径。算例结果表明本文所提算法具有较好的收敛性和寻优能力，以通行时间最短为目标将大幅节省巡视人员路程时间，具有较好的实用价值，能够有效减少变电站巡视人员每轮的通行时间，提高工作效率。1）针对大量变电站巡视路径规划问题，考虑实际工作中往往先划分巡视范围给各个巡视小组，同时巡视路径应充分考虑通行时间的影响，建立了巡视范围划分模型和巡视线路模型。2）针对以上两个模型采用两阶段规划求解，第一阶段采用基于通行时间最短的 K-Means算法求解最优巡视范围划分方案；第二阶段采用多起点贪心算法求解中量数量的变电站巡视路径规划问题，提出了多项提高算法收敛性和寻优能力的措施。3）本文所提算法，具有较强的实际意义，可大幅减少每轮巡视时间。参考文献：1 刘洋.变电站巡视中存在的若干问题及对策 J.信息记录材料，2019，20（3）：237-238.2 尹雁和，贾子然，曾毅豪，等.变电站巡视中的图像识别技术应用 J.通信电源技术，2020，37（3）：141-142.YIN Yanhe，JIA Ziran，ZENG Yihao，et al.Application of Image Recognition Technology in Substation Patrol J.Telecom Power Technology，2020，37（3）：141-142.3 符杨，卫春峰，李振坤，等.考虑地理信息和行政边界的变电站供区优化 J.电网技术，2014，38（1）：126-133.FU Yang，WEI Chunfeng，LI Zhenkun，et al.Optimal Partitioning of Substation Service Areas Considering Impacts of Geo图 6方案一最优巡视路径Fig.6Optimal patrol routes of Scheme 1图 7方案二最优巡视路径Fig.7Optimal patrol routes of Scheme 2表 1方案对比Tab.1Schemes comparison参数方案一方案二提升率/%通行距离/km201.097193.8493.6通行时间/h14.7112.9212.2115第 38 卷电力学报graphic Information and Administrative Boundaries J.Power System Technology，2014，38（1）：126-133.4 钟成.基于改进粒子群算法的变电站巡视路径问题研究 J.云南电力技术，2020，48（3）：17-20.ZHONG Cheng.Study on the Perambulate Path of Substation Based on Improved Particle Swarm Optimization J.Yunnan Electric Power，2020，48（3）：17-20.5 梁建来，陈斌，朱从刚.变电智能巡视功能的拓展研究：GPS、3G 和 GIS 在无人值守变电站巡视维护及日常管理中的应用 J.自动化应用，2018（9）：108-109.6 邢耀杰，李艳.基于邮递员问题的变电站巡视路线研究 J.科技风，2018（24）：208.7 彭光超.基于邮递员问题的深圳供电局变电站巡视路线研究 D.天津：天津大学，2016.PENG Guangchao.Research on the Route of the Shenzhen Power Supply Bureau Substation Patrol Based on the Postman Problem D.Tianjin：Tianjin University，2016.8 张永涛，李博，张甲，等.基于图论的变电站巡检机器人全局路径规划 J.山东电力技术，2020，47（9）：45-49，66.ZHANG Yongtao，LI Bo，ZHANG Jia，et al.Global Path Planning of Substation Inspection Robot Based on Graph TheoryJ.Shandong Electric Power，2020，47（9）：45-49，66.9 关健，刘悦.基于蚁群算法的变电站巡检机器人自主导航方法 J.黑龙江电力，2017，39（4）：319-322，346.GUAN Jian，LIU Yue.Autonomous Navigation Method of Substation Inspection Robot Based on Ant Colony AlgorithmJ.Heilongjiang Electric Power，2017，39（4）：319-322，346.10 徐平，刘悦.基于改进 Kruskal算法的变电站机器人路径规划 J.广东电力，2016，29（12）：6-9.XU Ping，LIU Yue.Path Planning for Substation Robot Based on Improved Kruskal AlgorithmJ.Guangdong Electric Power，2016，29（12）：6-9.11 张营，鲁守银.基于 Hopfield神经网络的变电站巡检机器人自主导航方法 J.制造业自动化，2015，37（21）：36-38，41.ZHANG Ying，LU Shouyin.Autonomous Navigation Method of the Substation Inspection Robot Based on Hopfield Neural Network J.Manufacturing Automation，2015，37（21）：36-38，41.12 李锋，赵芳，王新磊，等.基于蚁群算法的光缆巡检最短路径规划研究 J.电力设备管理，2021（6）：153-154.LI Feng，ZHAO Fang，WANG Xinlei，et al.Research on the Shortest Path Planning of Optical Cable Inspection Based on Ant Colony Algorithm J.Electric Power Equipment Management，2021（6）：153-154.13 吴蕊，张安勤，田秀霞，等.基于改进 K-Means 的电力数据异常检测算法 J.华东师范大学学报（自然科学版），2020（4）：79-87.WU Rui，ZHANG Anqin，TIAN Xiuxia，et al.Anomaly Detection Algorithm Based on Improved K-Means for Electric Power Data J.Journal of East China Normal University（Natural Science），2020（4）：79-87.14 梁京章，黄星舒，吴丽娟，等.基于 KPCA 和改进 K-Means的电力负荷曲线聚类方法 J.华南理工大学学报（自然科学版），2020，48（6）：143-150.LIANG Jingzhang，HUANG Xingshu，WU Lijuan，et al.Clustering Method of Power Load Profiles Based on KPCA and Improved K-Means J.Journal of South China University of Technology（Natural Science Edition），2020，48（6）：143-150.15 成乐祥，季丽.基于加权 K-means聚类和遗传算法的变电站规划 J.江苏电机工程，2016，35（6）：9-12.CHENG Lexiang，JI Li.Substation Planning Based on Weighted K-Means Cluster Algorithm and Genetic Algorithm J.Jiangsu Electrical Engineering，2016，35（6）：9-12.16 来学伟.两种不同贪心算法在求解TSP问题中的应用和比较 J.河北北方学院学报（自然科学版），2018，34（7）：34-37.LAI Xuewei.Application and Comparison of Two Different Greedy Algorithms for Solving TSP ProblemJ.Journal of Hebei North University（Natural Science Edition），2018，34（7）：34-37.17 张永涛，于倩倩，肖智彬，等.基于枚举法的变电站巡检机器人巡视路线优化 J.浙江电力，2021，40（1）：12-17.ZHANG Yongtao，YU Qianqian，XIAO Zhibin，et al.Inspection Route Optimization of Substation Inspection Robot Based on Enumeration Method J.Zhejiang Electric Power，2021，40（1）：12-17.18 程维杰，程韧俐，徐洲，等.基于隐枚举法的快速分级切负荷优化方法 J.智慧电力，2021，49（5）：63-68.CHENG Weijie，CHENG Renli，XU Zhou，et al.Fast Hierarchical Load Shedding Optimal Method Based on Implicit Enumeration Method J.Smart Power，2021，49（5）：63-68.责任编辑：常建峰116