基于Dijkstra 算法的輸電線路人工巡檢優化方法

秦 奮，姚紅芳，馬蔡國，張俊婷，倪 濤，許金彤

（國網浙江省電力有限公司杭州供電公司，杭州 310009）

0 引言

輸電線路是電力系統的重要組成部分，其安全運行是系統整體穩定的重要保障。輸電線路及其附屬設備暴露在野外，其運行方式必定會受到環境因素、人為因素和設備自身因素等的影響，線路巡檢已經成為必不可少的運維任務。隨著經濟建設對電力需求的日益增長，線路巡檢成本越來越高。

目前，國內輸電線路巡檢方式主要有人工巡檢、無人機巡檢和車輛巡檢等[1-3]。在車輛巡檢和無人機巡檢應用中存在很多人工智能算法優化巡檢路徑[4-5]，其中包括粒子群算法、遺傳算法和蟻群算法等智能算法，利用智能算法在無人機和車輛巡檢中可以科學合理地對巡檢路徑進行規劃，提高巡檢效率。但由于輸電線路環境的復雜性，很多情況無法采用汽車巡檢和無人機巡檢，必須依靠人工。傳統人工輸電線巡檢路徑規劃大多由有經驗的巡檢員制定巡檢路徑，這種依靠經驗的方式存在很強的主觀性，缺乏科學性和客觀評價體系，因此存在著人力的浪費和塔桿、線纜井等設備巡檢不到位的情況[6-8]。對輸電線路人工巡檢路徑進行優化，可以有效提升巡檢效率，并能輸出有效數據以建立客觀評價體系，避免設備巡檢不到位或被多次巡檢，以節省人力資源和費用，因此具有重要意義[9-10]。

Dijkstra（狄克斯特拉）算法是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，它是從一個頂點到其余各頂點的最短路徑算法，解決的是有權圖中最短路徑問題[11-13]。Dijkstra 算法的主要特點是從起始點開始，采用貪心算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接節點，直到擴展到終點為止[14-15]。目前，該算法在農業、化工和網絡等領域得到了廣泛的研究和應用。但在輸電線路巡檢領域，基于Dijkstra 算法的路徑規劃方法的研究還很少。與遺傳算法等智能算法相比，Dijkstra 算法計算簡單、運行時間短，在全局信息已知、靜態規劃中，采用Dijkstra算法更加方便快捷。

因此，本文采用Dijkstra 算法研究輸電線路人工巡檢路徑的優化方法，通過規劃最短巡檢路徑，從而提高巡檢效率。

1 基于Dijkstra 算法的路徑規劃方法

1.1 Dijkstra 算法基本原理

Dijkstra 算法是典型的單源最短路徑算法，用于計算一個節點到其他所有節點的最短路徑。

假設V 是所有路徑中包含頂點的集合。將V分成2 組，第一組為已求出最短路徑的頂點集合，記為S；第二組為其余未確定最短路徑的頂點集合，記為U。初始狀態時，S 中只有一個源點，以后每求得一條最短路徑，就將其加入到集合S 中，直到全部頂點都加入到S 中為止。在加入的過程中，總保持從源點v 到S 中各頂點的最短路徑不大于從源點v 到U 中任何頂點的最短路徑。Dijkstra 算法的一般步驟如下：

（1）初始時，S 只包含起點s；U 包含除s 外的其他頂點，且U 中頂點的距離為起點s 到該頂點的距離。U 中頂點v 的距離為（s，v）的長度，若s和v 不相鄰，則v 的距離為∞。

（2）從U 中選出距離最短的頂點k，并將頂點k 加入到S 中；同時，從U 中移除頂點k。

（3）更新U 中各個頂點到起點s 的距離。

（4）重復（2）和（3），直到遍歷所有頂點。

1.2 基于Dijkstra 算法的路徑規劃

根據Dijkstra 算法的基本策略，人工巡檢路徑規劃的方法流程如圖1 所示。

圖1 基于Dijkstra 算法的人工巡檢流程

首先，提取線路上設備的唯一名稱和GIS（地理信息系統）坐標信息。由于線路上設備的命名規則按照國家電網統一規則（線路名稱+設備編號），因此每個設備的名稱是唯一的，并將這些信息作為該節點信息保存。按照預先設定好的GIS 信息精度要求，對系統中的所有節點GIS 信息的經度和緯度數據進行比較。將符合精度要求的、經度和緯度數據認為是一致的GIS 信息進行合并，只保留GIS 信息一致的節點編號較小的節點信息，并將一個或多個GIS 信息一致、節點編號較大的節點信息從系統列表中刪除。

