趙 蒙 ,張 博 ,胡祥培 ,黃敏芳

(1.大連理工大學(xué) 經(jīng)濟(jì)管理學(xué)院,遼寧 大連 116024;2.華北電力大學(xué) 經(jīng)濟(jì)與管理學(xué)院,北京 102206)

隨著我國(guó)用電需求和電網(wǎng)規(guī)模的快速增長(zhǎng),電力巡檢的工作量也大幅增加[1]。輸電設(shè)施長(zhǎng)期暴露在野外環(huán)境中,極易磨損老化,必須定期巡查、檢修以確保供電正常。無(wú)人機(jī)技術(shù)的成熟和發(fā)展為電力巡檢提供了相比人工作業(yè)更加安全、經(jīng)濟(jì)和高效的解決辦法。一方面,無(wú)人機(jī)電力巡檢操作靈活、部署方便,檢測(cè)精度高,能夠消除人工巡檢盲區(qū)[2];但另一方面,電力巡檢無(wú)人機(jī)的續(xù)航能力有限,通常需要保障車(chē)為無(wú)人機(jī)提供放飛回收、轉(zhuǎn)場(chǎng)載運(yùn)、電池更換和維護(hù)保養(yǎng)等服務(wù)保障,這就要求無(wú)人機(jī)和保障車(chē)的作業(yè)計(jì)劃充分協(xié)調(diào)以保證電力巡檢任務(wù)的順利執(zhí)行。

目前較為常用的一輛保障車(chē)固定搭配一架無(wú)人機(jī)的“一對(duì)一”模式雖然操作簡(jiǎn)單,但巡檢任務(wù)范圍較大時(shí)該模式的整體運(yùn)行效率低,對(duì)保障車(chē)的利用率不足,經(jīng)濟(jì)性和時(shí)效性較差[3-5]。實(shí)際上,車(chē)載無(wú)人機(jī)電力巡檢系統(tǒng)(Vehicle-mounted UAV Transmission Inspection System,VUTIS)可由中控平臺(tái)通過(guò)移動(dòng)互聯(lián)網(wǎng)技術(shù)同時(shí)遠(yuǎn)程控制多架無(wú)人機(jī),按照既定的任務(wù)方案協(xié)同合作,在更短的時(shí)間內(nèi)完成電力巡檢任務(wù)[6]。如圖1所示,作為無(wú)人機(jī)的可移動(dòng)保障平臺(tái),保障車(chē)可以通過(guò)更加靈活的作業(yè)方式在巡檢任務(wù)執(zhí)行期間同時(shí)服務(wù)更多無(wú)人機(jī),即“多對(duì)多”模式。在該模式下保障車(chē)可沿交通路網(wǎng)穿梭于運(yùn)維站和各駐車(chē)點(diǎn)之間,及時(shí)到達(dá)指定位置為無(wú)人機(jī)提供維保和換電等服務(wù);無(wú)人機(jī)則在放飛之后按計(jì)劃飛往目標(biāo)區(qū)域進(jìn)行電力設(shè)施巡檢,在任務(wù)完成或電力不足時(shí)前往任意駐車(chē)點(diǎn)與保障車(chē)匯合進(jìn)行換電、維保、轉(zhuǎn)場(chǎng)或隨車(chē)返回運(yùn)維站。

圖1 VUTIS示例

圖1右側(cè)所示為VUTIS的部分系統(tǒng)的運(yùn)行過(guò)程。其中,保障車(chē)h∈H 由運(yùn)維站i0出發(fā),車(chē)上載有滿(mǎn)電狀態(tài)的無(wú)人機(jī)d1∈D。保障車(chē)h首先到達(dá)駐車(chē)點(diǎn)i1放飛d1后駛往i2。d1首先飛往電力桿塔i3,之后前往i4,最后前往駐車(chē)點(diǎn)i2。與此同時(shí),無(wú)人機(jī)d2在離開(kāi)i6后抵達(dá)i5進(jìn)行巡檢,之后也前往i2。此時(shí),i1與i2均為電量不足狀態(tài),由h回收換電后載回運(yùn)維站i0。由此例可知,在“多對(duì)多”模式中,每輛保障車(chē)可以在滿(mǎn)足服務(wù)能力限制條件下同時(shí)服務(wù)多架無(wú)人機(jī),且無(wú)人機(jī)和保障車(chē)之間沒(méi)有固定的搭配關(guān)系,保障車(chē)本質(zhì)上作為無(wú)人機(jī)起降和轉(zhuǎn)運(yùn)的可移動(dòng)保障平臺(tái),而保障車(chē)在具體作業(yè)場(chǎng)景下同時(shí)服務(wù)的最大無(wú)人機(jī)數(shù)量則需由優(yōu)化決策方案確定。

雖然理論上VUTIS能夠提升無(wú)人機(jī)和保障車(chē)的利用率,節(jié)省運(yùn)行成本,但也對(duì)兩者作業(yè)方案的時(shí)空協(xié)同性提出了更高的要求。首先,當(dāng)無(wú)人機(jī)有換電或轉(zhuǎn)場(chǎng)需求時(shí),保障車(chē)須及時(shí)與無(wú)人機(jī)在駐車(chē)點(diǎn)匯合,以保障系統(tǒng)運(yùn)行效率。此外,在設(shè)計(jì)無(wú)人機(jī)和保障車(chē)的作業(yè)方案時(shí),還要充分考慮無(wú)人機(jī)的續(xù)航限制和氣象條件對(duì)航行速度的影響,同時(shí)關(guān)注保障車(chē)輛的承載能力和道路交通狀態(tài)對(duì)行駛速度的影響[7]。因此,VUTIS中無(wú)人機(jī)與保障車(chē)的協(xié)同作業(yè)優(yōu)化決策不僅要求對(duì)兩者的時(shí)空軌跡精準(zhǔn)刻畫(huà)并構(gòu)造耦合關(guān)聯(lián),還要根據(jù)系統(tǒng)運(yùn)行過(guò)程中的諸多限制條件對(duì)電力巡檢作業(yè)方案進(jìn)行調(diào)整和約束,最終實(shí)現(xiàn)電力巡檢成本的最小化。由此可知,VUTIS綜合優(yōu)化問(wèn)題本質(zhì)上是無(wú)人機(jī)和保障車(chē)作業(yè)計(jì)劃的協(xié)同優(yōu)化問(wèn)題(Vehicle-mounted UAV Cooperative Operation Problem,VUCOP)。相比傳統(tǒng)的車(chē)輛路徑問(wèn)題,該問(wèn)題更加側(cè)重于實(shí)現(xiàn)無(wú)人機(jī)和保障車(chē)在時(shí)間和空間上的協(xié)同合作,即需要在電力巡檢任務(wù)的牽引下,綜合優(yōu)化無(wú)人機(jī)和保障車(chē)的作業(yè)計(jì)劃,確保保障車(chē)能夠在必要時(shí)及時(shí)與無(wú)人機(jī)在駐車(chē)點(diǎn)相遇并為其提供收放飛,換電和轉(zhuǎn)場(chǎng)等服務(wù),同時(shí)還要盡可能地最小化VUTIS 運(yùn)行總成本。為實(shí)現(xiàn)該目標(biāo),VUCOP 要求對(duì)車(chē)輛和無(wú)人機(jī)作業(yè)方案的時(shí)間維度和電量狀態(tài)維度的刻畫(huà)更加精細(xì),需要在無(wú)人機(jī)和保障車(chē)之間建立更加復(fù)雜的時(shí)空耦合約束,模型結(jié)構(gòu)更加復(fù)雜難解。

