基于旅行商路徑與任務指派的風力發電設備檢修問題研究

鄧 佳，譚代倫

風能是一種具有無污染、分布廣泛、可循環利用等優點的可再生資源［1］，風能發電在我國發電系統的占比呈逐年上升趨勢［2］.其中，維護風力發電設備正常運行、保持較高的日均發電效率［3?4］，是風力發電運營公司日常需要解決的重要問題.

當風力發電設備數量較多時，電力運營公司不得不組織一定數量的檢修小組，依靠合適的運輸工具將檢修小組送達故障設備處完成檢修任務.對一批待檢修的風機故障任務，是否能及時有效地完成，對公司降低成本、提高效益具有重要作用.為此，在風力發電設備的故障檢修過程中，存在著運籌學領域中的優化問題，對其進行研究，對電力公司的高效運營和維修具有較強的理論與實踐意義.

該類問題不僅包含了沿某種路徑完成維修小組的運送，還包括了根據人員特性和故障需求進行合理的任務指派，前者更具有TSP問題［5］的特征，后者則比較符合運籌學中的AP 問題的特征［6］，因此它屬于這兩類基本運籌學問題復合而成的組合優化問題.由于設備數量多、場地面積大，這類復合型問題尤為突出，在其他領域也有類似情況.

對此，國內外學者展開了相關研究.在國外，TANG 等［7］于2007 年利用禁忌搜索算法求解了一類帶時間依賴的計劃調度問題.BAYS等［8?9］利用運籌學知識研究了一艘母艦攜帶一定數量的、帶有不同特定任務的無人小艇在某一片海域進行施放或回收作業問題.RASHIDNEJAD 等［10］研究了將維護調度與車輛路由相結合問題并利用遺傳算法求解.MOSAYEBI 等［11］提出了帶工作時間的TSP 問題，給出了數學模型并設計了啟發式搜索算法進行求解.目前，國內對該類問題的研究還較少.陳峰［12］研究了運籌學在整車物流智能調度決策支持系統的應用.袁瑋等［13］研究了運籌學在海上油田直升機智能航線規劃中的應用.周忠彬等［14］研究了運輸排程優化模型在海上批量傷員運送中的應用.

本文基于風力發電設備檢修場景，研究基于TSP 路徑與任務指派的MWPEP 問題，分析并建立數學模型，既拓寬了運籌學知識的應用，也對企業的經營管理具有較強的借鑒意義.

1 問題提出

在風力發電運營與管理的全過程，即使只考慮設備檢修環節，需要考慮的因素也比較多，為此需要對問題作一些必要的簡化，使問題具有基礎性和代表性.

①只考慮有一輛運輸工具的情形，它從固定的檢修中心出發，裝載上全部檢修小組及物資后，沿一定路線依次經過每一個待檢修的故障設備點，到達故障點后被指定的檢修小組馬上開始檢修工作，運輸工具則繼續前往下一個故障點，完成全部運送任務后回到起點.對每一個故障點，過且只過一次，以保證不遺漏也不重復.合理地規劃路線，將有利于盡早把檢修人員送達現場.

②對于檢修人員與故障設備，假設每一個設備點所出現的故障現象并不完全相同，成功檢修故障所需的時間也因而不同；另外，不同檢修人員對不同類別故障現象的檢修水平也各有不同，相應的每個檢修小組完成每一個故障設備的檢修時間也不完全相同.任務的指派規則是每一個檢修小組只承擔一個故障點的檢修任務，反之每一個故障點的檢修任務只被一個檢修小組完成.合理地進行故障檢修任務的指派，將有利于盡早完成全部的檢修任務.

綜合考慮運送與任務指派，問題的總體目標是規劃一條最優的運送路線和檢修小組的最優指派，使得全部檢修任務能盡早結束.其中，運輸工具的行進速度視為勻速，檢修小組對每一類故障現象的檢修時間可經統計或測試獲得.

基于以上問題描述，為完成風力發電設備的檢修任務，需要綜合運用基于TSP 問題的路徑規劃方法和AP 問題的任務指派方法，本文將其稱為基于TSP 路徑與任務指派的一類MWPEP 問題.

2 建立MWPEP 問題的數學模型

根據問題提出，MWPEP 問題的目標是要求盡早完成全部檢修任務，即使整體完工時間最短.容易發現，對任意一個檢修小組，它的檢修任務完工時間由兩個部分組成：一是運輸工具從檢修中心（即TSP 中0 號路徑點）出發將此檢修小組運送到達某個故障點所需的時間；二是到達故障點后檢修小組完成該故障任務檢修所花的時間.由于到達時間有先后，各個故障點檢修任務的完工時間有所不同，因此要使整體完工時間最短，則需使所有檢修小組的到達時間和檢修時間之和中的最大者盡量小.其中，到達時間由按TSP 問題特征進行路徑規劃的結果所決定，檢修時間由按AP 問題特征進行任務指派的結果所決定.

