面向巡檢車與無人機(jī)協(xié)同電力巡檢的車輛路徑規(guī)劃方法

曹 峰，崔少華，荊治家，姚寶珍

（1.大連理工大學(xué)，汽車工程學(xué)院，大連 116024；2.北京航空航天大學(xué)，交通科學(xué)與工程學(xué)院，北京 100191）

0 引言

小型多旋翼無人機(jī)憑借其機(jī)動(dòng)性強(qiáng)、作業(yè)效率高、易于發(fā)現(xiàn)桿塔平口以上缺陷等人工巡檢無法比擬的優(yōu)勢，目前已成為輸電線路巡檢的主要設(shè)備之一[1-2]。為了解決無人機(jī)電力巡檢作業(yè)中存在的航跡規(guī)劃難、大范圍快速機(jī)動(dòng)性差、自主規(guī)劃控制能力弱等問題，部分電力企業(yè)提出了巡檢車與無人機(jī)協(xié)同巡檢（即車機(jī)協(xié)同巡檢）作業(yè)模式。該作業(yè)模式中，智能巡檢車為無人機(jī)提供能源補(bǔ)給并運(yùn)載其進(jìn)行遠(yuǎn)距離移動(dòng)，由無人機(jī)直接對桿塔進(jìn)行巡檢，可實(shí)現(xiàn)巡檢車與無人機(jī)的優(yōu)勢互補(bǔ)，極大程度提升了電力巡檢的自動(dòng)化程度和巡檢效率。電力企業(yè)日常運(yùn)營過程中，為了更好地管理巡檢作業(yè)，需要合理編排巡檢排班方案。車機(jī)協(xié)同巡檢排班方案涉及每個(gè)工作日巡檢車作業(yè)范圍、駐車點(diǎn)位置、行駛路徑等，科學(xué)的排班方案能夠顯著提升巡檢效率，最大程度發(fā)揮車機(jī)協(xié)同巡檢的優(yōu)勢。

目前，物流配送、農(nóng)業(yè)植保、電力巡檢等領(lǐng)域正試點(diǎn)推廣車輛與無人機(jī)協(xié)同作業(yè)模式，將車輛在地面遠(yuǎn)距離移動(dòng)性能和無人機(jī)在空中小范圍作業(yè)能力相結(jié)合，突破傳統(tǒng)單車或單機(jī)作業(yè)的局限性。特別地，在輸電線路巡檢領(lǐng)域，無人機(jī)目前已成為重要的巡檢方式之一，國內(nèi)外學(xué)者針對無人機(jī)電力巡檢作業(yè)過程中的任務(wù)分配[3]、路徑規(guī)劃[4]等問題展開了深入的研究。

長期以來，車輛路徑及其變種問題已被廣泛研究[5]并解決了眾多實(shí)際問題[6]。隨著車輛與無人機(jī)協(xié)同作業(yè)模式的推廣，車輛攜帶無人機(jī)的路徑問題已成為車輛路徑問題的熱點(diǎn)研究方向之一[7-8]。在旅行商模型的基礎(chǔ)上建立的TSP-D（Traveling Salesmen Problem with Drone）模型可專門用于研究車輛與無人機(jī)協(xié)同路徑規(guī)劃問題。該模型中，無人機(jī)作為車輛的“助手”，幫助車輛完成部分客戶點(diǎn)的配送服務(wù)，該模型需要在同一個(gè)優(yōu)化目標(biāo)的基礎(chǔ)上協(xié)同求解車輛的路徑和無人機(jī)的路徑。Roberti等人[9]針對多種TSP-D 的變體，提出了一種緊湊的混合整數(shù)線性模型，并使用動(dòng)態(tài)編程遞歸的方式求解“最后一英里”交付問題中車輛和無人機(jī)的路徑規(guī)劃。王菊[10]根據(jù)電力巡檢作業(yè)約束，基于TSP-D 模型建立了一種面向電力巡檢的TSP-D 模型（TTI-TSP-D），設(shè)計(jì)了一種奇偶分層編碼的遺傳算法對上述模型進(jìn)行求解，并通過實(shí)例分析驗(yàn)證了算法的正確性和有效性。此外，根據(jù)車輛與無人機(jī)在協(xié)同作業(yè)中攜帶的貨物類型、訪問的客戶點(diǎn)類型等不同，多種更具針對性的模型被提出。Murray 等人[11]針對兩種車輛與無人機(jī)協(xié)同作業(yè)方式，分別提出了FSTSP（Flying Sidekick Traveling Salesman Problem）模型和PDSTSP（Parallel Drone Scheduling Traveling Salesman Problem）模型，并設(shè)計(jì)了啟發(fā)式算法進(jìn)行求解。不同于上述模型中車輛和無人機(jī)均能完成部分交付任務(wù)的作業(yè)方式，實(shí)際中存在車輛僅用于運(yùn)載無人機(jī)和貨物，不直接訪問任一客戶點(diǎn)的模式。該模式下車輛和無人機(jī)的路徑問題可轉(zhuǎn)化成兩級配送問題，包含三個(gè)設(shè)施層次：一級配送中心、二級配送中心、客戶點(diǎn)。其中，車輛只訪問第一級配送網(wǎng)絡(luò)中的一級配送中心和二級配送中心，無人機(jī)在第二級配送網(wǎng)絡(luò)中從二級配送中心出發(fā)前往客戶點(diǎn)完成配送任務(wù)。楊溢樂[12]根據(jù)配送中心、駐車點(diǎn)、客戶點(diǎn)組成的兩級物流配送網(wǎng)絡(luò)，建立了兩級選址-路徑（2E-LRP）模型。針對該模型，采用先求解無人機(jī)路由層，再求解車輛路由層的方式，設(shè)計(jì)了模擬退火算法進(jìn)行求解，結(jié)合兩層的結(jié)果計(jì)算全局最優(yōu)解。