目前,國(guó)內(nèi)外相關(guān)領(lǐng)域的研究主要側(cè)重于無(wú)人機(jī)電力巡檢的靜態(tài)路徑規(guī)劃。Van等[8]通過(guò)大數(shù)據(jù)技術(shù)建立無(wú)人機(jī)巡檢路徑規(guī)劃數(shù)據(jù)庫(kù),對(duì)追蹤到的無(wú)人機(jī)巡檢路徑規(guī)劃數(shù)據(jù)進(jìn)行分類(lèi)存儲(chǔ),從根本上提高了無(wú)人機(jī)巡檢路徑規(guī)劃的效率。朱程雯等[9]針對(duì)無(wú)人機(jī)巡線(xiàn)路徑問(wèn)題,建立無(wú)人機(jī)巡線(xiàn)作業(yè)環(huán)境模型,并利用蟻群算法求解,以?xún)?yōu)化巡線(xiàn)目標(biāo)的拍攝地點(diǎn)和巡線(xiàn)路徑。吳晏芳等[10]將大數(shù)據(jù)技術(shù)應(yīng)用在無(wú)人機(jī)巡檢路徑規(guī)劃,提出了基于大數(shù)據(jù)的輸電線(xiàn)路無(wú)人機(jī)巡檢路徑追蹤方法,實(shí)現(xiàn)無(wú)人機(jī)巡檢路徑規(guī)劃。有關(guān)車(chē)輛與無(wú)人機(jī)協(xié)同作業(yè)的相關(guān)研究主要應(yīng)用于車(chē)載無(wú)人機(jī)末端配送領(lǐng)域,也即帶有無(wú)人機(jī)的車(chē)輛路徑問(wèn)題(Vehicle Routing P roblem with Drone,VRP-D)[11-13]。Wang等[14]研究了基于中轉(zhuǎn)站的車(chē)輛和無(wú)人機(jī)協(xié)同配送問(wèn)題,通過(guò)構(gòu)建該問(wèn)題的集覆蓋模型,采用分支定價(jià)算法實(shí)現(xiàn)了對(duì)該問(wèn)題的精確求解。楊雙鵬等[15]針對(duì)“疫情隔離”期間應(yīng)急物資配送問(wèn)題,提出一種卡車(chē)+無(wú)人機(jī)聯(lián)合配送模式,即卡車(chē)不參與客戶(hù)配送,完全充當(dāng)無(wú)人機(jī)倉(cāng)庫(kù),無(wú)人機(jī)可攜帶多個(gè)包裹進(jìn)行多點(diǎn)配送。何勇等[16]針對(duì)“載機(jī)平臺(tái)+無(wú)人機(jī)”服務(wù)模式的載機(jī)平臺(tái)調(diào)度問(wèn)題,在用戶(hù)需求分散且隨時(shí)間頻繁波動(dòng)的優(yōu)化背景下,提出基于兩階段魯棒優(yōu)化的載機(jī)平臺(tái)調(diào)度模型,并采用L 型算法進(jìn)行求解。隨著車(chē)載無(wú)人機(jī)電力巡檢技術(shù)的逐漸成熟和推廣使用,大部分學(xué)者借鑒VRP-D 的優(yōu)化方法重點(diǎn)研究“一對(duì)一”[17]和“一對(duì)多”[7]模式的靜態(tài)路徑規(guī)劃問(wèn)題,少部分針對(duì)“多對(duì)多”模式的研究則從空間和時(shí)間兩個(gè)維度上分別構(gòu)建無(wú)人機(jī)和車(chē)輛調(diào)度方案的關(guān)聯(lián)性約束,再建立時(shí)間和空間變量之間的耦合關(guān)系;若考慮無(wú)人機(jī)的續(xù)航約束和保障車(chē)的承載約束,則還要通過(guò)引入大量間接變量在時(shí)空變量間建立非線(xiàn)性約束。這會(huì)導(dǎo)致模型結(jié)構(gòu)極其復(fù)雜而難以通過(guò)數(shù)值型算法快速求解,采用啟發(fā)式算法又難以保證求解大規(guī)模實(shí)際問(wèn)題時(shí)的計(jì)算精度[18-19]。

針對(duì)這一難題,采用時(shí)空網(wǎng)絡(luò)建模方法構(gòu)建無(wú)人機(jī)與保障車(chē)協(xié)同路徑優(yōu)化模型。通過(guò)提高變量維度減少變量種類(lèi)和變量間的復(fù)雜耦合約束,能夠明顯地降低模型結(jié)構(gòu)的復(fù)雜度。但另一方面,提高變量維度又會(huì)造成網(wǎng)絡(luò)規(guī)模和變量總數(shù)的大幅度提高。尤其為精準(zhǔn)刻畫(huà)無(wú)人機(jī)續(xù)航限制對(duì)其電力巡檢方案的影響,需要在時(shí)空網(wǎng)絡(luò)的基礎(chǔ)上構(gòu)建無(wú)人機(jī)的時(shí)空-狀態(tài)網(wǎng)絡(luò)模型,這又會(huì)導(dǎo)致變量維度的進(jìn)一步提高。換言之,通過(guò)采用時(shí)空網(wǎng)絡(luò)建模方法,VUCOP可以進(jìn)一步轉(zhuǎn)化為基于軸福式網(wǎng)絡(luò)的甩掛運(yùn)輸路徑優(yōu)化問(wèn)題(Truck and Trailer Routing Problem,TTRP)的衍生變種,而本質(zhì)上仍然是求解難度很高的NP 難問(wèn)題。因此,為實(shí)現(xiàn)VUCOP 的快速精確求解,本文設(shè)計(jì)基于拉格朗日松弛和貪心規(guī)則的松弛解轉(zhuǎn)換算法(Lagrangian Relaxation and Greedy Rules Algorithm,LR-GR)。首先通過(guò)松弛變量間的耦合難約束,將原問(wèn)題轉(zhuǎn)化為由兩組相互獨(dú)立子問(wèn)題構(gòu)成的對(duì)偶松弛問(wèn)題。鑒于每組子問(wèn)題結(jié)構(gòu)相對(duì)簡(jiǎn)單,可快速求解得到原問(wèn)題的松弛解。之后,針對(duì)VUTIS的軸福式網(wǎng)絡(luò)結(jié)構(gòu)以及無(wú)人機(jī)和保障車(chē)作業(yè)計(jì)劃的時(shí)空關(guān)聯(lián)特性,基于貪心規(guī)則對(duì)松弛解進(jìn)行可行化處理,在保證LR-GR 算法單步迭代的計(jì)算速度的同時(shí)兼顧求解質(zhì)量,以保證優(yōu)化算法在求解較大規(guī)模實(shí)際問(wèn)題時(shí)能夠快速收斂,進(jìn)而在合理時(shí)間范圍內(nèi)得到近似最優(yōu)解。最后,通過(guò)一組敏感性分析實(shí)驗(yàn)驗(yàn)證了無(wú)人機(jī)最大載電量對(duì)于VUTIS整體運(yùn)營(yíng)策略的影響。

