基于蟻群算法的艦載直升機維修資源優(yōu)化調(diào)度研究*

李軍亮 滕克難 衣冠琛 劉國桓

(1.海軍航空工程學院 煙臺 264001)(2.92514部隊 煙臺 264007)

基于蟻群算法的艦載直升機維修資源優(yōu)化調(diào)度研究*

李軍亮1滕克難1衣冠琛1劉國桓2

(1.海軍航空工程學院 煙臺 264001)(2.92514部隊 煙臺 264007)

針對艦載直升機遠航時駐艦周期長、維修任務時間緊、資源有限的特殊性，合理構建艦載直升機駐艦維修模型，建立艦載直升機駐艦維修資源優(yōu)化調(diào)度模型，采用改進蟻群算法進行仿真計算，通過計算驗證表明：該算法較好的解決維修過程中出現(xiàn)的資源沖突問題，縮短艦載直升機維修工期。

艦載直升機; 維修保障; 資源調(diào)度; 蟻群算法

Class Number V241

1 引言

隨著藍色海軍戰(zhàn)略轉型的不斷深入，海軍執(zhí)行遠洋任務日益頻繁，艦載直升機能夠擔負偵察、搜救、運輸、反潛等多種使命，其作用更加突出。但艦載直升機的使用仍受到多方面因素制約，一方面由于目前艦載直升機駐艦保障仍然沿用岸基“基層級”、“中繼級”和“基地級”的三級保障體制，艦船空間有限不能攜帶較多的航材備件，維修資源相對受限；另外遠航時艦載直升機駐艦周期長、氣候環(huán)境惡劣，執(zhí)行任務具有突發(fā)性和應急性，裝備故障率高且故障出現(xiàn)時間具有不確定性[1]。那么如何通過對維修資的源優(yōu)化調(diào)度來解決維修保障過程中出現(xiàn)的維修保障資源分配不均、計劃不周、預測不準等問題，充分利用現(xiàn)有維修資源，縮短待修直升機維修周期，提高維修資源利用率，在短時間內(nèi)恢復戰(zhàn)斗力，最大限度地保證直升機完好率，順利執(zhí)行各項任務已經(jīng)成為機務維修人員亟待解決的重大課題。

資源受限項目調(diào)度問題(resource-constrained project scheduling problem,RCPSP)，要求在滿足項目任務的緊前關系和資源約束的條件下，優(yōu)化項目的進度安排，從而優(yōu)化最小項目目標函數(shù)。RCPSP算法主要分兩種：精確算法和啟發(fā)式算法。精確算法包括整數(shù)規(guī)劃、分支界定法、動態(tài)規(guī)劃法等。由于RCPSP是NP-hard問題，對于較復雜的項目，在可以接受的時間范圍內(nèi)，精確算法難以得到最優(yōu)解。相對而言啟發(fā)式算法不能保證得到最優(yōu)解，但能夠較快地找到較好解。各類啟發(fā)式算法是近年來的研究熱點，目前的研究主要集中于遺傳算法、模擬退火、禁忌搜索以及蟻群算法[2～3]。筆者根據(jù)艦載直升機有限資源維修問題的特殊性，采取蟻群算法進行優(yōu)化實現(xiàn)，基于復雜的參數(shù)設置，得到較好的結果。

2 艦載直升機駐艦保障維修資源分析

艦載直升機維修資源是指與艦載直升機維修直接關聯(lián)的維修經(jīng)費、維修物資器材、維修設施設備、維修人才、維修信息以及維修管理等有形和無形的資源[4]。而在實際工作中只考慮以實物形式存在的艦載直升機維修資源，即維修物資器材、維修設施設備和維修人才。

根據(jù)實際工作情況，艦載直升機的駐艦維修是由隨艦保障的地勤人員來完成，維修工作按照機械、特設、電子、軍械和聲納五個專業(yè)進行劃分，如果多專業(yè)同時進行項目維修，就可能會產(chǎn)生資源沖突，每個維修項目的工作進度都會受到影響，就容易造成整體維修工期拖后的現(xiàn)象，要合理解決資源沖突，有效利用關鍵資源，有序分散的并行進行維修項目，保證多項目、多工序交叉進行和推進，就勢必要對維修資源進行優(yōu)化調(diào)度。