車機(jī)協(xié)同巡檢作業(yè)模式下，巡檢車只負(fù)責(zé)運(yùn)載無人機(jī)，不直接對輸電線路進(jìn)行巡檢。該問題若采用兩級配送模型進(jìn)行建模，能夠更加真實(shí)地描述車輛和無人機(jī)構(gòu)成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，也便于采用多階段求解算法對問題進(jìn)行簡化計(jì)算，降低求解復(fù)雜度和計(jì)算規(guī)模，但是該種求解方式僅能得到各階段局部最優(yōu)解的疊加。本文針對輸電線路車機(jī)協(xié)同巡檢作業(yè)模式下的車輛路徑問題，考慮到電力企業(yè)實(shí)際作業(yè)需求與約束，設(shè)計(jì)多層嵌套的啟發(fā)式算法綜合求解無人機(jī)任務(wù)分配、駐車點(diǎn)選址、巡檢車路徑規(guī)劃三個(gè)問題。本文所提方法能夠得到近似全局最優(yōu)的駐車點(diǎn)選址方案及各個(gè)工作日巡檢車的行駛路徑，為電力企業(yè)制定車機(jī)協(xié)同巡檢作業(yè)排班方案提供科學(xué)有效的決策方法。

1 車機(jī)協(xié)同巡檢下巡檢車路徑規(guī)劃模型

巡檢車路徑規(guī)劃問題實(shí)際上包括巡檢車駐車點(diǎn)選址、在每個(gè)駐車點(diǎn)處無人機(jī)的任務(wù)分配并基于分配方案優(yōu)化巡檢車訪問駐車點(diǎn)的順序。本研究的目的是在進(jìn)行大面積電力巡檢作業(yè)過程前，通過求解巡檢車最優(yōu)行駛路徑來編排合理的作業(yè)排班方案，從而提升車機(jī)協(xié)同巡檢作業(yè)效率。

1.1 問題描述

假設(shè)電力公司運(yùn)維區(qū)域內(nèi)有一個(gè)運(yùn)維站、n個(gè)備選駐車點(diǎn)、m個(gè)待巡檢的桿塔。現(xiàn)有一輛巡檢車，每個(gè)工作日從運(yùn)維站出發(fā)，訪問若干個(gè)駐車點(diǎn)后返回運(yùn)維站。巡檢車在每個(gè)駐車點(diǎn)處駐車一次，多架無人機(jī)由巡檢車起降平臺上起飛，前往各自目標(biāo)桿塔，完成相應(yīng)巡檢任務(wù)后降落至巡檢車起降平臺進(jìn)行補(bǔ)能或由巡檢車運(yùn)載前往下一作業(yè)區(qū)域。巡檢車每個(gè)工作日的總作業(yè)時(shí)間由行駛時(shí)間和在駐車點(diǎn)處等待無人機(jī)巡檢作業(yè)時(shí)間兩部分組成。

已知運(yùn)維站、備選駐車點(diǎn)、待巡檢桿塔的位置坐標(biāo)。根據(jù)作業(yè)約束及相關(guān)參數(shù)，以完成整個(gè)運(yùn)維區(qū)域巡檢任務(wù)的總作業(yè)時(shí)間最小為優(yōu)化目標(biāo)，預(yù)先編排巡檢排班計(jì)劃，包括從備選駐車點(diǎn)中選擇合適的駐車點(diǎn)集合，計(jì)算所需工作日數(shù)量并規(guī)劃巡檢車每個(gè)工作日訪問被選中的駐車點(diǎn)的路徑。

1.2 問題假設(shè)

考慮到模型建立及求解的復(fù)雜性，增加模型的適應(yīng)性及可理解性，同時(shí)貼近電力巡檢真實(shí)作業(yè)場景，本文對巡檢車路徑規(guī)劃模型做以下假設(shè)：

（1）訪問假設(shè)：由于運(yùn)維站與待巡桿塔間的距離遠(yuǎn)遠(yuǎn)超過無人機(jī)單次飛行的最遠(yuǎn)距離，所以無人機(jī)必須由巡檢車運(yùn)載至各駐車點(diǎn)后方可訪問待巡桿塔。由于道路限制，巡檢車只能訪問運(yùn)維站和駐車點(diǎn)，不能訪問待巡桿塔。

（2）運(yùn)維站起始假設(shè)：每個(gè)工作日巡檢車從運(yùn)維站出發(fā)，完成當(dāng)天全部巡檢任務(wù)后返回運(yùn)維站。

（3）路徑假設(shè)：由于本文研究的巡檢車路徑僅為巡檢車訪問駐車點(diǎn)的先后順序，不依據(jù)真實(shí)路網(wǎng)對巡檢車進(jìn)行實(shí)際路徑規(guī)劃，故假設(shè)巡檢車從上一個(gè)駐車點(diǎn)到下一個(gè)駐車點(diǎn)行駛距離為地理直線距離，由兩點(diǎn)間經(jīng)緯度坐標(biāo)直接計(jì)算可得。