1 問(wèn)題描述和時(shí)空網(wǎng)絡(luò)構(gòu)建

車(chē)載無(wú)人機(jī)電力桿塔巡檢系統(tǒng)如圖1所示,其空間網(wǎng)絡(luò)表示為有向圖GS=(I,L)。其中:集合I=IH∪ID表示空間節(jié)點(diǎn),集合IH包括駐車(chē)點(diǎn)和運(yùn)維站i0所在節(jié)點(diǎn),ID為電力桿塔所在節(jié)點(diǎn)集合;L=LH∪LD表示網(wǎng)絡(luò)中的弧段,LH為駐車(chē)點(diǎn)之間以及駐車(chē)點(diǎn)與運(yùn)維站之間的弧段,LD為電力桿塔之間以及電力桿塔與駐車(chē)點(diǎn)之間的弧段。在時(shí)間維度上,將系統(tǒng)運(yùn)營(yíng)周期均勻離散化并生成時(shí)間戳集合T={t0,t0+δT,…,t0+MTδT},其中,t0為起始時(shí)間,δT為兩相鄰時(shí)間戳之間的時(shí)間間隔,集合T中最多包含MT +1個(gè)時(shí)間戳。通過(guò)結(jié)合空間網(wǎng)絡(luò)有向圖和時(shí)間戳集合,得到車(chē)載無(wú)人機(jī)電力巡檢系統(tǒng)的時(shí)空網(wǎng)絡(luò)GT=(N,A)。其中:集合N=NH∪ND表示時(shí)空網(wǎng)絡(luò)中的時(shí)空節(jié)點(diǎn),集合NH包括駐車(chē)點(diǎn)和i0所對(duì)應(yīng)的時(shí)空節(jié)點(diǎn),ND為電力桿塔所對(duì)應(yīng)的時(shí)空節(jié)點(diǎn)集合;A=AH∪AD表示時(shí)空弧段,AH為駐車(chē)點(diǎn)之間以及駐車(chē)點(diǎn)與運(yùn)維站之間的時(shí)空弧段,AD為電力桿塔之間以及電力桿塔與駐車(chē)點(diǎn)之間的時(shí)空弧段。考慮到無(wú)人機(jī)電量限制對(duì)電力桿塔巡檢任務(wù)的影響,本文在刻畫(huà)無(wú)人機(jī)作業(yè)過(guò)程時(shí),在時(shí)空網(wǎng)絡(luò)的基礎(chǔ)上進(jìn)一步拓展電力狀態(tài)維度。參考時(shí)間戳集合,定義無(wú)人機(jī)電量狀態(tài)集合E={e0,e0+δE,…,e0+MδE},其中,e0為無(wú)人機(jī)最低安全電量,δE為兩相鄰電量等級(jí)之間的電量差值,e0+MδE即為無(wú)人機(jī)最大電量。由此構(gòu)建時(shí)空電網(wǎng)絡(luò)GE=(V,K),其中,集合V=VH∪VD表示時(shí)空電節(jié)點(diǎn),集合VH包括駐車(chē)點(diǎn)和i0所對(duì)應(yīng)的時(shí)空電節(jié)點(diǎn),VD為電力桿塔所對(duì)應(yīng)的時(shí)空電節(jié)點(diǎn)集合;K=KH∪KD表示時(shí)空電弧段,KH為駐車(chē)點(diǎn)之間以及駐車(chē)點(diǎn)與運(yùn)維站之間的時(shí)空電弧段,KD為電力桿塔之間以及電力桿塔與駐車(chē)點(diǎn)之間的時(shí)空電弧段。一隊(duì)保障車(chē)H 各載若干架無(wú)人機(jī)D 由運(yùn)維站出發(fā)按照既定計(jì)劃前往指定的駐車(chē)點(diǎn)i∈IH執(zhí)行無(wú)人機(jī)的放飛和回收任務(wù)。無(wú)人機(jī)在放飛后,根據(jù)計(jì)劃飛往相應(yīng)的電力桿塔執(zhí)行巡檢任務(wù),之后前往任意駐車(chē)點(diǎn)由保障車(chē)回收,進(jìn)行電池更換和維保工作,之后視計(jì)劃進(jìn)行再次放飛或由保障車(chē)載回運(yùn)維站。

車(chē)載無(wú)人機(jī)系統(tǒng)電力巡檢的過(guò)程在時(shí)空網(wǎng)絡(luò)中可由兩者的時(shí)空軌跡表示。圖2所示為時(shí)空網(wǎng)絡(luò)包含19個(gè)空間網(wǎng)絡(luò)節(jié)點(diǎn)和38個(gè)時(shí)間戳。其中:節(jié)點(diǎn)1為運(yùn)維站,由紅色標(biāo)識(shí);節(jié)點(diǎn)2～7為駐車(chē)點(diǎn),由藍(lán)色標(biāo)識(shí);節(jié)點(diǎn)8～19為電力桿塔所在節(jié)點(diǎn),由綠色標(biāo)識(shí)。所有無(wú)人機(jī)和保障車(chē)的時(shí)空軌跡均由時(shí)空弧段構(gòu)成。例如,保障車(chē)h1在時(shí)間點(diǎn)0 由運(yùn)維站1 出發(fā),并在時(shí)間點(diǎn)2到達(dá)駐車(chē)點(diǎn)4,以時(shí)空弧可表示為(1,0,4,2)。

圖2 VUTIS時(shí)空網(wǎng)絡(luò)表示示例

