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

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

0 引言

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

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

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

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

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

1.1 Dijkstra 算法基本原理

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

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

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

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

（3）更新U 中各個(gè)頂點(diǎn)到起點(diǎn)s 的距離。

（4）重復(fù)（2）和（3），直到遍歷所有頂點(diǎn)。

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

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

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

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

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

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

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

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

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

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

根據(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)化

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

表1 設(shè)備名稱

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

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

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

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

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

表4 地上路徑向量列表 min

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

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

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

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

3 結(jié)語(yǔ)

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