（4）巡檢車假設(shè)：巡檢車的能源方式一般為燃油，可滿足單日作業(yè)需求，巡檢車數(shù)量為1輛。

（5）工作時(shí)間假設(shè)：由于車機(jī)協(xié)同巡檢作業(yè)模式仍需巡檢人員操作設(shè)備，故巡檢車單個(gè)工作日作業(yè)時(shí)長不超過電力企業(yè)設(shè)定的巡檢人員工作日最長作業(yè)時(shí)長。

（6）起降及充電假設(shè)：無人機(jī)更換電池及起降時(shí)間忽略不計(jì)；巡檢車上搭載多塊無人機(jī)電池，可滿足單個(gè)工作日無人機(jī)更換電池的需求。

（7）無人機(jī)任務(wù)假設(shè)：巡檢車上搭載的多架無人機(jī)是同質(zhì)的，且無人機(jī)往返駐車點(diǎn)與目標(biāo)桿塔間的飛行速度相同；無人機(jī)在待巡檢桿塔處的巡檢時(shí)間均相同；無人機(jī)單次起降只完成一基桿塔的巡檢任務(wù)；無人機(jī)必須同點(diǎn)起降；無人機(jī)在駐車點(diǎn)與待巡檢桿塔間直線飛行，忽略無人機(jī)起飛與降落階段的飛行距離。

1.3 數(shù)學(xué)模型

車機(jī)協(xié)同巡檢下巡檢車路徑規(guī)劃模型的標(biāo)號和參數(shù)說明如表1所示。

表1 模型標(biāo)號和參數(shù)說明

續(xù)表1

車機(jī)協(xié)同巡檢作業(yè)模式下巡檢車路徑規(guī)劃模型如下：

式（1）表示優(yōu)化目標(biāo)為最小化巡檢車總作業(yè)時(shí)間，即所有工作日作業(yè)時(shí)間之和；式（2）表示每個(gè)工作日巡檢車的作業(yè)時(shí)間由該工作日訪問的被選中駐車點(diǎn)的總巡檢時(shí)間與該工作日巡檢車總行駛時(shí)間兩部分組成，且每個(gè)工作日巡檢車的作業(yè)時(shí)長不超過電力企業(yè)設(shè)定的巡檢人員工作日最長作業(yè)時(shí)長；式（3）表示巡檢車每個(gè)工作日由運(yùn)維站駛出，并最終返回運(yùn)維站；式（4）和式（5）共同表示每個(gè)被選中的駐車點(diǎn)都只能被巡檢車在某個(gè)工作日訪問有且僅有一次，且訪問某一被選中的駐車點(diǎn)后必會(huì)離開該駐車點(diǎn)；式（6）表示所有待巡桿塔均被有且僅有一個(gè)被選中的駐車點(diǎn)服務(wù)；式（7）表示某工作日的任意一段車輛路徑的兩個(gè)端點(diǎn)，必被該工作日的巡檢車訪問；式（8）表示若某個(gè)駐車點(diǎn)在某個(gè)工作日被巡檢車訪問，則該駐車點(diǎn)必為被選中的駐車點(diǎn)；式（9）和式（10）為決策變量約束。

其中，由于巡檢車在每個(gè)駐車點(diǎn)處需放飛所攜帶的無人機(jī)完成巡檢任務(wù)，所有無人機(jī)同時(shí)作業(yè)，當(dāng)且僅當(dāng)所有無人機(jī)均完成各自巡檢任務(wù)并降落至巡檢車時(shí)，巡檢車才會(huì)運(yùn)載全部無人機(jī)前往下一駐車點(diǎn)，故式（11）表示巡檢車在每個(gè)被選中駐車點(diǎn)處的巡檢時(shí)間等于該駐車點(diǎn)耗時(shí)最長的無人機(jī)的任務(wù)時(shí)間；式（12）表示在每個(gè)被選中駐車點(diǎn)處，每架無人機(jī)的任務(wù)時(shí)間由往返駐車點(diǎn)與桿塔間的飛行時(shí)間和在桿塔處的巡檢時(shí)間兩部分組成；式（13）表示每基桿塔有且僅被一架無人機(jī)訪問一次，式（14）表示在每個(gè)被選中的駐車點(diǎn)處，所有無人機(jī)的總起飛次數(shù)等于該駐車點(diǎn)服務(wù)的桿塔總數(shù)，式（13）和式（14）共同表示單架無人機(jī)單次起飛只巡檢一基桿塔；式（15）和式（16）表示變量屬性，其中stk為0-1變量，zik為非負(fù)實(shí)數(shù)。

2 算法設(shè)計(jì)

