基于Dijkstra 算法的輸電線路人工巡檢優(yōu)化方法

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

（國網(wǎng)浙江省電力有限公司杭州供電公司，杭州 310009）

0 引言

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

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

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

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

1 基于Dijkstra 算法的路徑規(guī)劃方法

1.1 Dijkstra 算法基本原理

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

假設(shè)V 是所有路徑中包含頂點的集合。將V分成2 組，第一組為已求出最短路徑的頂點集合，記為S；第二組為其余未確定最短路徑的頂點集合，記為U。初始狀態(tài)時，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）重復(fù)（2）和（3），直到遍歷所有頂點。

1.2 基于Dijkstra 算法的路徑規(guī)劃

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

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

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

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

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

2 輸電線路人工巡檢路徑優(yōu)化

2.1 Dijkstra 路徑規(guī)劃仿真

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

圖2 路線節(jié)點示意

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

圖3 規(guī)劃的最短路徑

2.2 輸電線路巡檢路徑優(yōu)化

為驗證基于Dijkstra 算法的路徑規(guī)劃方法的有效性，對4 條輸電線路進行了巡檢路徑優(yōu)化。表1 列出了以4 條線路為例，按照國家電網(wǎng)統(tǒng)一規(guī)則命名的設(shè)備表格。

表1 設(shè)備名稱

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

表2 節(jié)點信息表格記錄

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

表3 節(jié)點信息表格記錄

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

表4 地上路徑向量列表 min

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

根據(jù)Dijkstra 路徑規(guī)劃方法，將最優(yōu)路徑的結(jié)果用圖形化的方式進行直觀表達，如圖5 所示。根據(jù)該規(guī)劃路徑，巡檢完13 個塔桿所需的時間為33.6 min。而在常規(guī)巡檢路線中，路線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 路徑規(guī)劃的總巡檢時間為43.5 min，而常規(guī)路徑的總巡檢時間分別為53.8 min 和47.9 min。可見，Dijkstra 路徑規(guī)劃方法縮減了人工巡檢時間，提高了巡檢效率。

圖5 地上最優(yōu)巡檢路徑示意

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

3 結(jié)語

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