多專業(yè)多項目維修工作并行開展時要考慮維修任務中維修項目所需的資源配置，再根據(jù)各個專業(yè)的分工職能，對所屬專業(yè)項目的維修資源進行調(diào)配。直升機維修工作是一個復雜的系統(tǒng)工程，各專業(yè)并行作業(yè)時存在制約和關聯(lián)，各專業(yè)內(nèi)部工序可在滿足緊前約束的前提下串聯(lián)進行。文獻[5]在資源受限模型建模時引進維修單元重要度的概念來確定工序前后順序的優(yōu)先策略。具體表現(xiàn)為實際維修工作中維修項目的重要性和蟻群算法中信息素的揮發(fā)系數(shù)聯(lián)系起來，即維修項目重要度和信息素揮發(fā)系數(shù)成反比關系，這樣的計算結果更貼近實際維修工作。

筆者結合目前艦載直升機駐艦保障的實際情況，對在艦面可完成的實際維修項目進行編碼，規(guī)則如下：

按照目前的維修方式將直升機維修工作劃分為機械專業(yè)M1，特設專業(yè)M2，軍械專業(yè)M3，電子專業(yè)M4，聲納專業(yè)M5，各專業(yè)維修項目按照工作順序編碼，各維修項目完成需要的時間用矩陣D表示。

(1)

其中，矩陣中的列分別表示專業(yè)，矩陣中的行表示專業(yè)的維修項目。dij表示第i個專業(yè)的第j個維修項目的工作時間。確定每個項目dij的優(yōu)先策略時，首先要滿足緊前約束，其次參考重要度函數(shù)θj，θj如式(2)所示：

(2)

3 艦載直升機維修優(yōu)化調(diào)度模型的建立

由于艦載直升機維修任務比較特殊，不僅具有較高的并發(fā)性，還有關鍵資源的制約。那么一個維修項目可以表示為一個節(jié)點式(activity-on-node,AON)有向網(wǎng)絡[6]，并存在兩類約束：一類是任務之間存在的邏輯約束，用AON網(wǎng)絡中的箭頭表示；另一類是有限資源造成的資源約束，限定同一時刻各任務對資源的需求不能超過資源的供給。假設項目包含j個任務，需要k種可更新資源,其中第k種資源的供給量為Rk。項目的第j個任務，其工期為Pj，截止日期為dj對第k種資源的需求量為rjk，其所有緊前任務的集合記為Pj，任務的開始時間標記為Sj，結束時間標記為Cj，項目從t=0時刻開始執(zhí)行,設定最晚完工時間為T=∑Pj；在時間t所有進行中任務的集合標記為It，可以用任務結束時間向量表示一個項目進度計劃S=(C1,C2,…,Cj)。因此，RCPSP可以描述為

minf(s)

(3)

s.t

Sj≥Ch,?j,h∈Pj

(4)

∑j∈Itrk≤Rk,?k,t

(5)

式(3)表示項目的目標函數(shù)，式(4)表示任務之間的緊前關系，式(5)表示資源約束。對于經(jīng)典RCPSP問題，目標是最小化項目總工期。

4 蟻群算法設計

蟻群算法是對螞蟻群體利用信息素進行覓食行為的仿生，已經(jīng)被廣泛應用于各種組合優(yōu)化問題，以及應用于求解RCPSP[7～8]。一般而言，蟻群算法采用進度生成機制，通過逐步擴展局部進度計劃來生成一個完整可行的項目進度計劃，并通過反復搜索獲得最優(yōu)解。

(6)

式中：τij為信息素信息，ηij為啟發(fā)式信息,α和β為控制兩類信息權重的參數(shù)。啟發(fā)式信息一般表示螞蟻在搜索決策中可以利用的直觀信息。在RCPSP中，一般用優(yōu)先規(guī)則來構造啟發(fā)式信息，最常見的是最遲完工(late finish，LF)時間，記任務j的最遲完工時間為Lj，則啟發(fā)式信息可以表示為

(7)

信息素的更新是蟻群算法的重點，包括信息素的揮發(fā)和累積。鑒于艦載直升機維修工作的特殊性，本文將ρ的變化為與重要度函數(shù)θj成反比的函數(shù)，各條路徑信息素更新如式(8)所示：

(8)

Δτij(g)=ρ/f

(9)

式中：ρ為信息素的揮發(fā)率，f為螞蟻在完成一次完整的搜索后得到的目標函數(shù)值。當螞蟻k從第1個任務逐步搜索到第j個任務時，就構成一個完整的任務列。以該任務列的順序，在滿足資源約束的前提下，按照盡早原則逐個安排所有任務的開始時間，就得到一個可行的項目進度計劃。

5 算例分析

