宋璟毓，蕭 衛(wèi)，賈建龍，趙振宇

（1.中國船舶工業(yè)系統(tǒng)工程研究院，北京100094；2.海豐通航科技有限公司，北京100070；3.92950部隊，遼寧葫蘆島125100）

航母等大型載機水面艦艇區(qū)別于其他常規(guī)艦艇的一大顯著特征在于，其所配置的廣闊甲板可作為提供艦載機起飛、著艦以及各項保障作業(yè)的平臺，從而拓展了母艦的三維立體作戰(zhàn)能力。然而，由于甲板空間狹小，各型艦載機的甲板航空保障作業(yè)也面臨著諸多挑戰(zhàn)：一是安全風險較大，航空保障作業(yè)過程涉及的“油電氣液”等安全風險源較陸地機場更為集中；二是參與保障的資源繁多，協(xié)同性較強。其中，較為突出的是保障人員和保障設備的協(xié)同保障組織管理難度較大；三是保障作業(yè)過程約束復雜。對此，須綜合考慮甲板航空保障作業(yè)的特殊環(huán)境。基于模型驅動的方法設計面向效能的航空保障作業(yè)流程，可以實現(xiàn)機群安全、協(xié)調、高效地進行甲板出動回收作業(yè)，從而提升機群的出動架次率和作戰(zhàn)能力。

美軍航母經(jīng)過幾十年的實踐經(jīng)驗，歸納總結了NATOPS標準化作業(yè)手冊，提出了甲板航空保障流程的總體流程和作業(yè)規(guī)范，但該框架無法面向任務進行流程優(yōu)化[1]。蘇析超等[2]針對多機機務保障流程中保障組分配問題，提出了基于改進混合差分進化算法的調度方法；進一步針對一站式保障模式下多資源協(xié)同調度問題，設計了一類Memetic優(yōu)化算法[3]。文獻[4]針對甲板航空保障作業(yè)的串并行混合特性，構建了拓展柔性作業(yè)車間調度模型進行優(yōu)化求解。文獻[5]在以上基礎上，考慮了單機機組模式、大機組模式和一體化聯(lián)合保障模式等不同保障模式對調度管理的影響，并驗證了一體化聯(lián)合保障模式的優(yōu)越性。Ryan等[6]建立了艦載機作業(yè)的混合整數(shù)線性規(guī)劃模型，并將基于線性規(guī)劃的方法和基于人工經(jīng)驗的調度規(guī)則進行了對比分析。Qi等[7]針對大規(guī)模調度中存在操作規(guī)程和經(jīng)驗知識表示難、復雜約束處理難且規(guī)劃耗時等問題，提出了基于層次任務網(wǎng)絡的甲板航空保障任務規(guī)劃方法。此外，針對保障過程中的時間不確定性，文獻[8-9]分別從隨機不確定和區(qū)間不確定兩類描述形式進行度量；而針對保障過程中的隨機故障等較大擾動，文獻[10-11]分別采用滾動時域規(guī)劃和完全重規(guī)劃的方法進行干擾管理。

在調度優(yōu)化算法設計方面，相關研究成果涵蓋了遺傳算法[5]、差分進化算法[12-13]、Memetic算法[3]、粒子群算法[14]、禁忌搜索算法[15]、遺傳和聲混合算法[16]等。以上算法主要以基于種群的智能優(yōu)化算法為主。該模式相對于面向單解的局部搜索算法，由于種群個體間的相互作用，難以在程序上實現(xiàn)并行運算，時效性較差，因而也限制了其在工程實踐中的應用。

以上研究主要針對甲板航空保障調度問題開展，而航空保障作業(yè)優(yōu)化具體包括工序路徑的選擇、資源的分配以及時序的規(guī)劃3個層面，調度僅是流程優(yōu)化中的一部分。本文基于單解的貪婪隨機自適應搜索算法（Greedy Randomized Adaptive Search Procedure，GRASP），對甲板航空保障作業(yè)流程進行優(yōu)化研究，為艦載機智能保障的工程實踐提供理論和方法支撐。

1 甲板航空保障作業(yè)流程優(yōu)化建模