由圖2可知,保障車(chē)h1時(shí)空軌跡包括時(shí)空弧段(1,0,4,2)、(4,2,4,4)、(4,4,7,25)、(7,25,7,29)、(7,29,2,33)和(2,33,2,38),h2時(shí)空軌跡包括時(shí)空弧段(1,0,5,5)、(5,5,5,7)、(5,7,4,24)、(4,24,4,27)、(4,27,6,31)、(6,31,6,33)和(6,33,4,38)。由于考慮到無(wú)人機(jī)電池電量對(duì)無(wú)人機(jī)續(xù)航能力和巡檢任務(wù)的影響,因而在時(shí)空網(wǎng)絡(luò)的基礎(chǔ)上增加電量狀態(tài)維度組成時(shí)空電網(wǎng)絡(luò),并通過(guò)時(shí)空電軌跡對(duì)無(wú)人機(jī)的電力巡檢作業(yè)方案進(jìn)行描述。圖2中,無(wú)人機(jī)d1、d2和d3電池滿(mǎn)載電量為8。無(wú)人機(jī)d1和d2隨保障車(chē)h1由駐車(chē)點(diǎn)1出發(fā)到達(dá)駐車(chē)點(diǎn)4,也即表示為時(shí)空電路徑(1,0,8,4,2,8)。由此可知,無(wú)人機(jī)d1的時(shí)空電軌跡包括弧段(1,0,8,4,2,8)、(4,2,8,4,4,8)、(4,4,8,14,7,7)、(14,7,7,14,12,6)、(14,12,6,11,16,5)、(11,16,5,11,21,4)、(11,21,4,7,27,2)、(7,27,2,7,29,8)、(7,29,8,12,33,6)和(12,33,6,12,38,5),無(wú)人機(jī)d2的時(shí)空電軌跡包括弧段(1,0,8,4,2,8)、(4,2,8,4,4,8)、(4,4,8,16,7,7)、(16,7,7,16,12,6)、(16,12,6,18,16,5)、(18,16,5,18,20,3)、(18,20,3,4,25,2)、(4,25,2,4,27,8)、(4,27,8,6,31,8)、(6,31,8,6,33,8)、(6,33,8,15,36,7)和(15,36,7,15,38,6),無(wú)人機(jī)d3的時(shí)空電軌跡包括弧段(1,0,8,5,5,8)、(5,5,8,5,7,8)、(5,7,8,17,11,7)、(17,11,7,17,17,6)、(17,17,6,19,20,5)、(19,20,5,19,25,4)、(19,25,4,10,28,3)、(10,28,3,10,32,2)、(10,32,2,2,36,1)和(2,36,1,2,38,8)。由各無(wú)人機(jī)的時(shí)空電軌跡可見(jiàn),考慮到電力桿塔的體積構(gòu)造以及需要著重檢測(cè)的位置不同,無(wú)人機(jī)實(shí)際上需要在不同桿塔處的滯留的時(shí)間也有所不同。此外,無(wú)人機(jī)在執(zhí)行不同的電力檢測(cè)任務(wù)時(shí)通常需要開(kāi)啟不同的傳感器和信息通信模塊,由此導(dǎo)致能耗速率的差異。例如,圖2中,無(wú)人機(jī)d1在巡檢電力桿塔11時(shí)滯留時(shí)間為5個(gè)時(shí)間單位,耗電量為1個(gè)單位,而無(wú)人機(jī)d2在巡檢電力桿塔18時(shí)滯留時(shí)間為4個(gè)時(shí)間單位,耗電量為2個(gè)單位?？紤]到無(wú)人機(jī)在各項(xiàng)性能指標(biāo)具有一致性的情況下,可知相對(duì)于電力桿塔18,桿塔11的巡檢任務(wù)耗時(shí)更長(zhǎng),但桿塔18的巡檢任務(wù)耗電量更多。需要注意的是,上述電力巡檢任務(wù)的差異性會(huì)通過(guò)無(wú)人機(jī)時(shí)空電網(wǎng)絡(luò)的結(jié)構(gòu)特性加以刻畫(huà)。例如,無(wú)人機(jī)在到達(dá)示例中電力桿塔11后須通過(guò)一條長(zhǎng)5個(gè)時(shí)間單位,1個(gè)電量單位的等待時(shí)空電弧段,而在到達(dá)桿塔18后也須通過(guò)一條長(zhǎng)4個(gè)時(shí)間單位,1個(gè)電量單位的等待時(shí)空弧段才能夠完成桿塔18的巡檢任務(wù)。

2 模型建立

2.1 模型假設(shè)

本文提出的VUCOP 旨在通過(guò)優(yōu)化協(xié)同保障車(chē)與無(wú)人機(jī)的電力巡檢作業(yè)方案,在保證完成電力巡檢任務(wù)的前提下盡可能地降低系統(tǒng)運(yùn)行總成本,同時(shí)還要考慮保障車(chē)的載重限制,無(wú)人機(jī)的續(xù)航限制,天氣對(duì)無(wú)人機(jī)飛行速度的影響和可行的飛行路徑等決策要素。鑒于優(yōu)化問(wèn)題本身的復(fù)雜性,為進(jìn)一步聚焦研究?jī)?nèi)容,做出如下假設(shè):

(1) 無(wú)人機(jī)和保障車(chē)均具有一致的性能指標(biāo),包括行駛(或飛行)速度和能耗速率等。

(2) 無(wú)人機(jī)僅在駐車(chē)點(diǎn)與各電力桿塔以及各電力桿塔之間飛行,駐車(chē)點(diǎn)和運(yùn)維站之間由保障車(chē)運(yùn)送。

(3) 電力巡檢無(wú)人機(jī)普遍采用快速換電模式,無(wú)人機(jī)在返回駐車(chē)點(diǎn)換電后即可在單位時(shí)間段內(nèi)完成換電和維保。

2.2 符號(hào)定義和數(shù)學(xué)模型

除上文中定義的集合符號(hào),模型中涉及的其他主要參數(shù)和變量定義如下:

cD——無(wú)人機(jī)固定使用成本

cH——保障車(chē)固定派遣成本

q——保障車(chē)可同時(shí)承載和服務(wù)的最大無(wú)人機(jī)數(shù)量

mO——保障車(chē)虛擬時(shí)空起點(diǎn)

mD——保障車(chē)虛擬時(shí)空終點(diǎn)

uO——無(wú)人機(jī)虛擬時(shí)空電起點(diǎn)

uD——無(wú)人機(jī)虛擬時(shí)空電終點(diǎn)

因此,基于時(shí)空電網(wǎng)絡(luò)建模方法,VUCOP優(yōu)化模型具體為:

目標(biāo)函數(shù)式(1)表示VUTIS綜合作業(yè)方案的總成本最小,包括保障車(chē)和無(wú)人機(jī)各自的固定派遣成本以及可變行駛成本。其中和分別為保障車(chē)和無(wú)人機(jī)的派遣成本,分別為兩者在執(zhí)行電力巡檢任務(wù)過(guò)程中的行駛和飛行成本。由目標(biāo)函數(shù)形式可知,VUCOP 優(yōu)化決策中包括優(yōu)化無(wú)人機(jī)和保障車(chē)的派遣數(shù)量以及無(wú)人機(jī)和保障車(chē)在任務(wù)執(zhí)行過(guò)程中的協(xié)同作業(yè)計(jì)劃。約束條件式(2)、(3)分別為保障車(chē)和無(wú)人機(jī)的時(shí)空(電)軌跡的流平衡約束。其中,α和β分別為式(2)、(3)的流平衡狀態(tài)參數(shù),即當(dāng)m=mO時(shí),α=1;當(dāng)m=mD時(shí),α=-1;當(dāng)m∈NH時(shí),α=0。當(dāng)u=uO時(shí),β=1;當(dāng)u=uD時(shí),β=-1;當(dāng)u∈V時(shí),β=0。需要注意的是,未派出的無(wú)人機(jī)和保障車(chē)的時(shí)空軌跡僅包含由虛擬起點(diǎn)到虛擬終點(diǎn)的時(shí)空(電)路徑,不會(huì)產(chǎn)生相應(yīng)的派遣和作業(yè)成本。式(4)確保每座電力桿塔都接受巡檢。其中,集合={(i,t,e)|(i,t,e)∈VD}表示桿塔i∈ID對(duì)應(yīng)的所有時(shí)空電節(jié)點(diǎn)集合,向量(u,u′)=(i,t,e,j,s,f)∈KD,表示以u(píng)=(i,t,e)∈VD為起始節(jié)點(diǎn)的對(duì)于桿塔i的巡檢時(shí)空電弧段。式(5)為保障車(chē)和無(wú)人機(jī)作業(yè)方案的耦合關(guān)聯(lián)約束,即無(wú)人機(jī)由保障車(chē)承載完成各駐車(chē)點(diǎn)及運(yùn)維站之間的轉(zhuǎn)移,且需要在駐車(chē)點(diǎn)處由保障車(chē)進(jìn)行換電。集合

