電力巡檢車載無人機協同作業優化

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

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

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

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

圖1 VUTIS示例

圖1右側所示為VUTIS的部分系統的運行過程。其中,保障車h∈H 由運維站i0出發,車上載有滿電狀態的無人機d1∈D。保障車h首先到達駐車點i1放飛d1后駛往i2。d1首先飛往電力桿塔i3,之后前往i4,最后前往駐車點i2。與此同時,無人機d2在離開i6后抵達i5進行巡檢,之后也前往i2。此時,i1與i2均為電量不足狀態,由h回收換電后載回運維站i0。由此例可知,在“多對多”模式中,每輛保障車可以在滿足服務能力限制條件下同時服務多架無人機,且無人機和保障車之間沒有固定的搭配關系,保障車本質上作為無人機起降和轉運的可移動保障平臺,而保障車在具體作業場景下同時服務的最大無人機數量則需由優化決策方案確定。

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

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

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

1 問題描述和時空網絡構建

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

車載無人機系統電力巡檢的過程在時空網絡中可由兩者的時空軌跡表示。圖2所示為時空網絡包含19個空間網絡節點和38個時間戳。其中:節點1為運維站,由紅色標識;節點2～7為駐車點,由藍色標識;節點8～19為電力桿塔所在節點,由綠色標識。所有無人機和保障車的時空軌跡均由時空弧段構成。例如,保障車h1在時間點0 由運維站1 出發,并在時間點2到達駐車點4,以時空弧可表示為(1,0,4,2)。

圖2 VUTIS時空網絡表示示例