車機(jī)協(xié)同巡檢作業(yè)模式下巡檢車路徑規(guī)劃問題是在備選駐車點(diǎn)中選擇合適的駐車點(diǎn)進(jìn)行巡檢作業(yè)，并根據(jù)已選擇駐車點(diǎn)的巡檢時(shí)間規(guī)劃巡檢車的行駛路徑。該問題實(shí)際上需要解決駐車點(diǎn)選址、各駐車點(diǎn)無人機(jī)任務(wù)分配、巡檢車路徑規(guī)劃三個(gè)問題。其中，駐車點(diǎn)選址是無人機(jī)任務(wù)分配和巡檢車路徑規(guī)劃的基礎(chǔ)，各駐車點(diǎn)無人機(jī)任務(wù)分配是為了計(jì)算駐車點(diǎn)處巡檢時(shí)間以提供車輛路徑時(shí)間參數(shù)。駐車點(diǎn)選址方案直接影響無人機(jī)任務(wù)序列和巡檢車行駛路徑，同時(shí)，決策者難以在備選駐車點(diǎn)集合中確定最優(yōu)的被選中駐車點(diǎn)的數(shù)量和組合。基于此，本文以駐車點(diǎn)選址算法為主程序，巡檢車路徑規(guī)劃算法為子程序，計(jì)算巡檢車最優(yōu)路徑的總作業(yè)時(shí)間并作為駐車點(diǎn)選址方案優(yōu)劣的評價(jià)標(biāo)準(zhǔn)。此外，無人機(jī)任務(wù)分配算法為巡檢車路徑規(guī)劃算法的子程序，用來計(jì)算各被選中駐車點(diǎn)的巡檢時(shí)間并傳入巡檢車路徑規(guī)劃算法。綜上，本文設(shè)計(jì)的多層嵌套的啟發(fā)式算法求解流程如圖1 所示。主程序每次迭代都會(huì)生成一個(gè)新的駐車點(diǎn)選址方案，并由無人機(jī)任務(wù)分配算法計(jì)算該選址方案下各駐車點(diǎn)的巡檢時(shí)間傳入巡檢車路徑規(guī)劃算法。巡檢車路徑規(guī)劃算法計(jì)算該選址方案下近似最優(yōu)的巡檢車行駛路徑并將該路徑的總作業(yè)時(shí)間傳入主程序，以使駐車點(diǎn)選址主程序朝著全局最優(yōu)解的方向演變。

圖1 巡檢車路徑規(guī)劃問題求解算法流程圖

2.1 駐車點(diǎn)選址算法

根據(jù)駐車點(diǎn)選址問題的特性，本文選擇了一種在水資源領(lǐng)域應(yīng)用較為成功的全局優(yōu)化算法——SCE-UA 算法作為主程序。SCE-UA 算法最早由Duan 等人[13]提出，相較于遺傳算法等傳統(tǒng)進(jìn)化算法，具有更強(qiáng)的魯棒性和更佳的收斂性。

本文使用SCE-UA 算法求解駐車點(diǎn)選址問題的流程如圖2所示，具體步驟如下所述：

圖2 SCE-UA算法流程圖

（1）初始化。設(shè)定初始化參數(shù)，包括參與進(jìn)化的復(fù)合形的個(gè)數(shù)v(v≥1)和每個(gè)復(fù)合形所包含的樣本數(shù)目m(m≥n+1)，其中n為參數(shù)個(gè)數(shù)，所以，樣本點(diǎn)數(shù)目s=v×m。

（2）產(chǎn)生樣本。隨機(jī)產(chǎn)生s個(gè)樣本點(diǎn)，并逐一判斷各樣本點(diǎn)是否可行，若不可行則重新產(chǎn)生樣本，直至產(chǎn)生s個(gè)可行的樣本點(diǎn)。其中，判斷樣本點(diǎn)是否可行的方式為判斷所有的桿塔是否都有至少一個(gè)小于作業(yè)半徑距離的被選中的駐車點(diǎn)為其服務(wù)。若所有桿塔都有對應(yīng)的小于作業(yè)半徑距離的駐車點(diǎn)為其服務(wù)，則樣本點(diǎn)可行，反之不可行。本算法的樣本點(diǎn)編碼方式為0-1 編碼，各樣本點(diǎn)的編碼長度等于備選駐車點(diǎn)的數(shù)目。編碼位為0 則表示該編碼位代表的駐車點(diǎn)沒有被選中，反之，為1 則表示被選中。以10 個(gè)備選駐車點(diǎn)為例，[0110111010]為一個(gè)樣本點(diǎn)編碼示例，該樣本點(diǎn)編碼長度為10，每一位編碼位都對應(yīng)一個(gè)駐車點(diǎn)。該樣本點(diǎn)編碼表示第2、3、5、6、7、9 號駐車點(diǎn)被選中，1、4、8、10號駐車點(diǎn)沒有被選中。

（3）排序標(biāo)號。計(jì)算每個(gè)樣本點(diǎn)的函數(shù)值，根據(jù)函數(shù)值的大小對樣本點(diǎn)進(jìn)行排序及標(biāo)號。其中，每個(gè)樣本點(diǎn)的函數(shù)值為在該樣本點(diǎn)代表的選址方案下，巡檢車的最優(yōu)總作業(yè)時(shí)間，由巡檢車路徑規(guī)劃算法計(jì)算得出。

（4）構(gòu)造復(fù)合形。將s個(gè)樣本點(diǎn)劃分為v個(gè)復(fù)合形，每個(gè)復(fù)合形包含m個(gè)樣本點(diǎn)。

（5）復(fù)合形進(jìn)化。復(fù)合形進(jìn)化是SCE-UA算法的核心部分，采用競爭的復(fù)合形進(jìn)化算法（CCE）對復(fù)合形進(jìn)行進(jìn)化操作。

2.2 駐車點(diǎn)處無人機(jī)任務(wù)分配算法

