基于改進引力搜索算法的艦載機一站式保障作業優化調度方法?

朱興動 趙 洋 范加利 黃 葵

（1.海軍航空大學 煙臺 264001）（2.海軍航空大學青島校區 青島 266041）

1 引言

集大量高新技術成果于一體的航空母艦已經成為評價一支現代海軍作戰能力的核心要素，在其構建的海上大縱深，多層次的攻防體系中，艦載戰斗機扮演著一個重要的角色。而艦載機的數量及其出動能力也成為了衡量航母的綜合作戰性能的關鍵指標［1］。而航空艦面保障作業效率是影響艦載機出動回收能力的主要因素。制定高效可行的艦載機甲板作業度方案，對于提升艦載機艦面保障能力具有重要意義。

相關研究主要圍繞傳統的多站位保障與一站式保障兩種不同的保障模式展開，而一站式保障模式相較于傳統的保障模式極大地提升了保障效率，將會是未來航母所采用的主流保障模式［7］。一站式保障模式對艦載機保障作業的有序管理、分配提出了更高的要求，其中各項保障作業工序對保障資源的爭奪沖突消解問題，以及如何對各艦載機的保障工序進行合理規劃，避免再次出動準備各項保障作業間的相互干擾的問題尤為突出。但目前艦載機一站式保障調度的相關研究在以上兩個方面仍有所欠缺，因此，本文對一站式保障模式的作業流程、資源約束特性以及不同的出動模式下各類艦載機的放飛優先級進行了系統性地分析，建立了艦載機一站式保障調度模型，并設計了一種適用于求解大規模作業調度，消解資源沖突的改進GSA算法求解該模型。最后，通過對“福特”級航母的典型出動案例仿真驗證了算法的可行性和有效性。

2 模型建立

美國“福特”級航母首次引入了一站式保障模式的概念［8］，在飛行甲板右舷設置了18 個“一站式保障區”，所有“一站式保障區”的保障模塊都進行了系統化的集成設計，集中設置了油、氣、電、液等艦面保障設備。艦載機著艦并自主滑入保障站位后，按照作業流程有序開展機務勤務保障作業，主要包括添加燃油、補充氧氣、航電檢查、特設檢查、機械檢查以及軍械檢查等一系列工序，艦載機不需移動即可完成全部保障作業。一站式保障作業的節點活動網絡圖（Active On the Node，AON）如圖1。

2.1 模型假設

假設1：艦載機按照給定的保障流程進行，保障工序之間有串行、并行和柔性關系；

假設2：任意艦載機的保障作業，對其他艦載機工序的完成沒有影響；

假設3：進行再次出動準備作業的艦載機均滿足一站式保障條件，能夠在同一站位完成所有保障工序，不需調運；

假設4：保障人員的保障范圍均可覆蓋到全體保障站位；

假設5：航母的各類消耗性資源儲存總量充足；假設6：不考慮突發故障和其他干擾因素。

2.2 參數設定

I={1，…，i，…，n} ：I表示待保障艦載機機群集合，n為當前需要進行再次出動準備作業的艦載機架數；V={(i，j)|i?I，j?Ji} 表示甲板作業集，即所有要執行的工序，其中Ji={1，2，…，|Ji|}為艦載機i(i?I)的全部保障工序集合，| ? |為集合中元素的個數；TX={1，…，i，…，tx} 表示甲板勤務作業調度時間序列；Oij表示艦載機i的第j項保障工序；Hi表示艦載機i(i?I)的保障停機位；stij表示工序Oij的開始執行時間；edij表示工序Oij的結束時間；INit表示艦載機i(i?I)在t時刻處于保障作業狀態的工序集；Tij表示艦載機i(i?I)完成第j項保障工序的持續時間；Qi表示艦載機i(i?I)自主滑抵一站式保障停機位的時間；Wij表示Oij的緊前工序集合；Gp表示機務保障人員專業類型集合；Ge表示勤務保障設備類型集合；Gh表示保障工位空間類型集合；Gr表示航母甲板的供給性資源類型集合；Lrmk表示甲板的第k(k?Gr) 類供給性資源最多可同時維持Lrmk個固定保障設備的運轉；NS表示甲板一站式保障站位的數量。Npijk表示工序Oij所需的第k(k?Gp)類保障人員的數量；Neijk表示工序Oij所需的第k(k?Ge)類保障設備的數量；Nrijk表示工序Oij所需的第k(k?Gr)供給性資源的數量；NHik表示艦載機i(i?I)的第k(k?Gs)類工位空間可同時容納的機務保障人員數量；Lpk={1，2，…，|Lpk|}表示第k(k?Gp)類機務保障人員集合；Lek表示第k(k?Ge)類勤務保障設備；Wsij表示工序Oij的保障工位。

2.3 再次出動保障調度模型

甲板航空保障作業的調度起始點為一波次艦載機全部著艦并滑行至一站式保障站位。

2.3.1 目標函數

艦載機機群出動架次率是衡量航母作戰及綜合保障能力的常用指標［4，9］，而提高艦載機出動架次率的一個直接有效的途徑就是縮短單波次甲板機務勤務保障作業完工時間。