其次，根據各個節點之間的GIS 坐標信息或已知路徑來計算各節點之間的路徑長度，并保存在路徑向量列表中。路徑向量列表包含以下數據：起始節點編號，終點節點編號，路徑長度（向量），路徑屬性。由于線路巡檢包含地上（塔桿）和地下（線纜井），在計算路徑規劃之前將地上（塔桿）和地下（線纜井）做為限制條件對線路屬性進行分類拆分。則一條完整的線路中，可以有3 種情況：只由地上（塔桿）的路徑屬性組成一條完整的線路；只由地下（線纜井）的路徑屬性組成一條完整的線路；由1 段或多段地上（塔桿）的路徑屬性和1 段或多段地下（線纜井）的路徑屬性共同組成一條完整的線路。

最后，采用Dijkstra 最短路徑算法來對輸電線路中的所有路徑向量列表進行巡檢路徑規劃。對于以節點表示的線路列表中的每一個節點進行檢測，按照節點編號從小到大的順序進行排列的每個節點都通過其2 個節點之間的路徑向量進行連接。如果該線路上的所有節點都被檢測到了，說明該條線路已完成巡檢，則此時的路徑即為最優路徑。

2 輸電線路人工巡檢路徑優化

2.1 Dijkstra 路徑規劃仿真

本文將Dijkstra 算法在仿真巡檢節點上進行了驗證，仿真的巡檢路線節點包含A，B，C，D，E，F 共6 個節點，各節點之間的距離如圖2 所示。

圖2 路線節點示意

根據第1 節的Dijkstra 路徑規劃方法，規劃的最短路徑如圖3 所示，路徑距離總和為16 km。相比于其他路徑，例如D-E-B-C-A-F 的總路徑距離為23 km 或D-C-A-F-B-E 的總路徑距離為28 km 等，基于Dijkstra 算法規劃的路徑距離得到了大幅縮減。

圖3 規劃的最短路徑

2.2 輸電線路巡檢路徑優化

為驗證基于Dijkstra 算法的路徑規劃方法的有效性，對4 條輸電線路進行了巡檢路徑優化。表1 列出了以4 條線路為例，按照國家電網統一規則命名的設備表格。

表1 設備名稱

提取該設備的線路名稱及該設備在該線路內的設備編號、GIS 坐標信息，將這些信息作為該節點信息進行保存。還是以表1 中4 條線路的設備信息為例，節點信息表格記錄如表2 所示。

表2 節點信息表格記錄

對符合精度要求、經度和緯度數據認為是一致的GIS 信息進行合并。合并后的信息如表3 所示。顯然，在實際生成的優化巡檢路徑中，即使其設備在表1 中都屬于同一條線路，地上（塔桿）/地下（線纜井）也是2 條毫不相關的路徑。因此對表3 中只以地上（塔桿）的數據為例，建立地上（塔桿）路徑向量列表，見表4。表4 中的數據為2 個節點之間巡檢所需的時間。

表3 節點信息表格記錄

為直觀地表示，將表4 中的數據用圖形化的方式進行表達，如圖4 所示。

表4 地上路徑向量列表 min

圖4 地上初始巡檢路徑示意

根據Dijkstra 路徑規劃方法，將最優路徑的結果用圖形化的方式進行直觀表達，如圖5 所示。根據該規劃路徑，巡檢完13 個塔桿所需的時間為33.6 min。而在常規巡檢路線中，路線1-2-6-3-4-8-5-7-11-10-9-13-12 所需的巡檢時間為41.1 min，路線1-4-8-9-13-10-5-3-2-6-7-11-12 所需的巡檢時間為35.2 min。加上巡檢人員的返程路徑，Dijkstra 路徑規劃的總巡檢時間為43.5 min，而常規路徑的總巡檢時間分別為53.8 min 和47.9 min。可見，Dijkstra 路徑規劃方法縮減了人工巡檢時間，提高了巡檢效率。

圖5 地上最優巡檢路徑示意

此外，若設備信息或線路信息有變動，如增加、刪除、修改GIS 信息和修改名稱等，這些變動都會對節點信息或路徑向量信息產生影響，因此需要重新計算。對此，可對巡檢優化方法的系統設置定時計算周期，如果在設定的周期內發生上述信息的改變，則到了指定時間系統即開始重新計算優化路徑；如果在設定的周期內未發生上述信息改變，則到了指定時間系統不做更新計算。

3 結語

本文采用Dijkstra 算法對4 條輸電線路人工巡檢路徑進行了優化，算法考慮了巡檢員巡檢路徑長度最小化和巡檢線路屬性的因素，科學制定巡檢路徑，巡檢時間由常規的53.8 min 和47.9 min 縮短至43.5 min。該方法既適用于電力供電部門輸電線路人工巡檢的路徑優化，也適用于配電線路人工巡檢的路徑優化。