在每個(gè)駐車點(diǎn)處多架無人機(jī)同時(shí)作業(yè)，需要對巡檢車攜帶的多架無人機(jī)進(jìn)行任務(wù)分配，以使各無人機(jī)任務(wù)時(shí)間相近，避免出現(xiàn)多架無人機(jī)長時(shí)間等待某架無人機(jī)的情況，縮短各駐車點(diǎn)的巡檢時(shí)間。本文采用遺傳算法求解各駐車點(diǎn)處無人機(jī)的任務(wù)序列，并將耗時(shí)最長的無人機(jī)的任務(wù)時(shí)間作為該駐車點(diǎn)的巡檢時(shí)間傳入巡檢車路徑規(guī)劃子程序。

遺傳算法的染色體編碼方式采用實(shí)數(shù)編碼，每個(gè)染色體均為1 行m'列的數(shù)列，其中m'為該駐車點(diǎn)服務(wù)的桿塔總數(shù)。劃分每個(gè)駐車點(diǎn)服務(wù)的桿塔集合的方法為：每個(gè)待巡檢桿塔均由距離最近的已選中的駐車點(diǎn)服務(wù)。同時(shí)，通過設(shè)置中斷點(diǎn)的方式將完整染色體分為多個(gè)子段，中斷點(diǎn)的個(gè)數(shù)為k-1，其中，k為無人機(jī)架數(shù)，每個(gè)染色體子段對應(yīng)一架無人機(jī)的任務(wù)序列。初始染色體的生成方式為隨機(jī)生成1～m'的隨機(jī)數(shù)列。

種群中每個(gè)個(gè)體的適應(yīng)度函數(shù)值為該個(gè)體染色體對應(yīng)的無人機(jī)任務(wù)分配方案中耗時(shí)最長的無人機(jī)的任務(wù)時(shí)間。

選擇運(yùn)算采用輪盤賭法從種群中選擇最優(yōu)個(gè)體，個(gè)體選擇的概率與其適應(yīng)度函數(shù)值成反比。

交叉算子采用2-opt 方法，變異算子采用隨機(jī)選擇兩對不相鄰基因位互換基因值的方式。

2.3 巡檢車路徑規(guī)劃算法

巡檢車路徑規(guī)劃算法是根據(jù)任意一個(gè)可行的選址方案及該選址方案下每個(gè)被選中的駐車點(diǎn)的巡檢時(shí)間，求解巡檢車從運(yùn)維站出發(fā)訪問所有被選中的駐車點(diǎn)的最優(yōu)路徑，即算法的輸入為選址方案及每個(gè)被選中的駐車點(diǎn)的巡檢時(shí)間，輸出為巡檢車的最優(yōu)路徑及總作業(yè)時(shí)間。進(jìn)一步地，由于巡檢車需要滿足工作時(shí)間約束，在單個(gè)工作日無法完成全部巡檢任務(wù)的情況下，需要將巡檢任務(wù)劃分為多個(gè)工作日的巡檢任務(wù)，并規(guī)劃每個(gè)工作日巡檢車的行駛路徑。基于以上分析，本文采用免疫算法進(jìn)行巡檢車路徑規(guī)劃。

免疫算法的抗原為巡檢車路徑的總作業(yè)時(shí)間，包括巡檢車的行駛時(shí)間及所有被選中的駐車點(diǎn)的巡檢時(shí)間兩部分。

免疫算法抗體編碼方式為實(shí)數(shù)編碼。根據(jù)駐車點(diǎn)選址主程序中傳入的駐車點(diǎn)選址方案，確定被選中的駐車點(diǎn)的集合。若被選中的駐車點(diǎn)的個(gè)數(shù)為p，則隨機(jī)生成多個(gè)1 行p列的數(shù)列組成初始抗體群。其中，每個(gè)抗體都代表一條巡檢車訪問駐車點(diǎn)的序列，每個(gè)初始抗體中的各元素均為在該選址方案下某一個(gè)駐車點(diǎn)的編號。

進(jìn)一步地，由于每個(gè)抗體表示的巡檢車的路徑為多個(gè)工作日的路徑，本算法采用從抗體第一位開始依次添加路徑點(diǎn)并判斷作業(yè)時(shí)長的方式對路徑進(jìn)行劃分。若添加路徑點(diǎn)前該路徑滿足單個(gè)工作日最長作業(yè)時(shí)長約束，但添加后不滿足該約束，則添加前的路徑作為一個(gè)工作日的路徑，并從添加的這一位開始，繼續(xù)進(jìn)行上述操作，直到所有位都被分配到某一個(gè)工作日的路徑中為止。

本算法中對抗體群中的個(gè)體評價(jià)標(biāo)準(zhǔn)采用的是個(gè)體的期望繁殖率。生成父代抗體群的方式為在初始抗體群中按期望繁殖率降序?qū)贵w進(jìn)行排序，取與初始抗體群規(guī)模相同大小的前N個(gè)抗體作為父代抗體群。

對父代抗體群執(zhí)行免疫操作，包括選擇、交叉、變異等，由父代抗體群生成子代抗體群，再將記憶庫中的個(gè)體取出，共同組成新抗體群。其中，本算法的個(gè)體選擇方法為輪盤賭法，個(gè)體的期望繁殖率直接決定其被選擇的概率。本算法的交叉操作采用2-opt 的方法，從父代抗體生成子代抗體。變異操作采用隨機(jī)選擇變異位進(jìn)行變異的方式。