各類甲板資源中，對保障效能具有決定性影響的主要為機務保障人員和保障設備的配置數量及其工作性能［5］，最終體現在保障完工時間的變化上。因此，調度模型的指標函數取為最小化一波次艦載機機群再次出動保障作業時間，即最小化最大完工時間：

依據優化目標定義決策變量：

2.3.2 約束條件

1）機務保障人員約束。任意時刻所有保障作業對某類專業人員的需求量不得大于該類專業保障人員配置數量：

2）甲板勤務保障設備約束：

此外，若同一架艦載機的兩相鄰工序分配在同一個保障設備上，那么后續工序無需等待前一個工序結束即可開始保障：

3）保障工序流程約束：

艦載機各保障作業開始與結束的時序關系：

4）保障站位數量約束：

5）工位空間約束：

6）資源供給能力約束：

7）資源需求與分配約束：

8）艦載機起飛優先級約束：

3 GSA算法設計

保障作業調度優化的最終目標是最小化一波次保障作業的最大保障完工時間，該問題可以抽象為具有NP-hard 特性的資源受限多項目調度問題（Resource-constrained multi-project scheduling，RCMPSP）［8］，目前解決此類問題的方法主要有引力搜索算法（GSA）、粒子群優化算法（Particle Swarm Optimization，PSO）、遺傳算法（Genetic Algorithm，GA）等其他智能優化算法。研究表明，GSA 算法在優化調度［10］、數字辨識［11］等領域具有更好的簡潔性和實用性，其尋優精度和收斂速度對比PSO、GA 等算法具有相當的優勢［12］。因此，本文選取了GSA作為求解算法，但GSA 存在易早熟收斂，局部搜索能力差的問題［13］，故本文設計了一種改進的引力搜索算法（IGSA）來求解保障作業調度優化問題。IGSA的流程如圖2所示。其中δ2表示粒子適應度方差，c為判斷閾值。

圖2 IGSA算法流程圖

3.1 編碼與基于SSGS的解碼過程

3.1.1 編碼

由于艦載機保障作業調度問題是離散的［15］，考慮到本文所研究的調度問題中包含三個子問題，即工序排序、保障設備分配以及保障人員分配，所以引入了二元任務鏈表，即為滿足保障流程約束條件的作業序列編碼。它由兩部分組成，包括艦載機與工序。圖3 給出了一個可行的二元任務鏈表示意圖，其中第一行向量I表示艦載機編號，第二行向量J表示工序號，n、m表示艦載機機群所有工序數量。

圖3 艦載機保障作業調度編碼示意圖

3.1.2 解碼

根據資源需求生成調度方案需要利用調度生成機制（Schedule Generation Scheme，SGS）實現食物位置編碼向調度方案的映射。SGS 有串聯進度生成機制（Serial Schedule Generation Scheme，SSGS）和并聯進度生成機制［16］（Parallel Schedule Generation Scheme，PSGS）。

Krüger 在研究中指出，SSGS 是具有活動性的積極的調度計劃，而PSGS 生成的只是非延遲性的調度計劃，且不考慮有限性資源的分配問題［17］。對于求解多資源約束下的最小化最大保障時間的問題，SSGS 能夠較快搜索更為完整的解空間，鑒于此，本文基于SSGS生成調度方案，根據作業調度編碼映射到調度方案，輸出滿足時序關系和資源約束的優化調度任務鏈表，進而得到各保障工序的最大完工時間即目標函數值、人員和設備的調度方案及其作業時序。在此過程中引入資源沖突消解策略［18］來引導算法產生積極調度計劃。SSGS 以時間為階段變量，共有J 個階段。定義三個工序集合存在于在每一個階段g 對應的調度時刻tg中：已完成工序集（Complete group）表示為Cg；可調度工序集（Decision group）表示為Dg；執行工序集（Active group）表示為Ag。在任意階段g 中，引入了資源沖突消解策略和資源優先分配規則的SSGS算法包括以下步驟：

Step 1選取當前可調度工序集Dg中第一序列的工序，加入到執行工序集Ag中。為當前執行工序集中工序執行三層決策。

Step 2以Ag中當前執行工序的緊前工序的最大完成時間為時間變量的起始值，以1 個時間單位為步長向后步進搜索，直到某一時刻的保障人員、保障設備，工位空間以及消耗資源剩余量滿足當前執行工序對保障資源的需求量，將該時刻設定為當前執行工序的開始時間stij，結束時間edij=stij+Tij。

Step 3按照保障人員與保障設備的分配規則為當前執行工序尋找當前時間點中符合規則的人員與設備，將stij至edij時間序列中的與置為零。

Step 4更新保障人員、保障設備、剩余資源和站位空間的信息。

Step 5將當前執行工序加入到已完成工序集Cg中并從Dg和Ag中刪除，重復執行Step 1，直至可調度工序集合為空集，然后轉入下一階段，當Dg=?，調度完成。

3.2 粒子位置更新策略