鑒于此，下面先給出必要的數學符號和變量，再基于TSP 問題和AP 問題分別從兩個方面進行分析和建模.

2.1 符號與變量

不妨設共有n個故障點，依次記為1，2，…，n，檢修中心記為0 號點，任意第i個點的坐標記為pi(xi，yi)，i=0，1，2，…，n，這里假設所有點均在一個平面內，而不考慮具體的山區或海上情形.運輸工具以勻速行駛，速度記為V0.共有n個檢修小組，任意第j個檢修小組完成第i個故障檢修任務的時間記為cij.

對所有路徑節點（包括設備故障點和檢修中心），設任意兩點之間的距離為dij，按歐式距離公式計算，公式為：

式中：i，j=0，1，2，…，n.

經過該段路程dij所花的時間為：

2.2 基于TSP 路徑與任務指派的建模

對MWPEP 問題，基于TSP 路徑與任務指派進行建模，主要是指在TSP 行走路徑基礎上考慮任務指派所形成的設備檢修時間的疊加.為此，不妨設任意一輪檢修設備及人員運送形成的TSP 路徑及任務指派的檢修小組如下：

式中：v0為0 號檢修中心，vi，ui∈{1，2，…，n}分別為不重復的任意一個設備故障點和任意一個檢修小組.

因此，各檢修小組被運送到設備故障點的到達時間和完成檢修任務的完工時間可沿路徑點依次計算，結果如表1 所示.

表1 基于TSP 路徑與任務指派的變量構造

借鑒基于路徑構建的TSP 問題的數學模型，記任意一條運送路徑為V={v0，v1，…，vi，…，vj，…，vn}，對應檢修小組的任意一個指派為U={u1，u2，…，ui，…，uj，…，un}，則MWPEP問題的數學模型（記為模型Ⅰ）可表示為：

上述模型的目標是使各個檢修小組的完工時間最大最小化，它依賴于運送路徑，也依賴于指派方案.此外由表1 可知，模型中運送到每一個路徑節點的到達時間TVi與前一個節點的到達時間TVi?1形成累加關系，在模型中也可以由遞推關系式表示為：

2.3 基于0-1 型決策變量的建模

TSP 問題的0?1 規劃模型 和AP 問題的模型均基于0?1 型決策變量進行建模，其優點是比較容易刻畫路徑節點被唯一經過、維修任務與檢修小組的唯一分配等對應關系，但這種對應關系無法體現出路徑節點被經過的先后順序，因此無法按表1 刻畫出每一個節點的到達時間，相應的檢修時間也無法累加進去.

基于此，除繼續采用關于TSP 路徑和任務指派的兩種0?1 型決策變量外，還將運送到達任意一個節點的到達時間也作為一組決策變量，并對其進行約束.

為此，設TSP 的路徑節點集為V={1，2，…，n}，待分配的任務集為U={1，2，…，n}.在節點集V中，0 為檢修中心，是出發的起始點，不分配檢修小組.問題的主要決策變量及定義如下：

Ti：運送到第i個故障點的到達時間.式中：i，j，k=1，2，…，n.

決策變量xij，yik仍然分別用于約束運送路徑和任務指派關系的生成，結合變量Ti可表示檢修任意第i個設備故障點處的完工時間為：

式中：cik為第k個檢修小組對第i個設備故障點的檢修時間.

根據AP 問題的基本約束，對于任意i，決策變量組{yi1，yi2，…，yin}必只有一個取值為1，因此式（1）就是任意第i個設備故障點處的到達時間和檢修時間之和，即第i點的完工時間.

于是，MWPEP 問題要使運送與檢修總體完工時間最短的目標可以表示為：

下面對Ti構建必要的約束，運送到第j個設備故障點的兩種情形如圖1 所示.

圖1 運送到達第j 點的兩種情形

由圖1（a）可知，當起點從0 號點出發時，必有

類似地，當最終從任意第i個設備故障點返回0 號起點時，必有

由圖1（b）可知，當從任意第i點向第j點運送時，必有

綜合TSP 問題、AP 問題的0?1 規劃模型，以及式（1）～式（4），可建立MWPEP 問題基于0?1 型決策變量的數學模型（記為模型Ⅱ）如下：

3 MWPEP 問題算例與模型分析

前面已經建立了MWPEP 問題的兩個數學模型，其中，模型Ⅰ的建模過程簡單直觀，可以通過列舉一個方案，描述清楚模型Ⅰ的可行解和目標函數值的形成過程.而對模型Ⅱ直接構建可行解，其目標函數值計算過程與模型Ⅰ相似，在此不再對模型Ⅱ進行舉例計算.在模型Ⅱ中，為刻畫到達節點的先后順序，構造了一組運送到第i個故障點的到達時間作為決策變量，下面對模型Ⅱ中構造的決策變量做詳細分析.

3.1 MWPEP 問題算例