表示無(wú)人機(jī)由保障車(chē)承載通過(guò)時(shí)空弧(m,n)∈AH所對(duì)應(yīng)的時(shí)空電弧段集合。該約束表示保障車(chē)在干線(xiàn)(駐車(chē)點(diǎn)間或駐車(chē)點(diǎn)與運(yùn)維站之間)的時(shí)空弧段數(shù)與載重量的乘積q均不得小于無(wú)人機(jī)相對(duì)應(yīng)時(shí)空電弧段的數(shù)量,即可以保證無(wú)人機(jī)放飛、回收和轉(zhuǎn)場(chǎng)等操作均要求保障車(chē)及時(shí)到達(dá)指定位置并全程提供保障服務(wù)。式(6)、(7)分別為變量的完整性約束。

3 模型求解算法

由于采用了時(shí)空網(wǎng)絡(luò)建模方法,VUCOP 本質(zhì)上可視為基于軸輻式網(wǎng)絡(luò)的TTRP衍生問(wèn)題,而后者已被證明是NP-hard問(wèn)題[21]。在TTRP 的基礎(chǔ)上,VUCOP 進(jìn)一步要求無(wú)人機(jī)和保障車(chē)的協(xié)同作業(yè)方案在時(shí)間上保持協(xié)同,同時(shí)還需要考慮電力巡檢任務(wù)執(zhí)行過(guò)程中無(wú)人機(jī)的電量限制,以及保障車(chē)承載無(wú)人機(jī)的數(shù)量限制,因此模型結(jié)構(gòu)更為復(fù)雜,求解更難。為了在保證優(yōu)化方法計(jì)算效率的同時(shí)盡可能地提高求解精度,本文根據(jù)VUCOP 優(yōu)化模型結(jié)構(gòu)設(shè)計(jì)基于LR 算法框架的優(yōu)化求解方法,將原問(wèn)題拆分為兩組結(jié)構(gòu)相對(duì)簡(jiǎn)單、求解效率較高的子問(wèn)題,得到原問(wèn)題的松弛解。在此基礎(chǔ)上,根據(jù)每個(gè)松弛子問(wèn)題包含的優(yōu)化決策信息設(shè)計(jì)高效算法得到相應(yīng)的可行解。最后,通過(guò)次梯度算法更新迭代松弛因子,縮小上下界之間的差值直到求得滿(mǎn)足實(shí)際決策需求的近似最優(yōu)解甚至最優(yōu)解。

3.1 基于LR的原問(wèn)題模型分解

首先,VUCOP為整數(shù)線(xiàn)性規(guī)劃問(wèn)題且其優(yōu)化模型結(jié)構(gòu)滿(mǎn)足KKT條件[22],適用于LR算法進(jìn)行求解;其次,通過(guò)分析模型的約束條件可知,式(4)、(5)是建立了多組變量間的耦合關(guān)聯(lián)的難約束。因此,通過(guò)松弛這兩組約束,可以將原問(wèn)題分解為兩組互不關(guān)聯(lián)的子問(wèn)題,每組子問(wèn)題結(jié)構(gòu)相對(duì)簡(jiǎn)單,便于求解。

然后得到原問(wèn)題的對(duì)偶問(wèn)題,即

滿(mǎn)足約束條件式(2)、(3)和式(6)、(7)。

由于松弛了約束條件式(4)、(5),解除了變量X、Y之間的耦合關(guān)聯(lián),因而松弛問(wèn)題可以拆分為兩個(gè)相互獨(dú)立的子問(wèn)題。其中,問(wèn)題S1中包含了個(gè)獨(dú)立子問(wèn)題,以決策每輛保障車(chē)的作業(yè)方案,即

滿(mǎn)足約束式(2)、(6)。

滿(mǎn)足約束式(3)、(7)。

由于每組松弛子問(wèn)題都只包括一組變量及其對(duì)應(yīng)的流平衡約束和完整性約束,結(jié)構(gòu)相對(duì)簡(jiǎn)單且符合全幺模性質(zhì),因而可直接將子問(wèn)題松弛為連續(xù)線(xiàn)性規(guī)劃問(wèn)題,且以往相關(guān)研究中已證明得到的最優(yōu)解仍然能夠保證二元性[23]。即此時(shí)約束條件式(6)、(7)可替換為:

線(xiàn)性化之后,每個(gè)獨(dú)立子問(wèn)題均可采用單純形法和內(nèi)點(diǎn)法等連續(xù)線(xiàn)性?xún)?yōu)化算法進(jìn)行快速求解,且可采用分布式并行計(jì)算進(jìn)一步提高求解效率。

根據(jù)LR 的對(duì)偶性可知,由此得到的松弛問(wèn)題目標(biāo)函數(shù)最小值即為原問(wèn)題目標(biāo)函數(shù)最小值的下界。

3.2 松弛解的可行化方法

由于松弛了原問(wèn)題模型中的兩組關(guān)鍵約束式(4)、(5),在求解中等實(shí)際規(guī)模問(wèn)題時(shí)得到的協(xié)同作業(yè)方案大多數(shù)不可行,需要根據(jù)每組松弛解能夠提供的決策信息及其之間的關(guān)聯(lián)性重新構(gòu)建耦合關(guān)聯(lián),以得到原問(wèn)題的可行解。由于松弛解的可行化算法直接關(guān)系到最終優(yōu)化結(jié)果的精度和算法整體的求解效率,所以算法需要兼顧每次循環(huán)的求解質(zhì)量和速度,以提高LR-GR 算法整體的收斂效果同時(shí)盡可能地減少算法復(fù)雜度。由此,本文根據(jù)問(wèn)題特點(diǎn)提出基于貪心規(guī)則的兩階段可行化算法。

