基于NP問題的機巡計劃編排研究

廖建東，陳 浩，柳亦鋼

（廣東電網(wǎng)有限責(zé)任公司機巡管理中心，廣東 廣州510000）

隨著國民經(jīng)濟的快速發(fā)展，生活與工業(yè)用電量與日俱增，使得我國用電需求不斷增加，電網(wǎng)的規(guī)模也隨之越來越大。與此同時，電力巡檢工作也遇到了前所未有的挑戰(zhàn)。為了確保輸電線路安全可靠，需定期對輸電線路進(jìn)行巡檢。然而，輸電線路分布區(qū)域廣，監(jiān)測成本高，現(xiàn)階段狀態(tài)評估技術(shù)在分析準(zhǔn)確性和實施經(jīng)濟性上還有所欠缺，故目前大部分電網(wǎng)公司仍采取“人巡+機巡”協(xié)同的定期巡檢的方式來維護(hù)輸電線路[1]。但定期巡檢存在人工成本高、效率低、工作計劃安排不合理等現(xiàn)象；現(xiàn)有的機巡計劃編排方式已逐漸無法滿足未來的機巡作業(yè)管理需求。所以迫切需要構(gòu)建一整套機巡計劃智能編排方案，實現(xiàn)對機巡計劃的高效編排。目前，中國南方電網(wǎng)公司已經(jīng)建立了完善的機巡作業(yè)中心，實現(xiàn)了定期機巡計劃的智能編排，極大縮減了編排的時間。

1 機巡作業(yè)調(diào)度方案設(shè)計流程

智能調(diào)度方案可以有效覆蓋各條輸電線路，且在規(guī)定期限內(nèi)完成巡檢工作。智能調(diào)度算法需要根據(jù)電網(wǎng)運維管控流程要求進(jìn)行設(shè)計優(yōu)化。例如，廣東電網(wǎng)有限責(zé)任公司2019年版《輸電線路運維策略及管控機制實施細(xì)則》[2]，輸電線路運維管控工作流程包括：

（1）開展輸電線路狀態(tài)評價，確定健康度；

（2）開展輸電線路重要性評估，確定重要度；

（3）根據(jù)輸電線路風(fēng)險矩陣，確定管控級別；

（4）制定輸電線路運維管控策略，明確管控要求；

（5）制定工作計劃，開展輸電線路運維。

依據(jù)該工作流程，按照年度機巡計劃設(shè)計調(diào)度算法，年度機巡計劃調(diào)度方案設(shè)計流程如圖1所示。考慮到機巡作業(yè)中心需要為廣東省14個地市制定年度機巡計劃，涉及的輸電線路數(shù)量龐大、地域分布廣，年度機巡計劃本身也是多目標(biāo)優(yōu)化問題，屬于“NP問題”[3]，求解過程復(fù)雜，算法時間復(fù)雜度高，直接對年度機巡計劃進(jìn)行求解可能會導(dǎo)致優(yōu)化算法實時性較差等問題。鑒于目前南方電網(wǎng)實施的是集約化巡視方式（地市的機巡任務(wù)會被機巡隊集中在一段時間內(nèi)完成），因此可以將年度機巡計劃自下而上分為兩個層面來求解：

圖1 年度機巡計劃調(diào)度算法設(shè)計流程

（1）地市層面。機巡作業(yè)中心得到地市上報的機巡任務(wù)需求，即待巡線路的巡視方式、各桿塔位置、巡視路段長度等信息后，先對地市內(nèi)的機巡任務(wù)進(jìn)行規(guī)劃，得到一個機巡隊情況下，集約化執(zhí)行對應(yīng)機巡任務(wù)所需要的時間，作為省級層面優(yōu)化的輸入數(shù)據(jù)。

（2）省級層面。通過“地市層面”的規(guī)劃，機巡作業(yè)中心可以將原來14個地市的分散機巡任務(wù)需求看作“14個大的機巡任務(wù)”，只需要考慮以合理的間隔和方式，將“14個大的機巡任務(wù)”優(yōu)化到下一年度中不同的季度和月份中去，避免陷入到地市詳細(xì)機巡任務(wù)的細(xì)節(jié)里面。

2 機巡作業(yè)調(diào)度算法設(shè)計內(nèi)容

在一條輸電線路中，由于空域環(huán)境和地理環(huán)境的限制，可能需要進(jìn)行分段處理，比如在具備直升機飛行的路段，采用直升機精細(xì)化巡視和直升機通道巡視；在不具備直升機飛行但可以固定翼飛行的路段，采用固定翼通道巡視；在直升機與固定翼均不可用的路段，采用人工巡檢為主，多旋翼無人機輔助，在特殊情況路段，可視情況放棄巡檢。