蟻群算法是一種自適應、正反饋、分布式的模擬優(yōu)化計算法，它在求解各復雜的組合優(yōu)化問題上表現(xiàn)出一定優(yōu)勢，較好的α，β有較好的解質(zhì)量以及好的穩(wěn)定性，但如果對蟻群參數(shù)選擇不當，蟻群算法較快收斂到局部最優(yōu)或較慢的收斂，對算法有極大地影響。文獻[9～10]利用大量數(shù)據(jù)分析了α，β參數(shù)不同組合得到的算法性能。在0.1≤α≤0.3，3≤β≤6的些范圍內(nèi)，算法總體上有較好的性能，到達的最優(yōu)解與全局最優(yōu)接近，同時，所需的迭代次數(shù)也較少，不易陷入局部最優(yōu)，導致算法停滯。本文算法中控制參數(shù)取值如表1所示。

表1 計算參數(shù)的選擇

假設艦載直升機在執(zhí)行某次任務后，部分裝備受到損傷，再次出動需要對5個專業(yè)9個項目維修，如表2所示。

表2 維修項目、時間及保障重要度

根據(jù)以上假設和優(yōu)化目標，采用蟻群算法用Matlab編程計算結果如圖1所示。

圖1 最佳路徑和最短工時

假設條件數(shù)據(jù)不變，應用其它算法求解本例，得到計算結果如表3所示，可以發(fā)現(xiàn)本文所述算法求解結果基本優(yōu)于其他算法，其求解時間對比顯示：本文求解時間小于其它算法，基本適用于應急保障資源調(diào)度對決策時間的快速要求。

表3 計算結果的比較

6 結語

該模型可以計算出艦載直升機在有限資源情況下保障維修的最短工時和最優(yōu)工序，能夠提高維修效率，從而提高艦載直升機的完好率。本文在計算維修任務的重要度時只考慮了三個影響因素，為了更切近實際保障工作，可以全面研究各種影響因素，確定更為合理的維修工序。

[1] 張鑫,金超.基于蟻群算法的艦船維修資源優(yōu)化調(diào)度[J].兵工自動化,2011,30(11):1-35.

[2] 壽涌毅,傅奧.多目標資源受限項目調(diào)度的多種一群算法[J].浙江大學學報,2010,44(1):51-55.

[3] 崔遜學.多目標進化算法及其應用[M].北京:國防工業(yè)出版社,2008:253-256.

[4] 李耀華,譚娜,郝貴和.飛機維修計劃優(yōu)化模型與算法研究[J].控制工程,2008,15(1):99-102.

[5] 孫寶琛,賈希勝.基于蟻群算法的維修資源應急調(diào)度研究[J].研究與設計,2012(6):37-41.

[6] 陳慶華.裝備運籌學[M].北京:國防工業(yè)出版社,2007:85-89.

[7] Merkle D, Middendorf M, Sch Meck H. Ant colony optimization for resource constrained project scheduling[J]. IEEE Transactions on Evolutionary Computation,2002,6(4):333-346.

[8] Mazzeo S, Loiseau I. An ant colony algorithm for the capacitated vehicle routing[J]. Electronic Notes indiscrete Mathematics,2004(8):181-186.

[9] 蔣玲艷.蟻群算法的參數(shù)分析[J].計算機工程與應用,2007(20):31-36.

[10] 黃翰,郝志峰,吳春國.蟻群算法的收斂速度分析[J].計算機學報,2007,30(8):1344-1353.

Optimal Scheduling of Shipboard Helicopter Maintenance Resource Based on Ant Colony Algorithm

LI Junliang1TENG Ke’nan1YI Guanchen1LIU Guohuan2

(1. Naval Aeronautical Engineering Institute, Yantai 264001)(2. No. 92514 Troops of PLA, Yantai 264007)

According to the particularity of the maintenance of shipboard helicopter with constrained resource and time limited, the optimized scheduling model of shipboard helicopter maintenance resource is put forward. By using the ant colony algorithm, the simulating calculation proves that the method uses the pheromone update to enhance search capability of ants to the optimal path, which solves the resource shortage problem well and reduces the maintenance cycle.

shipboard helicopter maintenance, resource constraint, optimized resources, shortest time, ant-colony-algorithm

2014年5月10日,

2014年6月23日 作者簡介:李軍亮,男,博士研究生,研究方向:飛行器動力學和航空裝備保障。滕克難,男,博士,教授,博士生導師,研究方向:武器裝備發(fā)展論證。衣冠琛,男,碩士,研究方向:航空裝備保障。劉國桓,男,工程師,研究方向:航空裝備保障。

V241

10.3969/j.issn1672-9730.2014.11.035