首先,對(duì)未接受巡檢的電力桿塔所對(duì)應(yīng)的巡檢時(shí)空電弧段重新賦予權(quán)重,新增派遣無(wú)人機(jī)完成剩余的巡檢任務(wù),之后再根據(jù)所有無(wú)人機(jī)的派遣方案對(duì)集合AH內(nèi)時(shí)空弧段的權(quán)重進(jìn)行賦值,逐次增派保障車(chē)覆蓋相應(yīng)時(shí)空弧段直至完成所有無(wú)人機(jī)保障任務(wù)。需要注意的是,保障車(chē)作業(yè)方案還需要特別考慮無(wú)人機(jī)的承載數(shù)量限制。具體步驟如下:

步驟1根據(jù)松弛解篩選得到仍未接受巡檢的電力桿塔集合IR。

步驟2對(duì)于所有時(shí)空電弧段(u,v)∈KD,生成權(quán)重參數(shù):

式中,M為取值較大的固定參數(shù)。

步驟3選取無(wú)人機(jī)集合中尚未派遣的一架無(wú)人機(jī)d∈D,求解如下模型,得到相應(yīng)的可行解,即

步驟5對(duì)于無(wú)人機(jī)集合中尚未派遣的保障車(chē)h∈H,求解模型:

步驟6輸出最終可行解并將其代入原問(wèn)題目標(biāo)函數(shù)式(1),求得相應(yīng)的目標(biāo)函數(shù)值作為最小目標(biāo)函數(shù)值的上界。

3.3 基于次梯度算法的LR乘子迭代方法

考慮到VUCOP優(yōu)化模型結(jié)構(gòu)的復(fù)雜性,在解決實(shí)際規(guī)模問(wèn)題時(shí)需要通過(guò)不斷迭代LR 乘子的取值縮小原問(wèn)題最優(yōu)解的上下界之間的差值,不斷改善可行解的質(zhì)量,在合理的運(yùn)算時(shí)間內(nèi)得到滿(mǎn)足實(shí)際要求精度的可行解甚至是最優(yōu)解。本文采用的次梯度算法計(jì)算復(fù)雜度低,在諸多相關(guān)領(lǐng)域研究中都能以較高的執(zhí)行效率迭代LR 乘子的取值快速收斂上下界。算法具體步驟如下:

步驟0初始化。

(1) 迭代次數(shù)K0;

(2) 步長(zhǎng)因子(τ)0=2;

(3) 最優(yōu)解上界(UB)0=-∞;

(4)LR 乘子:(λi)0=0,?i∈ID,(μmn)0=0,?(m,n)∈AH。

步驟1求解松弛子問(wèn)題S1和S2,得到松弛解即原問(wèn)題目標(biāo)函數(shù)最大值的下界(LB)K。

步驟2根據(jù)2.2節(jié)的兩階段算法將松弛解可行化得到可行解和相應(yīng)的目標(biāo)函數(shù)值,如果該取值大于下界,則更新上界(UB)K→(UB)K+1。

步驟3如果在一定迭代次數(shù)之內(nèi)可行解沒(méi)有明顯改善,即下界沒(méi)有明顯上升,則更新步長(zhǎng)因子(τ)K=(τ)K+1/θ,θ＞1。

步驟4按照下式計(jì)算第K+1次迭代的步長(zhǎng):

步驟5按照下式得到第K +1次迭代的LR乘子:

步驟6若滿(mǎn)足以下任意條件則停止迭代,并輸出最優(yōu)上界作為最終的目標(biāo)函數(shù)值,相應(yīng)的可行解以及上下界之間的相對(duì)差值;否則,K→K+1,跳轉(zhuǎn)至步驟2。

(1) 最優(yōu)解上下界的相對(duì)差值(即LR-GR 算法的相對(duì)誤差)小于預(yù)設(shè)的閾值,即 ((UB)K -(LB)K)/(LB)K≤ε;

(2) 步長(zhǎng)因子小于閾值,即(τ)K＜;

(3) 迭代次數(shù)達(dá)到預(yù)設(shè)的最大迭代數(shù),即K=。

4 算例分析

為了驗(yàn)證本文優(yōu)化方法的性能,首先通過(guò)一組可變規(guī)模的算例比較LR-GR 算法與CPLEX 商用求解器的計(jì)算時(shí)間和精度,再通過(guò)一個(gè)較大規(guī)模算例進(jìn)行敏感性實(shí)驗(yàn)分析無(wú)人機(jī)電池最大載電量對(duì)于VUTIS在最優(yōu)作業(yè)策略下的影響,進(jìn)而得到相應(yīng)的管理學(xué)啟示。本文的所有算例均用MATLAB編程實(shí)現(xiàn),使用的CPLEX 版本是12.6.3 學(xué)術(shù)版,并通過(guò)Yalmip工具箱做接口調(diào)用。算例的運(yùn)行環(huán)境為載有Intel(R)Core(TM)i7-8700 CPU 3.2 GHz處理器和16 GB內(nèi)存的臺(tái)式計(jì)算機(jī)。

為了保證可變規(guī)模算例的代表性,VUTIS網(wǎng)絡(luò)參照?qǐng)D1中的軸輻式網(wǎng)絡(luò)結(jié)構(gòu),駐車(chē)點(diǎn)間的距離在[1,5]km 內(nèi)隨機(jī)生成,電力桿塔之間以及電力桿塔與駐車(chē)點(diǎn)之間的距離在[0.4,1]km 內(nèi)隨機(jī)生成。設(shè)系統(tǒng)運(yùn)行的時(shí)間段內(nèi)包含60個(gè)時(shí)間戳,時(shí)間間隔為2 min。每輛保障車(chē)的固定派遣成本為100 元,單位距離行駛成本為0.5元/km,平均行駛速度為30 km/h,每輛車(chē)最多可以同時(shí)承載和服務(wù)2架無(wú)人機(jī)。每架無(wú)人機(jī)的固定使用成本設(shè)為30元,單位距離飛行成本為0.1 元/km,平均飛行速度為12 km/h。設(shè)無(wú)人機(jī)電池電量包含15個(gè)電量等級(jí),每個(gè)電量等級(jí)1 000 m Ah。假設(shè)無(wú)人機(jī)每飛行2 min消耗1個(gè)電量等級(jí)。

在對(duì)比試驗(yàn)中CPLEX 的最大計(jì)算時(shí)間設(shè)置為3 000 s,如果在此時(shí)間范圍內(nèi)無(wú)法找到可行解,則以“NA”表示。LR-GR 和CPLEX 的優(yōu)化結(jié)果和性能對(duì)比如表1所示。需要說(shuō)明的是,表中“規(guī)?！表?xiàng)的3組數(shù)字分別表示每個(gè)算例的駐車(chē)點(diǎn)、電力桿塔、保障車(chē)以及無(wú)人機(jī)的數(shù)量。