甲板航空保障作業(yè)流程優(yōu)化問題（Aviation Support Operation Processes Optimization on Deck，ASOPOD）可以描述為：給定Nf架待保障的艦載機，機群集合表示為I={1,2,…,Nf}，各艦載機按時刻Zi入場至指定停機位并開展保障作業(yè)，各艦載機i的保障工序集為Ji，對應機群的保障工序集為J，單機保障作業(yè)流程并非固定的網(wǎng)絡流結構[5]，局部工序之間由于存在安全性或空間的限制而不能并行作業(yè)，且相互間的前后順序未定，即定義Vi表示i機不能同步作業(yè)的工序對集合；其余工序則按照既定的保障工藝順序進行作業(yè)，即定義i機j道工序Oij當且僅當其前序工序集Pij保障結束后方可開始，其工時為dij。各工序的保障還需相應的保障人員、保障設備和供給類資源，分別定義保障人員、保障設備和供給量資源類別集合為Kp、Ke和Kw。ASOPOD的目標即為在滿足甲板航空保障作業(yè)的各項約束前提下，通過優(yōu)化各工序的作業(yè)流程、時序計劃和資源分配，使得機群高效快速地完成甲板保障作業(yè)任務，即最小化保障完工時間Cmax。

1）Sij為工序Oij的保障開始時間；

2）Eij為工序Oij的保障完成時間；

基于以上所述，建立ASOPOD的數(shù)學模型如下。

選取調度優(yōu)化目標為最小化機群保障完工時間：

約束模型包括：

式（2）為入場保障時間約束，即飛機需入場系留后方可開展各項保障作業(yè)；式（3）為具有緊前緊后順序約束的時序關系；式（4）為分配至相同保障資源的作業(yè)優(yōu)先級關系，即占用相同人員或設備下，優(yōu)先級高的工序先進行保障；式（5）為不可并行作業(yè)的工序時序約束；式（6）為保障設備對應保障工序的覆蓋范圍約束；式（7）為供給類資源的供給能力約束，即任意時刻可供保障的飛機數(shù)量有限；式（8）、（9）分別確保保障人員和設備的分配量與工序對資源需求量一致。

2 基于GRASP算法的流程優(yōu)化方法

本文采用基于單解的GRASP算法對調度優(yōu)化模型進行求解。該算法是一類多步啟動的迭代優(yōu)化算法，每一次迭代循環(huán)包括2個核心步驟：一是在構造階段生成可行的初始解；二是在鄰域搜索階段對初始解進行局部擾動尋優(yōu)，并采用貪婪選擇保留最優(yōu)解。

應用至本文問題中，采用工序列表編碼形式，GRASP算法的迭代過程如表1所示。

表1 GRASP算法結構Tab.1 Structure of GRASP algorithm

算法包含一組精英集EliteSet，用于保留搜索過程所獲得的相異的最優(yōu)解集；在構造初始解階段，一個新的解將從精英集中通過一定機制BuildActList（*）進行組合生成；其次，在鄰域搜索階段，通過搜索機制LocalSearch（*）進行鄰域擾動并改進新解；最后，通過串行調度機制[3]將編碼轉換為具體的調度方案，如果新解的目標函數(shù)優(yōu)于精英集中的最劣解，則用該解進行替換并更新精英集，假設精英解集的規(guī)模為Ne，并維持不變。

首先，在構造初始解階段，構造過程如表2所示，從前至后依次選擇工序構造完整的長度為No的工序列表。定義每個調度階段的EligibleSet為滿足緊前工序約束的可調度工序集合，精英解復制鏈長為nit，其選取范圍為[nit_min，nit_max]。

表2 初始解構造階段Tab.2 Stage of initial solution construction

在每一步選取工序過程中，當鏈長nit為0時，則由函數(shù)SelectSolution（*）選取一個參考對象reference用于指導工序的選擇，其可以是某個優(yōu)選規(guī)則或工序列表解，本算法中的優(yōu)先規(guī)則選取完全隨機規(guī)則random和基于后悔值偏好的隨機采樣RBRS。若reference為工序列表解，則隨機選取復制鏈長nit按照EligibleSet在工序列表解中位置進行選取工序；否則，當reference為優(yōu)選規(guī)則時，則根據(jù)對應規(guī)則從Eligible-Set中選取工序，最終輸出完整的工序列表。

具體函數(shù)SelectSolution（*）的實現(xiàn)過程如表3所示，其中，pRandom、pRBRS分別為選中隨機規(guī)則和RBRS規(guī)則的概率，通常取較小的數(shù)值，用于對所選擇的精英解進行小范圍的隨機擾動，以增強搜索的多樣性。

其次，在鄰域搜索階段，主要對所構造的解進行進一步地局部優(yōu)化，為增強搜索的高效性，選擇雙向對齊（Double Justification，DJ）[17]進行局部調整，可保證更新解不劣于初始解。

具體執(zhí)行過程如下：首先，根據(jù)初始解的工序列表按正向串行調度機制進行時序調度和資源分配[3]；其次，根據(jù)各工序的完工時間，按照越大越優(yōu)先的規(guī)則，采用反向串行調度，按流程逆向從后向前排程；依此順序，不斷進行正向和逆向的交替調度，使得時間得到最大程度的壓縮，直到正向調度方案沒有提升，并輸出最優(yōu)改進解。