現設需要維修的設備故障點有5 個，編號為1，2，3，4，5，起點記為0.為簡化計算，直接給出任意兩點之間的運送時間，不再給出距離矩陣和速度.相應地，檢修小組有5 個，編號記為A，B，C，D，E，給出任意設備故障點對應檢修小組的檢修時間，相關數據如表2 所示.

表2 MWPEP 問題算例的運送時間和檢修時間數據

注：表2 中任意兩路徑點之間的運送時間即為模型Ⅰ中的矩陣T=(tij)，指派給任意路徑點的檢修小組所對應的檢修時間即為模型Ⅰ中的矩陣C=(cik)，且表中時間數據的單位均為分.

3.2 基于算例對模型Ⅰ的分析

在模型Ⅰ中，首先規劃了一條TSP 運送路徑，然后在路徑的基礎上分配任務指派的檢修小組.其中，運送到達每個路徑點的時間與檢修小組完成工作需要的檢修時間之和，就是檢修此路徑點的完工時間.所有路徑點的檢修完工時間中最大值為最大完工時間，最大完工時間與運輸返回起點時間中較大者，即為目標函數值.

假設一輪運送路徑及任務指派的檢修小組為：0 →2(D) →1(C) →4(A) →5(E)→3(B)→0 記為方案1，參照表1 的計算公式可得出方案1 任意路徑點的到達時間、檢修時間和完工時間，如表3 所示.

表3 方案1 對應的變量取值

為更直觀理解表3 中數字的含義，繪制方案1 的運輸路線、指派方案及相應的時間，如圖2 所示.其中圓中數字為對應路徑點，長方形中字母和數字分別代表分配給對應路徑點的檢修小組及檢修時間，帶箭頭的線上數字為兩相鄰路徑點的運輸時間，圓形外面的數字為對應路徑點的到達時間.

圖2 方案1 的旅行路徑和檢修小組指派

從圖2 可以看出，從起點到路徑點3，需要依次經過路徑點2，1，4，5，到達路徑點3 的時間為41，此時檢修小組B 在路徑點3 執行檢修任務，所需檢修時間為11.所以，在路徑點3的檢修任務完工時間為到達路徑點3 的時間與檢修小組B 完成檢修任務所需時間之和為52.同理，在路徑點1，2，4，5 的檢修完工時間分別為26，19，35，46.運輸工具完成運送返回到起點花費的時間為51.所以，在這個方案中，所有路徑點的檢修完工時間和運輸返回起點所需時間中最大值為52，則方案1 的函數值為52.

通過對模型Ⅰ進行舉例說明，對MWPEP問題的決策變量和目標函數形成有了更清楚的認識.

3.3 基于算例對模型Ⅱ進行分析

在模型Ⅱ中，為了刻畫到達路徑點的順序，特別使用了運送到達任意一個節點的到達時間Ti作為一組決策變量，并對Ti的取值范圍進行約束，下面對方案1 中到達時間的約束作進一步分析，現設變量xij的取值如表4所示.

表4 MWPEP 問題方案1 對應變量xij 的取值

從表4 可以看出，當從0 號點出發到達第一個路徑點為2 號路徑點，此時

從起點出發到達除路徑點2 的任意節點都會經過路徑點2，則對除路徑點2 的任意路徑點滿足Ti>T2，i≠2.所以，對除起點外任意路徑點滿足式（2），當且僅當i為從0 號點出發到達的第一個路徑點時取等.

同理，返回0 號點有兩種情況.返回0 號點前到達的最后一個路徑點為3 號點，那么到達3 號點的時間為運送花費總時間與從i點到0 號點所需時間之差，即

對除3 號點的任意路徑點，需要經過路徑點3 才能返回起點，故Ti

綜上，對除起點外任意路徑點i的到達時間的取值范圍滿足8 ≤Ti≤41，i=1，2，3，4，5，即

經過路徑點i到達路徑點j有兩種情況，第一種情況是從路徑點i可直接到達路徑點j，第二種情況是從路徑點i需要經過若干個路徑點才能到達路徑點j.若j點為4 號點，i點為1 號點，則從1 號點可直接到達4 號點，滿足

若i點為2 號點，從2 號點需要經過1 號點才能到達4 號點，此時T2=T1?t21

通過對模型Ⅱ到達時間變量的約束條件進行分析，對約束條件的構造過程更加容易理解.

4 結語

本文研究了風力發電設備檢修場景內的一類設備檢修問題.通過對問題做適當簡化，給出了基于TSP 路徑與任務指派的MWPEP 問題.同時以TSP 問題和AP 問題的數學模型為基礎，一方面，在TSP 路徑的基礎上，把指派所形成的檢修時間疊加，構造目標函數值，建立數學模型；另一方面，借鑒TSP 問題和AP 問題的0?1 規劃模型，刻畫到達每個節點時間作為一組決策變量，并限制其取值范圍進行建模.MWPEP 問題的提出，擴寬了運籌學知識的應用，同時，MWPEP 問題數學模型的建立，為今后使用智能算法求解此類問題奠定了基礎.