3 算例分析

為了測試本文所提算法的性能，本研究采用真實(shí)設(shè)備數(shù)據(jù)及桿塔數(shù)據(jù)進(jìn)行實(shí)例計(jì)算及分析。本節(jié)對比了Gurobi 求解器和本文提出的多層嵌套的啟發(fā)式算法對小規(guī)模算例的計(jì)算效果，并利用本文所提算法進(jìn)行了大規(guī)模算例的求解，可作為電力企業(yè)制定排班方案的參考示例。

3.1 算法對比分析

為了測試本文提出的多層嵌套的啟發(fā)式算法的求解效果，針對小規(guī)模算例分別采用Gurobi求解器和本文所提算法進(jìn)行求解。其中，由于本文所建立的模型中存在多處變量相乘，導(dǎo)致Gurobi求解器無法求解，故本研究在求解器中采用窮舉法進(jìn)行求解。具體而言，對于hi每一種可能的取值，都分別求解該取值下無人機(jī)的任務(wù)分配結(jié)果及巡檢車路徑規(guī)劃結(jié)果。最終，求解器輸出最優(yōu)的hi值及其對應(yīng)的排班方案作為該算例的精確最優(yōu)解。對于每組小規(guī)模算例，設(shè)定Gurobi求解器求解限制時(shí)間為3 600 s，本文所提算法運(yùn)行10 次取最好結(jié)果。本文實(shí)驗(yàn)均在同一實(shí)驗(yàn)環(huán)境下進(jìn)行，運(yùn)行環(huán)境為CPU(Intel(R)Core(TM)i7-6700)/RAM(16GB)的個(gè)人計(jì)算機(jī)，編程語言為MATLAB R2020a。

根據(jù)實(shí)際工程數(shù)據(jù)及大量實(shí)驗(yàn)，確定相關(guān)實(shí)驗(yàn)參數(shù)如下：

（1）電力巡檢相關(guān)作業(yè)參數(shù)：巡檢車數(shù)量為1輛，平均行駛速度為40 km/h，單次駐車作業(yè)半徑為2.5 km，無人機(jī)往返電力桿塔與駐車點(diǎn)間的平均飛行速度為60 km/h，每個(gè)電力桿塔處的巡檢時(shí)間為20 min。

（2）SCE-UA算法相關(guān)參數(shù)：復(fù)合形個(gè)數(shù)為20，每個(gè)復(fù)合形的樣本個(gè)數(shù)為10，最大迭代次數(shù)為100，子復(fù)合形中點(diǎn)的選取個(gè)數(shù)為10，產(chǎn)生子代個(gè)數(shù)為1。

（3）遺傳算法相關(guān)參數(shù)：種群規(guī)模為24，最大迭代次數(shù)為100，交叉概率為0.9，變異概率為0.01。

（4）免疫算法相關(guān)參數(shù)：種群規(guī)模為60，最大迭代次數(shù)為100，記憶庫容量為10，交叉概率為0.5，變異概率為0.1，多樣性評價(jià)參數(shù)為0.9，相似度閾值為0.7。

Gurobi 求解器和本文所提算法求解效果比較如表2所示。其中，備選駐車點(diǎn)數(shù)為n，待巡桿塔總數(shù)為m，無人機(jī)架數(shù)為k，選中的駐車點(diǎn)個(gè)數(shù)為SelectP，總巡檢時(shí)間為Ztotalmin，計(jì)算時(shí)間為Times，Gap 欄為本文所提算法的最好結(jié)果與Gurobi 求解結(jié)果的差值。特別地，由于啟發(fā)式算法求解小規(guī)模算例較易找到近似最優(yōu)解（或精確最優(yōu)解），若SCE-UA算法終止條件為達(dá)到最大迭代次數(shù)，則會(huì)造成算法無意義迭代。故求解小規(guī)模算例時(shí)，SCE-UA算法的終止條件為達(dá)到最大迭代次數(shù)和當(dāng)前解連續(xù)沒有得到改善的迭代次數(shù)達(dá)到10次。

表2 小規(guī)模算例計(jì)算結(jié)果比較

由于算例問題的難求解性，Gurobi 求解器在求解5 個(gè)備選駐車點(diǎn)、25 基待巡檢桿塔、3 架無人機(jī)的算例和6 個(gè)備選駐車點(diǎn)、30 基待巡檢桿塔、3架無人機(jī)的算例時(shí)，達(dá)到設(shè)定求解時(shí)間時(shí)未完成全部hi取值可能性下排班方案的求解。在其余算例中，本文所提算法求得的最優(yōu)解均與Gurobi 求解器求得的精確解相等，并且隨著算例規(guī)模的增加，多層嵌套的啟發(fā)式算法求解時(shí)間明顯優(yōu)于Gurobi求解器，表現(xiàn)出了較為良好的求解效果。

3.2 關(guān)鍵作業(yè)參數(shù)分析