為此，機巡作業(yè)中心在收到各地市供電局上報的“待巡線路需求模型”后，結(jié)合機巡作業(yè)資源能力模型，建立模型合理的安排機巡的任務(wù)執(zhí)行序列，最大程度發(fā)揮出機巡資源的能力，規(guī)劃出實現(xiàn)各地市年度巡視任務(wù)所需的巡視任務(wù)執(zhí)行時間，包括直升機精細(xì)化巡視時間、固定翼通道巡視時間和直升機通道巡視時間，并將該規(guī)劃結(jié)果保存到機巡調(diào)度優(yōu)化規(guī)則模型，作為機巡作業(yè)中心制定年度計劃的輸入數(shù)據(jù)之一。

地市年度巡檢時間規(guī)劃問題是指利用現(xiàn)有的不同類型的機巡資源（無人機和直升機），對若干空間分散的輸電線路布置區(qū)域，按照輸電線路管控級別等要求確定日常巡維的調(diào)度計劃，即在滿足不同巡視任務(wù)需求、作業(yè)區(qū)域地理條件、任務(wù)時間窗、機巡作業(yè)種類、數(shù)量和性能等約束下，為機巡資源分配巡視任務(wù)和地面調(diào)度方案。如圖2所示，機巡資源從基地出發(fā)，按照調(diào)度方案的任務(wù)執(zhí)行流程，經(jīng)地面調(diào)度抵達(dá)任務(wù)的起降場，依次完成各自的任務(wù)。每個電網(wǎng)巡視任務(wù)代表一個作業(yè)區(qū)域，包含不同等級的桿塔點和輸電線通道。

圖2 機巡作業(yè)調(diào)度示意圖

地市年度巡檢時間規(guī)劃問題可歸納為有容量約束的路徑規(guī)劃問題，即機巡作業(yè)基地為各輸電線路提供巡視作業(yè)服務(wù)，機巡作業(yè)基地的每種作業(yè)資源（直升機或無人機）都有巡視作業(yè)時間長度的限制，通過安排科學(xué)合理的作業(yè)資源巡視路線，使得一定數(shù)量的作業(yè)資源從機巡作業(yè)基地出發(fā)，完成巡視任務(wù)后返回機巡作業(yè)基地。

2.1 場景應(yīng)用假設(shè)

結(jié)合機巡任務(wù)需求以及復(fù)雜的作業(yè)環(huán)境，調(diào)度算法研究基于以下假設(shè)：

（1）在作業(yè)過程中，作業(yè)質(zhì)量不隨調(diào)度方案發(fā)生變化。

（2）一個機隊擁有一種機巡作業(yè)資源，比如直升機或固定翼無人機，若干工作人員，由車輛運載轉(zhuǎn)移。

（3）機巡資源作業(yè)效率恒定且作業(yè)過程中無故障。

（4）機隊每日可工作時長固定，一周為五個工作日，可開展機巡作業(yè)和空域管轄地面轉(zhuǎn)移，其余時間為非作業(yè)時間。

（5）一個機隊可以為多個輸電線路提供巡視作業(yè)服務(wù)，但是每個待巡輸電線路只能由單個機隊完成巡視任務(wù)。

（6）只有一個機巡作業(yè)基地，且所有的作業(yè)資源均以機巡作業(yè)基地為起點，分配的所有巡視作業(yè)資源完成后返回機巡作業(yè)基地。

（7）各待巡輸電線路附近具備提供機巡作業(yè)資源的后勤保障能力，包括直升機加油、無人機充電，提供巡視工作人員住宿等，規(guī)劃中認(rèn)為作業(yè)資源具有持續(xù)作業(yè)能力，不考慮作業(yè)資源維護(hù)或者故障、惡劣天氣、道路擁堵等因素的影響。

（8）作業(yè)資源的類型單一。

（9）機巡作業(yè)基地和待巡輸電線路的位置坐標(biāo)已知。

（10）所有距離采用歐幾里得距離表示。

2.2 方案模型設(shè)計

為了更加清晰準(zhǔn)確的描述模型，對模型中使用的符號進(jìn)行如下定義：

（1）R表示機巡資源集合，R={R1，R2，…，Rr}表示直升機資源或固定翼資源，注意模型中僅具有單一機巡作業(yè)資源。

（2）r表示機巡資源的數(shù)量，對機巡資源的描述主要包括位置、所攜帶傳感器、直升機性能（巡視航程，使用后維護(hù)時間，巡視速度等）或固定翼無人機性能（巡視航程，使用后維護(hù)時間，巡視速度等）等，具體數(shù)據(jù)來自機巡作業(yè)資源能力。