表3 參考對象選擇函數(shù)Tab.3 Selection function for reference

3 機群保障流程優(yōu)化案例仿真

艦載機的甲板航空保障項目一般包括充氣、加油、通電檢查、外觀機務檢查、彈藥掛載、慣導對準等項目，具體的通用化單機航空保障作業(yè)流程如圖1所示，共包含19道工序。其中，可變因素包括15號工序，其可位于3號工序前、16/17并行工序前或18號工序之后，且15、3、5、7和12號工序任意兩者之間均不能同步作業(yè)，因而其作業(yè)順序可變。1和19號工序分別為虛擬開始和虛擬結束工序，無實質內容。其余工序右側的Kpk和Kek分別表示該工序對第k類保障人員和設備存在需求，且需求量均為1，供給類資源與保障設備存在一一對應關系，即第k類設備存在需求時對應需要第k類供給量資源的保障。

仿真案例：選擇某典型航空保障任務A，需要出動12架艦載機并執(zhí)行飛行前的航空保障作業(yè)。各飛機對應各項保障工序的作業(yè)工時以及各飛機的入場系留完成時間如表4所示，其中1和19號虛工序無工時意義。

甲板航空保障資源配置方面，考慮保障設備均為固定類資源站，各類站點對應艦載機的覆蓋關系如表5所示。供給性資源可同時保障艦載機數(shù)量分別為[6，5，2，4，2]，4類保障人員配置數(shù)量分別為[5，5，8，10]。

圖1 通用化的單機航空保障作業(yè)流程Fig.1 General support process flow chart of single aircraft

表4 航空保障作業(yè)工序工時Tab.4 Durations of aviation support operation

表5 保障設備對應艦載機覆蓋關系Tab.5 Coverage relationship between equipment and aircraft

采用Matlab 2017對基于GRASP算法的甲板航空保障作業(yè)流程優(yōu)化方法進行編程實現(xiàn)，其中GRASP算法的相關參數(shù)設置為：復制鏈長的下界和上界分別為nit_min=1，nit_max=30，規(guī)則選擇概率pRandom=0.05，pRBRS=0.95。最大流程優(yōu)化生成評價次數(shù)取NSmax=10 000。

為了進一步體現(xiàn)改進GRASP算法的性能，選取該類問題抽象得資源受限項目調度問題的改進粒子群算法IPSO[18]，多模態(tài)遺傳算法MMGA[19]和混合分布估計算法HEDA[20]作為對比，其各自算法的參數(shù)設置參見文獻[8]。分別在同等條件下，對各算法獨立運行10次，所得計算結果如表6所示。

表6 算法對比結果Tab.6 Contrast results of algorithms

本文的GRASP算法在多次運算中均穩(wěn)定收斂至最優(yōu)值65，其尋優(yōu)性能最佳，且算法魯棒性最好。相比其他算法性能排序為：HEDA＞IPSO＞MMGA。其中，HEDA和IPSO算法均應用了雙向對齊機制，尋優(yōu)性能優(yōu)于MMGA。GRASP算法在初始解構造階段中就通過規(guī)則和精英解復制鏈長的機制有效地實現(xiàn)了開發(fā)和探索的融合，并進一步引入雙向對齊機制，從而更有效地提升解的質量，具備更高的尋優(yōu)性能，也更適用于求解甲板航空保障作業(yè)流程優(yōu)化問題。

圖2、3分別為由GRASP算法求解得到的最優(yōu)保障流程下保障人員及設備工序分配和時序方案。

圖2 保障人員工序分配及時序圖Fig.2 Schedule and operation allocation of support personnel

圖3 保障設備工序分配及時序圖Fig.3 Schedule and operation allocation of support equipment

4 結論

甲板航空保障作業(yè)流程優(yōu)化是關系到航母艦載機作戰(zhàn)力和保障力生成與生長的核心樞紐，屬于保障領域的一類特殊運籌優(yōu)化問題。在分析甲板航空保障作業(yè)流程優(yōu)化內涵的基礎上，以保障作業(yè)完工時間最小化為優(yōu)化目標，考慮了甲板作業(yè)過程中所涉及的各類約束情況，構建了甲板航空保障作業(yè)流程優(yōu)化的數(shù)學模型，并設計了相適應的GRASP算法。通過典型保障任務的仿真案例分析，驗證了GRASP算法在求解該類問題的全局搜索能力和魯棒性，并通過甘特圖的形式展示作業(yè)流程的具體執(zhí)行計劃，并可檢驗模型的有效性。下一步，可以考慮研究算法在動態(tài)不確定環(huán)境下并行高效調度決策中的應用，以提升動態(tài)調度的時效性。