小規(guī)模算例對比分析實(shí)驗(yàn)中所取電力巡檢相關(guān)作業(yè)參數(shù)為某電力公司實(shí)際工程數(shù)據(jù)，為了進(jìn)一步為電力公司實(shí)際巡檢作業(yè)提供參考，本節(jié)探究了作業(yè)參數(shù)對車機(jī)協(xié)同巡檢車輛路徑問題的模型及求解算法的影響。本研究的主要作業(yè)參數(shù)為：巡檢車數(shù)量Vehicle，平均行駛速度V，單次駐車作業(yè)半徑R，搭載的無人機(jī)架數(shù)k，無人機(jī)往返電力桿塔與駐車點(diǎn)間的平均飛行速度Vk，每基電力桿塔處的巡檢時(shí)間C。關(guān)鍵作業(yè)參數(shù)分析實(shí)驗(yàn)采用6個(gè)備選駐車點(diǎn)、30基待巡桿塔的小規(guī)模算例進(jìn)行多次對照實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3 所示。其中，總巡檢時(shí)間和平均求解時(shí)間均為五次相同實(shí)驗(yàn)的平均值，啟發(fā)式算法所取參數(shù)同3.1 節(jié)小規(guī)模算例對比實(shí)驗(yàn)。特別地，由于本文建立的車機(jī)協(xié)同巡檢路徑規(guī)劃模型只考慮單個(gè)巡檢車作業(yè)的場景，表中多個(gè)巡檢車算例中的總巡檢時(shí)間Ztotal為多個(gè)巡檢車作業(yè)時(shí)間之和。

由表3可以看出，上述關(guān)鍵作業(yè)參數(shù)對于總巡檢時(shí)間和算法求解時(shí)間的影響不盡相同。從巡檢時(shí)間角度來說，若總巡檢時(shí)間不超過單個(gè)工作日最長作業(yè)時(shí)長，由于Ztotal為多個(gè)巡檢車作業(yè)時(shí)間之和，巡檢車數(shù)量的增加會(huì)導(dǎo)致每個(gè)巡檢車都必須從運(yùn)維站出發(fā)前往各自目標(biāo)駐車點(diǎn)并返回運(yùn)維站，增加了所有巡檢車總行駛距離從而導(dǎo)致總巡檢時(shí)間增加。其次，若總巡檢時(shí)間超過單個(gè)工作日最長作業(yè)時(shí)長，由于各巡檢車獨(dú)立作業(yè)，則多個(gè)巡檢車執(zhí)行巡檢任務(wù)等同于單個(gè)巡檢車執(zhí)行多個(gè)工作日巡檢任務(wù)，所有巡檢車的總巡檢時(shí)間不會(huì)發(fā)生變化。此外，巡檢車行駛速度、巡檢車攜帶的無人機(jī)架數(shù)、無人機(jī)平均飛行速度的增加能夠降低總巡檢時(shí)間，而每基電力桿塔處的巡檢時(shí)間與總巡檢時(shí)間成正相關(guān)。從計(jì)算時(shí)間角度來說，巡檢車數(shù)量的增加會(huì)導(dǎo)致巡檢車路徑規(guī)劃子算法的復(fù)雜性增加，從而增加了總計(jì)算時(shí)間。特別地，巡檢車單次駐車作業(yè)半徑的增加會(huì)降低計(jì)算時(shí)間，這是由于較為狹窄的作業(yè)半徑區(qū)間會(huì)導(dǎo)致駐車點(diǎn)選址算法產(chǎn)生不可行解的可能性增加，算法需要重新生成可行解以替代不可行解。

表3 關(guān)鍵作業(yè)參數(shù)分析結(jié)果

實(shí)驗(yàn)表明，電力企業(yè)在實(shí)際應(yīng)用過程中，可通過硬件更新等方式提升巡檢車行駛速度、無人機(jī)平均飛行速度，通過優(yōu)化無人機(jī)拍攝步驟等方式降低無人機(jī)在桿塔處巡檢時(shí)間，從而在不增加設(shè)備數(shù)量的前提下縮短總巡檢時(shí)間以提升巡檢效率。

3.3 大規(guī)模算例實(shí)驗(yàn)

實(shí)際工程應(yīng)用中，電力公司運(yùn)維區(qū)域面積較大，需要巡檢的桿塔數(shù)量眾多。本節(jié)使用所提的多層嵌套的啟發(fā)式算法求解大規(guī)模車機(jī)協(xié)同巡檢車輛路徑問題，可為電力企業(yè)提供參考。

某電力公司運(yùn)維區(qū)域長22.15 km，寬16.10 km，共有205基待巡檢桿塔。出于桿塔實(shí)際坐標(biāo)數(shù)據(jù)保密等原因，算例中桿塔坐標(biāo)均在真實(shí)桿塔坐標(biāo)數(shù)據(jù)的基礎(chǔ)上統(tǒng)一添加了一個(gè)隨機(jī)數(shù)。該操作既能保證處理后的桿塔數(shù)據(jù)不失輸電線路桿塔分布規(guī)律，又能擴(kuò)大桿塔數(shù)據(jù)的隨機(jī)程度，以驗(yàn)證算法的適用性。該運(yùn)維區(qū)域內(nèi)共有25個(gè)備選駐車點(diǎn)，備選駐車點(diǎn)和運(yùn)維站的位置坐標(biāo)已知。假設(shè)電力企業(yè)設(shè)定的巡檢人員工作日最長作業(yè)時(shí)長為8小時(shí)，本實(shí)例以通過車機(jī)協(xié)同巡檢作業(yè)方式完成所有巡檢任務(wù)的總作業(yè)時(shí)間最小為優(yōu)化目標(biāo)，使用本文所提算法求解巡檢車每個(gè)工作日的最優(yōu)行駛路徑。算例中待巡檢桿塔、運(yùn)維站及備選駐車點(diǎn)位置分布如圖3所示，圖中橫坐標(biāo)為經(jīng)度，縱坐標(biāo)為緯度。