由圖2可知,保障車h1時空軌跡包括時空弧段(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時空軌跡包括時空弧段(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)。由于考慮到無人機電池電量對無人機續航能力和巡檢任務的影響,因而在時空網絡的基礎上增加電量狀態維度組成時空電網絡,并通過時空電軌跡對無人機的電力巡檢作業方案進行描述。圖2中,無人機d1、d2和d3電池滿載電量為8。無人機d1和d2隨保障車h1由駐車點1出發到達駐車點4,也即表示為時空電路徑(1,0,8,4,2,8)。由此可知,無人機d1的時空電軌跡包括弧段(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),無人機d2的時空電軌跡包括弧段(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),無人機d3的時空電軌跡包括弧段(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)。由各無人機的時空電軌跡可見,考慮到電力桿塔的體積構造以及需要著重檢測的位置不同,無人機實際上需要在不同桿塔處的滯留的時間也有所不同。此外,無人機在執行不同的電力檢測任務時通常需要開啟不同的傳感器和信息通信模塊,由此導致能耗速率的差異。例如,圖2中,無人機d1在巡檢電力桿塔11時滯留時間為5個時間單位,耗電量為1個單位,而無人機d2在巡檢電力桿塔18時滯留時間為4個時間單位,耗電量為2個單位。考慮到無人機在各項性能指標具有一致性的情況下,可知相對于電力桿塔18,桿塔11的巡檢任務耗時更長,但桿塔18的巡檢任務耗電量更多。需要注意的是,上述電力巡檢任務的差異性會通過無人機時空電網絡的結構特性加以刻畫。例如,無人機在到達示例中電力桿塔11后須通過一條長5個時間單位,1個電量單位的等待時空電弧段,而在到達桿塔18后也須通過一條長4個時間單位,1個電量單位的等待時空弧段才能夠完成桿塔18的巡檢任務。

2 模型建立

2.1 模型假設

本文提出的VUCOP 旨在通過優化協同保障車與無人機的電力巡檢作業方案,在保證完成電力巡檢任務的前提下盡可能地降低系統運行總成本,同時還要考慮保障車的載重限制,無人機的續航限制,天氣對無人機飛行速度的影響和可行的飛行路徑等決策要素。鑒于優化問題本身的復雜性,為進一步聚焦研究內容,做出如下假設:

(1) 無人機和保障車均具有一致的性能指標,包括行駛(或飛行)速度和能耗速率等。

(2) 無人機僅在駐車點與各電力桿塔以及各電力桿塔之間飛行,駐車點和運維站之間由保障車運送。

(3) 電力巡檢無人機普遍采用快速換電模式,無人機在返回駐車點換電后即可在單位時間段內完成換電和維保。

2.2 符號定義和數學模型

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

cD——無人機固定使用成本

cH——保障車固定派遣成本

q——保障車可同時承載和服務的最大無人機數量

mO——保障車虛擬時空起點

mD——保障車虛擬時空終點

uO——無人機虛擬時空電起點

uD——無人機虛擬時空電終點

因此,基于時空電網絡建模方法,VUCOP優化模型具體為:

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

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

3 模型求解算法

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

3.1 基于LR的原問題模型分解

首先,VUCOP為整數線性規劃問題且其優化模型結構滿足KKT條件[22],適用于LR算法進行求解;其次,通過分析模型的約束條件可知,式(4)、(5)是建立了多組變量間的耦合關聯的難約束。因此,通過松弛這兩組約束,可以將原問題分解為兩組互不關聯的子問題,每組子問題結構相對簡單,便于求解。

然后得到原問題的對偶問題,即

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

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

滿足約束式(2)、(6)。

滿足約束式(3)、(7)。

由于每組松弛子問題都只包括一組變量及其對應的流平衡約束和完整性約束,結構相對簡單且符合全幺模性質,因而可直接將子問題松弛為連續線性規劃問題,且以往相關研究中已證明得到的最優解仍然能夠保證二元性[23]。即此時約束條件式(6)、(7)可替換為:

線性化之后,每個獨立子問題均可采用單純形法和內點法等連續線性優化算法進行快速求解,且可采用分布式并行計算進一步提高求解效率。

根據LR 的對偶性可知,由此得到的松弛問題目標函數最小值即為原問題目標函數最小值的下界。

3.2 松弛解的可行化方法

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

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

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

步驟2對于所有時空電弧段(u,v)∈KD,生成權重參數:

式中,M為取值較大的固定參數。

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

步驟5對于無人機集合中尚未派遣的保障車h∈H,求解模型:

步驟6輸出最終可行解并將其代入原問題目標函數式(1),求得相應的目標函數值作為最小目標函數值的上界。

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

考慮到VUCOP優化模型結構的復雜性,在解決實際規模問題時需要通過不斷迭代LR 乘子的取值縮小原問題最優解的上下界之間的差值,不斷改善可行解的質量,在合理的運算時間內得到滿足實際要求精度的可行解甚至是最優解。本文采用的次梯度算法計算復雜度低,在諸多相關領域研究中都能以較高的執行效率迭代LR 乘子的取值快速收斂上下界。算法具體步驟如下:

步驟0初始化。

(1) 迭代次數K0;

(2) 步長因子(τ)0=2;

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

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

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

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

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

步驟4按照下式計算第K+1次迭代的步長:

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

步驟6若滿足以下任意條件則停止迭代,并輸出最優上界作為最終的目標函數值,相應的可行解以及上下界之間的相對差值;否則,K→K+1,跳轉至步驟2。

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

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

(3) 迭代次數達到預設的最大迭代數,即K=。

4 算例分析

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

為了保證可變規模算例的代表性,VUTIS網絡參照圖1中的軸輻式網絡結構,駐車點間的距離在[1,5]km 內隨機生成,電力桿塔之間以及電力桿塔與駐車點之間的距離在[0.4,1]km 內隨機生成。設系統運行的時間段內包含60個時間戳,時間間隔為2 min。每輛保障車的固定派遣成本為100 元,單位距離行駛成本為0.5元/km,平均行駛速度為30 km/h,每輛車最多可以同時承載和服務2架無人機。每架無人機的固定使用成本設為30元,單位距離飛行成本為0.1 元/km,平均飛行速度為12 km/h。設無人機電池電量包含15個電量等級,每個電量等級1 000 m Ah。假設無人機每飛行2 min消耗1個電量等級。

在對比試驗中CPLEX 的最大計算時間設置為3 000 s,如果在此時間范圍內無法找到可行解,則以“NA”表示。LR-GR 和CPLEX 的優化結果和性能對比如表1所示。需要說明的是,表中“規模”項的3組數字分別表示每個算例的駐車點、電力桿塔、保障車以及無人機的數量。

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

表1 LR與CPLEX優化結果及性能比較

此外,為了充分反映兩種求解方法優化得到的任務執行方案的總體效率,優化結果還對比了兩者求解得到的總派遣成本和總行駛成本。其中,總派遣成本是指無人機和保障車的固定派遣成本之和,總行駛成本是無人機飛行成本和保障車行駛成本之和。由兩組參數的對比結果可知。LR-GR算法得到的無人機和保障車的派遣成本在每組算例中都不大于CPLEX派遣成本。鑒于總派遣成本占總成本的比例較高,因此,LR-GR 算法求解得到的系統總成本也不大于CPLEX。此外,除算例1和2之外的所有可比較算例中,LR-GR算法都能夠優化得到更低的總派遣成本,且兩者差距也隨著問題規模的擴大而不斷增加。由總行駛成本的對比結果可知,在算例1中LR-GR 算法與CPLEX的總行駛成本相同,算例2中LR-GR求解得到的總行駛成本小于CPLEX。這說明,在較小算例中總派遣成本相同的情況下,LR-GR 算法求解得到的總行駛成本不高于CPLEX。而在其他規模較大案例中,LR-GR 求解得到的總行駛成本則要略高于CPLEX。這是由于在這些算例中,無人機和保障車派遣數量的增加能夠在一定程度上降低兩者的運行調度成本,但由于在系統總成本中,總派遣成本占比遠高于總行駛成本,可知LR-GR 算法優化得到的系統總成本低于CPLEX。

圖3所示為LR-GR 算法求解算例5過程中的相對誤差隨迭代次數的變化。可見,由于LR-GR算法的松弛解可行化方法的精度較高,迭代初期就能以較快的速度收斂至相對較低的誤差(以低于30的迭代次數達到接近10%的相對誤差)。因此,管理者可以根據實際的優化決策需求在保障一定求解精度的同時適當減少迭代次數和計算時間。

圖3 LR-GR 算法相對誤差隨迭代次數的變化

為了進一步驗證VUCOP 中關鍵參數的改變對于系統整體運作策略以及相應指標的影響,以算例8的網絡為基礎,在保持其他參數取值不變的情況下將無人機的電量等級總數由10增長至30,以觀察總成本和各部分成本的變化情況,其實驗結果如表2所示。需要說明的是,這里假設無人機續航能力(即最大載電量)提高的同時不改變其載重和續航能力等性能。在實際應用中,企業可以通過購買續航能力更高但其他性能維持不變的同系列不同型號的無人機,這也符合相關行業中電力巡檢的管理運營需求。

表2 系統運行各指標隨無人機電量等級總數的變化

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

5 結論

針對目前“一對一”模式下車載無人機電力巡檢系統對無人機和保障車利用率低的問題,結合電力巡檢任務范圍大,任務點分布稀疏的特點,以提升系統運行效率、靈活性和經濟性為目標,提出基于時空網絡的“多對多”車載無人機協同作業優化決策方法。研究成果為解決軸輻式雙層網絡下多主體協同優化決策問題提供了新方法,從無人機與車輛協同作業研究方向上進一步拓展了VRP-D的相關研究,對于車載無人機系統在電力巡檢中的進一步推廣和提升電力巡檢的自動化和智能化水平具有實踐指導意義。研究成果的創新之處可具體歸納為:

(1) 根據無人機電力巡檢的相關技術背景,通過調研相關行業目前在無人機電力巡檢實際運作中遇到的問題和關鍵需求,提出了車載無人機電力巡檢系統的作業模式,為未來的無人機電力巡檢的實踐管理提供理論支撐。

(2) 針對車載無人機電力巡檢協同作業優化問題,提出基于時空網絡的無人機與保障車協同路徑優化方法,將電力巡檢過程中的天氣和交通狀態等決策要素整合到時空網絡構建和時空路徑生成機制中,簡化了模型的形式。

(3) 為精準刻畫無人機巡航能力限制對系統決策的影響,在時空網絡的基礎上增加了無人機電量維度,避免在構建電量限制約束時出現非線性結構,進一步提高模型的可解性。

(4) 根據VUTIS中保障車和無人機作業方案的時空關聯特性,在LR 算法框架的基礎上提出LR-GR 算法,以兼顧單步迭代的計算效率和求解質量,并通過與CPLEX 求解器的對比驗證了優化算法在解決實際規模問題上的有效性。

此外,本文還通過敏感性分析實驗研究了無人機電池總載電量對于VUTIS運作策略和運行成本的影響,并得到了一些重要的管理啟示。例如,雖然無人機電池最大載電量的提高能夠節省無人機和保障車的派遣數量,降低固定成本,但又會提高每架無人機和每輛保障車的使用效率而在一定程度上提高行駛成本。由于無人機和保障車的行駛成本均遠小于各自的固定派遣成本,所以總成本仍然會下降。但這種下降趨勢也會隨著最大載電量的不斷增加而趨于平穩。由此可知,在系統建設和設備采購階段可以通過選擇續航能力更強的無人機而適當減少無人機的采購數量,但過度追求長續航的無人機必然會提高單架無人機的采購成本,最終導致系統運營總成本過高。

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