（3）M為巡視任務(wù)集合，M={M1，M2，…，Mm}，m為該地區(qū)巡視任務(wù)的個數(shù)，對巡視任務(wù)的初始描述主要包括任務(wù)數(shù)據(jù)需求（精細(xì)化巡視、通道巡視）、巡視長度、輸電線路位置和任務(wù)優(yōu)先級等，具體數(shù)據(jù)來自待巡線路需求模型。

（4）機巡資源的巡視時間記為T={T1，T2，…，Tr}。

（5）機巡資源Rj執(zhí)行巡視任務(wù)Mi預(yù)計所需時間為ti，j，假設(shè)機巡作業(yè)資源巡視速度固定，通過巡視方式以及巡視距離，即可確定巡視時間。

（6）機巡資源集合R的開始任務(wù)位置集合PR={Pj，j=1，2，…，r}，應(yīng)均位于機巡作業(yè)基地。

（7）巡視任務(wù)集合M的完成任務(wù)位置合集PM={Pi，i=1，2，…，m}。

（8）任意兩點之間的地面調(diào)度距離為dPi，Pj，地面轉(zhuǎn)移時間記為tPi，Pj，其中Pi和Pj∈（PR∪PM）。若兩個機巡任務(wù)之間無需通過地面，直接由固定翼無人機或者直升機飛行過去，則dPi，Pj表示機巡任務(wù)Pi和Pj之間的空中距離，tP，Pji表示直接通過空中轉(zhuǎn)移的時間。

（9）機巡資源Rk從待巡線路Pi轉(zhuǎn)移到Pj的狀態(tài)變量xi,j,k，

（10）任務(wù)Mi執(zhí)行的決策變量為yi,k，

（11）作業(yè)成本C ost={costw，costt}，其中costw為機巡隊單位距離的使用成本，包含機具折舊、人工費用和動力費用等；costt為機巡隊單位距離的轉(zhuǎn)移成本，主要為車輛燃油消耗和駕駛員人工費用。

（12）機巡作業(yè)資源作業(yè)時長Q表示每個機巡作業(yè)資源在該次分配中應(yīng)該承擔(dān)的作業(yè)時長上限，Q估算如下：

其中，r表示各機巡作業(yè)資源應(yīng)該盡可能平均的執(zhí)行巡視任務(wù)。

基于以上的假設(shè)條件和參數(shù)定義，建立地市年度巡檢時間規(guī)劃問題的數(shù)學(xué)模型如下：

其中式（4）為目標(biāo)函數(shù)，前二項為作業(yè)成本，最后一項為懲罰函數(shù)Pon，表征作業(yè)資源之間作業(yè)任務(wù)分配的不合理些，wi為權(quán)重；式（5）保證每次配送任務(wù)都以配送中心為起點和終點；式（6）保證每個待巡線路有且僅能被服務(wù)一次；式（7）保證每個機巡作業(yè)資源的巡視時長總和小于作業(yè)資源的的額定巡視時長；式（8）表示為待巡線路服務(wù)的集訓(xùn)數(shù)量總數(shù)小于機巡作業(yè)基地所擁有的作業(yè)資源總數(shù)；式（9）表示決策變量x、y，是0-1變量。

3 結(jié)束語

由于機巡作業(yè)變量的離散性，機巡計劃調(diào)度問題是為實現(xiàn)各地市輸電線路巡查需求而對共同使用的作業(yè)資源實行時間分配，是一個典型的組合優(yōu)化問題。通過利用精確算法求解NP難問題，即使能得到最優(yōu)解，也存在所需計算時間過長，難以直接應(yīng)用。因此，可以采用近似算法，通過輸入上述方案模型所需參數(shù)進(jìn)行求解計算。基于智能優(yōu)化的近似算法是基于一定的優(yōu)化搜索機制，并具有全局優(yōu)化性能的一類算法[4]。常見的算法有：模擬退火算法（SA）、遺傳算法（GA）、蟻群算法（ACO）、路徑重連算法（PR）、迭代局部收縮算法（ILS）、禁忌搜索算法（TS）、分散搜索算法（SS）、粒子群算法（PSO）等等。作為一種通用算法框架，智能化算法主要是針對具體問題對框架結(jié)構(gòu)進(jìn)行局部修改，具有較好的實踐通用性，且能在較快地處理大規(guī)模數(shù)據(jù)的同時得到可接受的解，在工業(yè)實際問題組合優(yōu)化求解方面具有一定優(yōu)勢。