通過(guò)表1中兩種求解方法的計(jì)算結(jié)果可知,隨著問(wèn)題規(guī)模的逐漸擴(kuò)大,兩者的計(jì)算時(shí)長(zhǎng)也都隨之增長(zhǎng),且求解精度也逐漸降低。在算例1 中,LRGR 算法的計(jì)算時(shí)間長(zhǎng)于CPLEX,相對(duì)誤差也要高于CPLEX?？梢?jiàn),在求解較小規(guī)模算例時(shí),CPLEX的計(jì)算性能要高于LR-GR 算法。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大,電力桿塔、駐車(chē)點(diǎn)、保障車(chē)和無(wú)人機(jī)的總數(shù)逐漸增加,雖然LR-GR 算法性能有所下降,但由于其采用了LR 松弛和獨(dú)立子問(wèn)題并行計(jì)算等策略提高了算法的計(jì)算效率,因而依然能夠保證相對(duì)較高的性能。相比之下,CPLEX 則劣化更為嚴(yán)重。尤其對(duì)于較大規(guī)模算例7和8,CPLEX 已經(jīng)無(wú)法在3 000 s內(nèi)給出可行解,但LR-GR 算法仍然能夠保證在實(shí)際操作中可接受時(shí)間范圍內(nèi)給出較高質(zhì)量的可行解(最大規(guī)模案例8的計(jì)算時(shí)間不超過(guò)2 000 s,計(jì)算誤差小于14%)。需要注意的是,VUCOP 是涉及多層復(fù)雜網(wǎng)絡(luò)多主體協(xié)同優(yōu)化的運(yùn)營(yíng)決策問(wèn)題,此類(lèi)問(wèn)題的復(fù)雜度較高?？紤]到車(chē)載無(wú)人機(jī)優(yōu)化調(diào)度領(lǐng)域內(nèi)相似研究中求解方法的性能表現(xiàn)[14,20],由對(duì)比實(shí)驗(yàn)的結(jié)果可見(jiàn),本文基于LR 框架的算法在解決較大規(guī)模問(wèn)題時(shí)具有相對(duì)較高的精度和計(jì)算效率。

表1 LR與CPLEX優(yōu)化結(jié)果及性能比較

此外,為了充分反映兩種求解方法優(yōu)化得到的任務(wù)執(zhí)行方案的總體效率,優(yōu)化結(jié)果還對(duì)比了兩者求解得到的總派遣成本和總行駛成本。其中,總派遣成本是指無(wú)人機(jī)和保障車(chē)的固定派遣成本之和,總行駛成本是無(wú)人機(jī)飛行成本和保障車(chē)行駛成本之和。由兩組參數(shù)的對(duì)比結(jié)果可知。LR-GR算法得到的無(wú)人機(jī)和保障車(chē)的派遣成本在每組算例中都不大于CPLEX派遣成本。鑒于總派遣成本占總成本的比例較高,因此,LR-GR 算法求解得到的系統(tǒng)總成本也不大于CPLEX。此外,除算例1和2之外的所有可比較算例中,LR-GR算法都能夠優(yōu)化得到更低的總派遣成本,且兩者差距也隨著問(wèn)題規(guī)模的擴(kuò)大而不斷增加。由總行駛成本的對(duì)比結(jié)果可知,在算例1中LR-GR 算法與CPLEX的總行駛成本相同,算例2中LR-GR求解得到的總行駛成本小于CPLEX。這說(shuō)明,在較小算例中總派遣成本相同的情況下,LR-GR 算法求解得到的總行駛成本不高于CPLEX。而在其他規(guī)模較大案例中,LR-GR 求解得到的總行駛成本則要略高于CPLEX。這是由于在這些算例中,無(wú)人機(jī)和保障車(chē)派遣數(shù)量的增加能夠在一定程度上降低兩者的運(yùn)行調(diào)度成本,但由于在系統(tǒng)總成本中,總派遣成本占比遠(yuǎn)高于總行駛成本,可知LR-GR 算法優(yōu)化得到的系統(tǒng)總成本低于CPLEX。

圖3所示為L(zhǎng)R-GR 算法求解算例5過(guò)程中的相對(duì)誤差隨迭代次數(shù)的變化?？梢?jiàn),由于LR-GR算法的松弛解可行化方法的精度較高,迭代初期就能以較快的速度收斂至相對(duì)較低的誤差(以低于30的迭代次數(shù)達(dá)到接近10%的相對(duì)誤差)。因此,管理者可以根據(jù)實(shí)際的優(yōu)化決策需求在保障一定求解精度的同時(shí)適當(dāng)減少迭代次數(shù)和計(jì)算時(shí)間。

圖3 LR-GR 算法相對(duì)誤差隨迭代次數(shù)的變化

為了進(jìn)一步驗(yàn)證VUCOP 中關(guān)鍵參數(shù)的改變對(duì)于系統(tǒng)整體運(yùn)作策略以及相應(yīng)指標(biāo)的影響,以算例8的網(wǎng)絡(luò)為基礎(chǔ),在保持其他參數(shù)取值不變的情況下將無(wú)人機(jī)的電量等級(jí)總數(shù)由10增長(zhǎng)至30,以觀(guān)察總成本和各部分成本的變化情況,其實(shí)驗(yàn)結(jié)果如表2所示。需要說(shuō)明的是,這里假設(shè)無(wú)人機(jī)續(xù)航能力(即最大載電量)提高的同時(shí)不改變其載重和續(xù)航能力等性能。在實(shí)際應(yīng)用中,企業(yè)可以通過(guò)購(gòu)買(mǎi)續(xù)航能力更高但其他性能維持不變的同系列不同型號(hào)的無(wú)人機(jī),這也符合相關(guān)行業(yè)中電力巡檢的管理運(yùn)營(yíng)需求。

表2 系統(tǒng)運(yùn)行各指標(biāo)隨無(wú)人機(jī)電量等級(jí)總數(shù)的變化

由表2可見(jiàn),在無(wú)人機(jī)電池最大載電量由10增長(zhǎng)至20的過(guò)程中,總成本和其他各部分成本總體上呈下降趨勢(shì)。隨著無(wú)人機(jī)電池最大載電量的提升,無(wú)人機(jī)的飛行成本則由7.34元波動(dòng)式下降至4.24元。尤其當(dāng)無(wú)人機(jī)使用成本減少時(shí),無(wú)人機(jī)飛行成本會(huì)出現(xiàn)先增后減的情況。如算例1～3中,無(wú)人機(jī)使用成本由240元下降至210元,而無(wú)人機(jī)飛行成本先由7.34 元增長(zhǎng)至8.28 元又下降至5.48 元。這說(shuō)明,在最優(yōu)作業(yè)計(jì)劃下無(wú)人機(jī)續(xù)航能力的提高確實(shí)能夠以更少的無(wú)人機(jī)和保障車(chē)完成電力巡檢任務(wù),但相對(duì)地需要每架無(wú)人機(jī)承擔(dān)更多的電力巡檢任務(wù),增加所有無(wú)人機(jī)的總飛行距離;同時(shí),也需要保障車(chē)載無(wú)人機(jī)更加頻繁地往返于各駐車(chē)點(diǎn),進(jìn)而增加保障車(chē)的總行駛距離,最終產(chǎn)生更多的無(wú)人機(jī)飛行成本和保障車(chē)行駛成本。但也注意到,隨著無(wú)人機(jī)最大載電量的不斷提升,系統(tǒng)效率提升的幅度也在逐漸降低,直至無(wú)人機(jī)最大載電量提升至24之后,無(wú)人機(jī)和保障車(chē)的派遣成本均維持不變,且總成本的下降幅度也相對(duì)較小。由此可見(jiàn),提高無(wú)人機(jī)最大載電量所帶來(lái)的邊際收益也隨之減少。