圖3 算例中待巡檢桿塔、運(yùn)維站及備選駐車點(diǎn)位置分布

本實(shí)驗(yàn)參考文獻(xiàn)[14]中公開的智能巡檢車攜帶的無人機(jī)架數(shù)，設(shè)定巡檢車搭載4架無人機(jī)。本實(shí)驗(yàn)中其他相關(guān)實(shí)驗(yàn)參數(shù)設(shè)置、實(shí)驗(yàn)環(huán)境同3.1 節(jié)中小規(guī)模算例求解對比實(shí)驗(yàn)。

將所有坐標(biāo)數(shù)據(jù)、相關(guān)參數(shù)輸入SCE-UA算法主程序中，經(jīng)過100 次迭代后，駐車點(diǎn)選址算法的收斂曲線如圖4 所示。其中，SCE-UA 算法的函數(shù)值即為巡檢車的總作業(yè)時(shí)間，該算法計(jì)算出的最優(yōu)巡檢車總作業(yè)時(shí)間為1 357.46 min。

圖4 SCE-UA算法收斂曲線

SCE-UA 算法輸出的最優(yōu)樣本點(diǎn)所代表的駐車點(diǎn)選址方案如圖5所示。

圖5 最優(yōu)樣本點(diǎn)代表的駐車點(diǎn)選址方案

最優(yōu)樣本點(diǎn)的編碼為：[1111111010010000101101111]，對應(yīng)的被選中的駐車點(diǎn)集合為：[1 2 3 4 5 6 7 9 12 17 19 20 22 23 24 25]，共有16 個(gè)備選駐車點(diǎn)被選中。

其中，算法得出的最優(yōu)選址方案對應(yīng)的每個(gè)被選中的駐車點(diǎn)的巡檢時(shí)間由駐車點(diǎn)處無人機(jī)任務(wù)分配算法計(jì)算可得，具體如表4所示。

表4 被選中的駐車點(diǎn)的近似最優(yōu)巡檢時(shí)間

近似最優(yōu)駐車點(diǎn)選址方案對應(yīng)的算法計(jì)算出的巡檢車最優(yōu)行駛路徑如圖6 所示。巡檢車完成整片運(yùn)維區(qū)域需要三個(gè)工作日，每個(gè)工作日的行駛路徑分別如下：

圖6 算法計(jì)算得出的巡檢車最優(yōu)行駛路徑

工作日1：運(yùn)維站—備選駐車點(diǎn)4—備選駐車點(diǎn)19—備選駐車點(diǎn)22—備選駐車點(diǎn)20—備選駐車點(diǎn)9—備選駐車點(diǎn)12—備選駐車點(diǎn)5—運(yùn)維站；

工作日2：運(yùn)維站—備選駐車點(diǎn)2—備選駐車點(diǎn)1—備選駐車點(diǎn)7—備選駐車點(diǎn)24—備選駐車點(diǎn)25—備選駐車點(diǎn)6—運(yùn)維站；

工作日3：運(yùn)維站—備選駐車點(diǎn)3—備選駐車點(diǎn)17—備選駐車點(diǎn)23—運(yùn)維站。

每個(gè)工作日巡檢車的作業(yè)時(shí)間如下：工作日1：459.39 min；工作日2：448.71 min；工作日3：449.35min。

綜上所述，在已知待巡桿塔、運(yùn)維站、備選駐車點(diǎn)位置坐標(biāo)的情況下，本文提出的巡檢車路徑規(guī)劃方法能夠綜合求解駐車點(diǎn)選址、無人機(jī)任務(wù)分配、巡檢車路徑規(guī)劃三個(gè)子問題。使用本文所提算法可以在巡檢車總作業(yè)時(shí)間最小的優(yōu)化目標(biāo)下，求得近似最優(yōu)的駐車點(diǎn)選址方案及該方案下巡檢車每個(gè)工作日的行駛路徑及作業(yè)時(shí)間。該方法能夠?yàn)殡娏ζ髽I(yè)進(jìn)行大面積巡檢時(shí)提供完整的巡檢車路徑規(guī)劃決策方案，實(shí)用價(jià)值較高。

4 結(jié)束語

本文以車機(jī)協(xié)同巡檢作業(yè)方式下巡檢車的路徑規(guī)劃問題為研究對象，以巡檢車總作業(yè)時(shí)間最小為優(yōu)化目標(biāo)建立了巡檢車路徑規(guī)劃模型。考慮到車機(jī)協(xié)同巡檢作業(yè)規(guī)模，設(shè)計(jì)了多層嵌套的啟發(fā)式算法。該算法可求解大面積巡檢區(qū)域下巡檢車的近似最優(yōu)路徑，能夠?yàn)殡娏ζ髽I(yè)制定巡檢作業(yè)排班計(jì)劃提供指導(dǎo)。實(shí)際應(yīng)用中，電力企業(yè)可根據(jù)算法求解出的訪問駐車點(diǎn)的順序，結(jié)合真實(shí)路網(wǎng)環(huán)境，對巡檢車的行駛路徑進(jìn)一步進(jìn)行優(yōu)化，以便于對巡檢車進(jìn)行跟蹤與管理。