通過先例保全交叉法（Modified Precedence Preservative Crossover，MPPX）對當前全局的粒子位置進行擾動［19］。首先產生一個長度為n 的隨機二進制矢量，其維數相當于任一粒子位置全部工序矢量的長度，用于選擇。粒子元素以生成新的粒子位置。其中0和1分別代表第一個和第二個粒子位置。這些數字代表元素從食物位置中移除并放入新粒子位置向量的順序。從左邊開始，根據隨機矢量的順序選擇一個元素，并從兩個食物位置矢量中移除，然后放入一個新的食物位置，直到兩個食物位置向量都為空。

其次，針對保障作業調度這種大規模RCMPSP問題難以跳出局部最優的特性，引入一種基于子拓撲工序網的變異策略［20］，以產生更大的鄰域變換范圍，防止算法早熟收斂，提高種群的多樣性。變異策略主要步驟如下：

Step 1在當前種群中按概率Pm 選取執行變異操作的食物位置向量集合，提取單一向量Re-Chrom執行步驟2；

Step 2在ReChrom 中隨機選擇一個操作點P?[1，|Ji|-len]，其中len 為重排子向量（即子任務鏈）的長度，選取P 至P+len 位的向量記為nC，并記錄P 和P+len 位在ReChrom 中位置LocP與LocP+len；

Step 3將nC 中的工序按照艦載機保障流程AON 圖的作業工序約束關系構造所選取子向量的AON 子圖，依照子圖的約束對子向量進行隨機重排；

Step 4用重排后的子向量（即子任務鏈）替代ReChrom 中[LocP，LocP+len]區間內的向量，構造出新的食物位置向量。

為進一步減少算法迭代的時間，提高算法收斂速度，在執行完交叉、變異擾動后，計算當前所有粒子的適應度值，并選取部分最優解作為初始解執行禁忌搜索［21］，算法主要流程如下。

步驟1接收初始解，作為當前解，將該粒子位置加入禁忌表；

步驟2創建當前解的候選解解集（鄰域解解集）；

步驟3在候選解解集中選擇目標函數值最優且不在禁忌表中的解，作為新的當前解；

步驟4新的當前解加入禁忌表，并更新禁忌表，判斷此時是否滿足終止條件，若是，則繼續執行下一步，反之則轉至步驟2；

步驟5輸出搜索到的最優解，即最優粒子位置。

4 仿真分析

4.1 案例構建

本文基于“福特”號航母甲板保障資源配置情況構建艦載機機群保障仿真案例，航母右舷的一站式保障區最多可停放20多架艦載機并能同時為18架艦載機提供各種保障，其中一站式保障站位編號分別為1～18，本文構建了一個艦載機機群雙周期連續出動保障案例，對8機和12機輪轉兩種出動模式進行調度仿真，表2 給出了不同作戰模式下的各類型艦載機的起飛優先權；作戰任務需求設定為預警機、電子戰飛機、空對地打擊戰斗機以及護航機。艦載機編號為1～12，只采用甲板的一站式保障區。任一艦載機i的單機保障工序流程如圖1所示，其中編號1 和編號19 為虛擬開始/結束工序。各保障工序對保障資源的需求和執行工序的時間參數情況以及保障設備的覆蓋范圍由于篇幅限制，未在文中給出。

表2 不同作戰任務下的艦載機起飛優先權

4.2 仿真結果

仿真案例采用的硬件平臺為Windows11 操作系統，Intel（R）Core（TM）i7-12700K CPU，3.61GHz主頻，32G 內存，Matlab R2022a 仿真軟件。經多次實驗對比分析，最終設定的算法參數為算法的種群規模N2=50，引力系數G0=50，粒子加速度α=10，遷移因子MF=15，變異概率Mutation（m）=0.2，交叉概率Crossrate（c）=0.2，貪婪搜索概率TSrate（s）=0.4，算法整體最大迭代次數T=300。

12 機輪轉模式下任務C 的最大保障完工時間隨下層迭代的曲線如圖4 所示。最終求解得到的任務C 的再次出動保障作業的保障人員和保障設備的最優調度方案如圖5 和圖6 所示。其中，橫坐標表示再次出動準備作業中一波次保障過程的時間軸，圖5 縱坐標Gpk-l代表第k 類專業中第l 個保障人員。圖6 縱坐標Gek-l代表第k 類第l個保障設備。

圖4 最大保障完工時間收斂圖

圖5 任務C的保障人員最優調度甘特圖

圖6 任務C的保障設備最優調度甘特圖

5 結語

針對一站式保障模式下艦載機保障作業調度問題，對艦載機再次出動保障任務的流程、保障資源約束進行了系統性的分析，建立了一站式保障調度優化模型，進而設計了一種改進的引力搜索算法用于該問題的求解。引入了融合資源沖突消解策略的串行進度生成機制來生成調度方案并解決作業調度過程中的資源爭奪問題；采用MMPX 交叉法、基于子拓撲網絡的變異策略以及禁忌搜索，提高算法的尋優能力。

最后通過對“福特”級航母艦面保障調度典型案例的仿真分析，驗證了本文所提模型和求解算法在一站式保障作業調度優化問題中具有良好的求解性能，表明了算法的有效性和可行性。