5 結(jié)論

針對(duì)目前“一對(duì)一”模式下車(chē)載無(wú)人機(jī)電力巡檢系統(tǒng)對(duì)無(wú)人機(jī)和保障車(chē)?yán)寐实偷膯?wèn)題,結(jié)合電力巡檢任務(wù)范圍大,任務(wù)點(diǎn)分布稀疏的特點(diǎn),以提升系統(tǒng)運(yùn)行效率、靈活性和經(jīng)濟(jì)性為目標(biāo),提出基于時(shí)空網(wǎng)絡(luò)的“多對(duì)多”車(chē)載無(wú)人機(jī)協(xié)同作業(yè)優(yōu)化決策方法。研究成果為解決軸輻式雙層網(wǎng)絡(luò)下多主體協(xié)同優(yōu)化決策問(wèn)題提供了新方法,從無(wú)人機(jī)與車(chē)輛協(xié)同作業(yè)研究方向上進(jìn)一步拓展了VRP-D的相關(guān)研究,對(duì)于車(chē)載無(wú)人機(jī)系統(tǒng)在電力巡檢中的進(jìn)一步推廣和提升電力巡檢的自動(dòng)化和智能化水平具有實(shí)踐指導(dǎo)意義。研究成果的創(chuàng)新之處可具體歸納為:

(1) 根據(jù)無(wú)人機(jī)電力巡檢的相關(guān)技術(shù)背景,通過(guò)調(diào)研相關(guān)行業(yè)目前在無(wú)人機(jī)電力巡檢實(shí)際運(yùn)作中遇到的問(wèn)題和關(guān)鍵需求,提出了車(chē)載無(wú)人機(jī)電力巡檢系統(tǒng)的作業(yè)模式,為未來(lái)的無(wú)人機(jī)電力巡檢的實(shí)踐管理提供理論支撐。

(2) 針對(duì)車(chē)載無(wú)人機(jī)電力巡檢協(xié)同作業(yè)優(yōu)化問(wèn)題,提出基于時(shí)空網(wǎng)絡(luò)的無(wú)人機(jī)與保障車(chē)協(xié)同路徑優(yōu)化方法,將電力巡檢過(guò)程中的天氣和交通狀態(tài)等決策要素整合到時(shí)空網(wǎng)絡(luò)構(gòu)建和時(shí)空路徑生成機(jī)制中,簡(jiǎn)化了模型的形式。

(3) 為精準(zhǔn)刻畫(huà)無(wú)人機(jī)巡航能力限制對(duì)系統(tǒng)決策的影響,在時(shí)空網(wǎng)絡(luò)的基礎(chǔ)上增加了無(wú)人機(jī)電量維度,避免在構(gòu)建電量限制約束時(shí)出現(xiàn)非線(xiàn)性結(jié)構(gòu),進(jìn)一步提高模型的可解性。

(4) 根據(jù)VUTIS中保障車(chē)和無(wú)人機(jī)作業(yè)方案的時(shí)空關(guān)聯(lián)特性,在LR 算法框架的基礎(chǔ)上提出LR-GR 算法,以兼顧單步迭代的計(jì)算效率和求解質(zhì)量,并通過(guò)與CPLEX 求解器的對(duì)比驗(yàn)證了優(yōu)化算法在解決實(shí)際規(guī)模問(wèn)題上的有效性。

此外,本文還通過(guò)敏感性分析實(shí)驗(yàn)研究了無(wú)人機(jī)電池總載電量對(duì)于VUTIS運(yùn)作策略和運(yùn)行成本的影響,并得到了一些重要的管理啟示。例如,雖然無(wú)人機(jī)電池最大載電量的提高能夠節(jié)省無(wú)人機(jī)和保障車(chē)的派遣數(shù)量,降低固定成本,但又會(huì)提高每架無(wú)人機(jī)和每輛保障車(chē)的使用效率而在一定程度上提高行駛成本。由于無(wú)人機(jī)和保障車(chē)的行駛成本均遠(yuǎn)小于各自的固定派遣成本,所以總成本仍然會(huì)下降。但這種下降趨勢(shì)也會(huì)隨著最大載電量的不斷增加而趨于平穩(wěn)。由此可知,在系統(tǒng)建設(shè)和設(shè)備采購(gòu)階段可以通過(guò)選擇續(xù)航能力更強(qiáng)的無(wú)人機(jī)而適當(dāng)減少無(wú)人機(jī)的采購(gòu)數(shù)量,但過(guò)度追求長(zhǎng)續(xù)航的無(wú)人機(jī)必然會(huì)提高單架無(wú)人機(jī)的采購(gòu)成本,最終導(dǎo)致系統(tǒng)運(yùn)營(yíng)總成本過(guò)高。

本文提出的時(shí)空狀態(tài)網(wǎng)絡(luò)模型加LR 松弛算法的優(yōu)化方法理論框架,為研究車(chē)載無(wú)人機(jī)電力巡檢系統(tǒng)設(shè)計(jì)和運(yùn)營(yíng)調(diào)度各類(lèi)問(wèn)題拓展研究思路。例如,考慮到無(wú)人機(jī)電力巡檢的實(shí)際操作過(guò)程中面臨的諸多不確定因素,在之后的研究中將更加關(guān)注VUTIS在運(yùn)行過(guò)程中受到的外界環(huán)境干擾而出現(xiàn)的隨機(jī)場(chǎng)景,并針對(duì)這一問(wèn)題將嘗試采用隨機(jī)規(guī)劃的方法對(duì)無(wú)人機(jī)電力巡檢系統(tǒng)的資源配置和網(wǎng)絡(luò)布局進(jìn)行可靠性設(shè)計(jì)。為提高無(wú)人機(jī)電力巡檢的作業(yè)效率,在部分作業(yè)場(chǎng)景下會(huì)將電力桿塔和電纜的巡檢任務(wù)同步進(jìn)行,由此產(chǎn)生車(chē)載無(wú)人機(jī)綜合電力巡檢作業(yè)優(yōu)化問(wèn)題也將是未來(lái)研究的關(guān)注方向。最后,在求解結(jié)構(gòu)更加復(fù)雜的優(yōu)化問(wèn)題時(shí),還需要基于現(xiàn)有的LR 優(yōu)化方法框架進(jìn)一步提高單步計(jì)算的求解質(zhì)量,加速收斂過(guò)程,以期在解決實(shí)際規(guī)模問(wèn)題時(shí)能夠以合理的計(jì)算時(shí)間得到更高精度的近似最優(yōu)解。