王云翔，畢玉泉，楊茂勝，王虹曇

(海軍航空工程學院青島校區(qū)，山東 青島 266041)

艦載機在航母上的布列，主要集中于兩個區(qū)域:一是航母寬大的飛行甲板，二是艦體內部的大型機庫。在飛行甲板上布列的艦載機數(shù)量決定了航母第一波次的攻擊能力。但大型海戰(zhàn)的經驗告訴我們，航母的連續(xù)攻擊能力更加重要，如中途島海戰(zhàn)等，都是因為第二、第三攻擊波次調度不利，導致戰(zhàn)役的失敗。航母的連續(xù)攻擊能力，很大程度上取決于艦載機在機庫與飛行甲板之間的調度優(yōu)化，即怎樣在最短時間內將指定的艦載機從機庫轉運到飛行甲板機務停機位。目前，國內一些學者已經在做艦載機調度優(yōu)化方面的研究。馮強針對艦載機航保系統(tǒng)的動態(tài)調度問題，給出了相應的約束條件，并應用Multi-agent技術建立了模型［1］。魏昌全針對艦載機連續(xù)出動情況下航保重調度問題和在空間約束情況下的艦載機航保調度問題建立了兩種模型［2-3］。李耀宇采用排隊論和逆向強化學習方法建立了兩種艦載機飛行甲板調度的模型［4-5］。司維超在考慮艦載機出動時間情況下建立了艦載機由飛行甲板停機位到起飛位的調度模型，并計算出了各種方案的出動時間［6］。

以上研究主要集中于艦載機在飛行甲板的調度，主要考慮問題是航空母艦航保系統(tǒng)的資源分配，而對艦載機在航母上任意停機位之間的調度問題還少有研究。本文以俄羅斯現(xiàn)役航空母艦為研究對象，主要針對艦載機從航母機庫內指定停機位轉運到飛行甲板指定停機位的調度問題進行研究，建立轉運方案的數(shù)學模型，利用智能粒子群算法對該問題進行求解，給出最優(yōu)方案。

1 艦載機出庫問題

1.1 出庫需求分析

艦載機在起飛前都要在機務停機位進行準備工作，如圖1所示。當?shù)谝徊ù闻炤d機出動完畢后，需要從機庫內將后續(xù)艦載機轉運到飛行甲板機務停機位，如圖2所示，在飛行甲板機務停機位準備后，滑向起飛位，這就是第二攻擊波次，以此類推。這里涉及兩個問題:一是艦載機的布列，艦載機在飛行甲板的布列要考慮到機務準備設備的位置，要便于操作，不能遠離設施，同時也不能過于緊密，避免進出停機位困難;二是艦載機的轉運，艦載機轉運要統(tǒng)籌兼顧，考慮轉運距離，合理利用轉運設施，同時開展作業(yè)，以最大程度節(jié)省時間。

圖1 飛行甲板停機位

圖2 機庫甲板停機位

對于艦載機的布列，主要由指揮員確定，根據(jù)當時飛行甲板面的設備分布情況，根據(jù)起飛位設備的需求等情況確定。當艦載機布列確定后，也就是從哪些機庫停機位轉運到哪些飛行甲板停機位確定后，就要考慮艦載機轉運的問題，即怎樣合理利用轉運設施，包括牽引車、調向轉盤和升降機等，在最短時間內將一個波次內的艦載機轉運到位。

1.2 出庫流程分析

本文以一次四機出動為例進行分析，機庫內的A、B、C、D四架艦載機分別轉運到飛行甲板的 E、F、G、H四個停機位。轉運過程做一個基本假設:機庫內停放兩輛牽引車，飛行甲板停放兩輛牽引車，且牽引車不隨升降機轉運。

1)A艦載機與D艦載機同時開始解系留轉運，A機到達一號調向轉盤后進行系留、轉向、解系留，到達一號升降機后進行系留。同時D機到達二號調向轉盤后進行系留、轉向、解系留，到達二號升降機后進行系留。

2)當A機在一號升降機系留后，牽引車返回B停機位，B機開始解系留，駛向調向轉盤，進行系留、轉向、解系留，到達一號升降機后進行系留。

3)當D機在二號升降機系留后，牽引車返回C停機位，C機開始解系留，駛向調向轉盤，進行系留、轉向、解系留，到達二號升降機后進行系留。

4)B機在機庫內轉運的同時，A機隨升降機上升到飛行甲板，解系留后，由牽引車牽引到E號停機位系留。牽引車返回升降機待命。

5)C機在機庫內轉運的同時，D機隨升降機上升到飛行甲板，解系留后，由牽引車牽引到H號停機位系留。牽引車返回待命。

6)B機隨升降機到達飛行甲板，解系留，并轉運到F停機位系留。

7)C機隨升降機到達飛行甲板，解系留，并轉運到G停機位系留。

以上是沒有經過優(yōu)化的出庫流程，不一定是最優(yōu)過程。其優(yōu)化主要體現(xiàn)在兩個方面:一是資源分配問題，整個流程涉及到4個設備，兩個調向轉盤兩個升降機，由于調向轉盤與升降機位置固定，因此，選定調向轉盤后，升降機不用再選擇，即資源分配時只需要分配調向轉盤;二是作業(yè)次序問題，對于同一個調向轉盤，要給出最優(yōu)的艦載機隊列方案。同時，在優(yōu)化中還要考慮空間約束問題，即艦載機停機位的路徑距離，由于牽引速度較慢，設備運行時間短，所以在艦載機調度過程中運動時間不可忽略。綜上可以看出，基于空間約束的艦載機出庫問題，可以轉化為考慮空間約束的柔性流水車間優(yōu)化問題。

2 基于空間約束的艦載機出庫模型

2.1 假設條件

為建立艦載機出庫調度模型，本文作如下假設:1)所有艦載機在調度開始時可用，無封閉障礙，所有轉運設備可用，調度過程中不損壞;2)牽引作業(yè)一次到位，無調整時間;3)牽引車負載作業(yè)和空駛作業(yè)速度一定且相等;4)所有艦載機保障工藝相同，全部要經過調向轉盤調整;5)艦載機所有停機位已知，且固定;6)同一時刻一臺設備只能保障一架艦載機;7)同一時刻一架艦載機只能接受一個階段一臺設備的保障。

2.2 參數(shù)說明

文中，F(xiàn)為所要達到的目標函數(shù)，即最優(yōu)方案為最后一架艦載機調度完工時間最短的方案;Tp(i)為第P套方案中，第i停機位艦載機的調度完工時間;Ts(i，j，k)為機庫內第i停機位艦載機處于第j順序到達k號升降機系留結束的時間;Tj(i，j，k)為機庫內第i停機位處于第j順序到達k號升降機的艦載機的開始轉運時間;A［m，k］為常數(shù)矩陣，是機庫內牽引車由第m停機位空駛到k號升降機的需用時間;B［i，k］為常數(shù)矩陣，是飛行甲板上第i停機位艦載機到第k號升降機的轉運需用時間;B(m，j，k)以第j順序升起后的艦載機由k號升降機到第m號飛行甲板停機位的轉運時間;C［i，k］為常數(shù)矩陣，是機庫內第i停機位艦載機到第k號升降機系留完畢需用時間;C(i，j+1，k)為在第i停機位的艦載機，以第j+1順序到達k號升降機的轉運時間;Tsj為升降機單程升降需用時間;Tt艦載機系留或解系留的需用時間;a(i，j，k)為機庫內第i停機位處于第j順序到達第k號升降機的艦載機的標號。

2.3 調度模型

艦載機出庫調度模型如下。

目標函數(shù):

式(1)表示目標為求取艦載機總調度完工時間最短的方案;式(2)表示處于第i初始停機位的艦載機轉運過程不中斷，保持轉運連續(xù)性;式(3)表示不同艦載機的初始停機位不同且已知。式(4)表示在考慮空間約束情況下，第i停機位艦載機到k號升降機的轉運時間確定。式(5)表示艦載機保障轉運屬于串行工序，只有前一工序完成后，下一道工序才能開始。式(6)、(7)表示考慮串行工序的等待時間，將串行工序的等待時間計算到轉運時間內。式(8)表示同一設備不能保障多架艦載機。

3 出庫調度問題的粒子群算法

3.1 智能粒子群算法

智能粒子群算法是一種基于群智能的優(yōu)化算法，初期用于無約束條件的連續(xù)函數(shù)優(yōu)化問題，經進一步發(fā)展后，提出了離散型的智能粒子群算法［7-8］。該算法可用來求解復雜的組合優(yōu)化問題，每個優(yōu)化方案都可編碼為搜索空間的一個粒子，每個粒子在解空間中都有一個位置和一個速度值，而且可以通過目標函數(shù)計算它的適應值，通過粒子的適應值可以找到個體最優(yōu)粒子和全局最優(yōu)粒子。所有粒子通過追隨這兩個最優(yōu)粒子的運動，逐漸趨于收斂，從而找到最優(yōu)組合。

粒子群算法數(shù)學表達如下:

其中:xi=(xi1，xi2，…，xid)為粒子群中第i個粒子在d維空間中的位置;vi=(vi1，vi2，…，vid)為粒子群中第i個粒子在d維解空間中的速度;pi=(pi1，pi2，…，pid)為粒子群中第i個粒子的個體歷史最優(yōu)值:pg=(pg1，pg2，…，pgd)為所有迭代中的全局最優(yōu)粒子;t為迭代次數(shù);w 為慣性因子;c1，c2為學習因子;rand1，rand2為［0，1］之間均勻分布的隨機數(shù)。艦載機出庫調度問題是一種組合優(yōu)化問題，具有離散、動態(tài)的特點，應用智能粒子群算法求解時，需要注意粒子的編碼問題。

3.2 粒子的編碼與解碼

可以把每種艦載機出庫調度方案作為一個粒子，而每種方案實際上要解決兩個問題，也就是前面所說的資源分配和作業(yè)次序，因此本文采用二維粒子進行方案的編碼［9-10］。對于一次L架艦載機的轉運，第一維L個向量表示各架艦載機的轉運作業(yè)次序，第二維L個向量用于分配各架艦載機需要占用的資源。如果以10架艦載機，2套調向轉盤為例，那么第一維數(shù)據(jù)可在-10與10之間取隨機數(shù)，第二維數(shù)據(jù)在1與3之間取隨機數(shù)，第i個粒子可由表1表示。

表1 第二維數(shù)據(jù)第i個粒子

對于處于10個停機位的艦載機，粒子位置向量Xi表示了10架艦載機的作業(yè)次序，數(shù)值越小的，作業(yè)次序越靠前。粒子位置Yi表示了10架艦載機的分配哪個轉盤。粒子解碼過程如下。

1)資源分配。對第二維粒子Yi進行向零取整操作Fix(Yi)，如表2，即可得到哪架艦載機分配哪個轉盤，本例中有兩套轉盤，因此Yi取值范圍是［1，3)。

表2 第二維粒子Yi向零取整結果

2)作業(yè)次序。按照資源分配后的序號，依次解碼出每個轉盤對應艦載機位置，然后按照第一維粒子Xi的數(shù)值大小進行排序，數(shù)值越小的作業(yè)次序越靠前，從而解碼出每臺設備的艦載機隊列。因此，上面表格中的艦載機隊列為:

轉盤1:3→1→8→4 轉盤2:9→6→10→5→7→2。

3.3 參數(shù)設置

粒子速度公式中，學習因子分別調節(jié)向個體最優(yōu)粒子和全局最優(yōu)粒子飛行的步長，本文分別取值為c1=1.7，c2=2。慣性因子w決定了粒子的搜索范圍，前期取值較大確保算法的全局性，后期取值較小確保收斂精度高。本文采用帶收縮因子和線性遞減權重的粒子群優(yōu)化算法［11］，慣性因子取值為

速度更新公式［12］為

3.4 算法步驟

1)算法初始化，設置迭代的最大次數(shù)，粒子群數(shù)量，初始化種群的位置和速度，注意各粒子的位置邊界與速度邊界。

2)對粒子解碼生成調度方案，根據(jù)艦載機作業(yè)次序通過目標函數(shù)計算適應值。對于超過約束條件的粒子，將其適應值設置為無窮大，從而淘汰不合理方案。根據(jù)粒子適應值，將每個粒子所有經歷位置中最好的設置為個體最優(yōu)粒子，將所有粒子所有經歷位置中最好的設置為全局最優(yōu)粒子。

3)由式(12)、(10)對粒子的速度和位置進行更新。

4)更新后的粒子，如果速度超過了邊界，則按邊界值取。如果位置超過了邊界，則位置取邊界值，速度取相反方向，使粒子向回飛。

5)判斷迭代條件，如果是，輸出結果，如果不是，轉向步驟2)。

4 仿真結果

本文采用Matlab7.1編程，以機庫內10架艦載機向飛行甲板轉運，前后各一套調向轉盤、一套升降機，飛行甲板兩臺牽引車，機庫兩臺牽引車為例。對于仿真中機庫內轉運、飛行甲板轉運和機庫內空駛三組時間參數(shù)矩陣，由于航母上所有機庫停機位和飛行甲板停機位固定，可在實地測量后給出。本文重在方法研究，其時間矩陣由圖紙上縮比測量后，按照機庫內3km/h，飛行甲板5km/h的速度，計算后給出，其參數(shù)矩陣參見表3。

表3 參數(shù)矩陣

設置粒子群種群數(shù)量為20，最大迭代次數(shù)為200，連續(xù)優(yōu)化10次，得到計算結果如表4所示，10次中最優(yōu)結果的收斂過程如圖3所示。從仿真結果可以看出:

1)在不考慮調整時間條件下，十架艦載機出庫最短用時1850s，其對應的轉運方案為

轉盤1隊列:5→3→1→2→4

轉盤2隊列:6→7→8→9→10;

2)十次優(yōu)化中，初始隨機方案調度用時最多在2300s以上，最優(yōu)結果可節(jié)省轉運用時450s左右，占總用時近20%，因此調度優(yōu)化具有較大應用價值。

圖3 最優(yōu)結果收斂過程

表4 仿真計算結果

3)智能粒子群算法應用于在空間約束條件下的艦載機出庫問題時，收斂速度較快，10次優(yōu)化過程全部在30次迭代內完成，在多次仿真情況下，最優(yōu)值相差不大，基本沒有陷入局部收斂，說明智能粒子群算法能夠較好地解決這類問題。

4)本仿真算例中停機位分布均勻，所得最優(yōu)結果沒有出現(xiàn)資源搶占問題，每臺調向轉盤平均分配5架艦載機。但當初始停機位或目標停機位分布不均時，可能會出現(xiàn)資源搶占，本文數(shù)學模型能夠較好解決這類問題，限于篇幅原因，這里不再列舉具體算例。

5)本文十架艦載機轉運最優(yōu)時間在31min左右，與實際轉運時間有一定差距，其主要原因是艦載機轉運中在臨時停機位的停車調整時間，但調整時間人為因素較大，預測難度大。本文所述方法重在解決資源分配和作業(yè)次序問題，轉運總用時只作為指揮員參考。

5 結束語

本文以俄羅斯航母在空間約束條件下艦載機出庫調度問題為研究對象，分析了制約其出庫調度速度的原因，梳理了艦載機出庫調度流程，建立機庫內艦載機出庫調度的模型，設計求解模型的智能粒子群算法，通過仿真，驗證了模型算法的可行性及有效性，給解決這類出庫問題提供了一種方法。

［1］ 馮強.不確定條件下艦載機動態(tài)調度仿真與優(yōu)化方法［J］.系統(tǒng)仿真學報，2011，23(7):1497-1506.

［2］ 魏昌全，陳春良，王保乳.基于任務的連續(xù)出動艦載機航空保障重調度研究［J］.指揮控制與仿真，2012，34(3):23-26.

［3］ 魏昌全，陳春良，王保乳.基于空間約束的艦載機航空保障調度研究［J］.控制工程，2013，20(4):701-706.

［4］ 李耀宇，朱一凡，楊峰，賈全.基于逆向學習的艦載機甲板調度優(yōu)化方案生成方法［J］.海軍工程大學學報，2013，35(4):171-175.

［5］ 李耀宇，朱一凡，賈全，李群.基于排隊網絡的艦載機甲板調運優(yōu)化調度策略生成方法［J］.國防科技大學學報，2013，25(5):26-30.

［6］ 司維超，韓維，史瑋韋.基于PSO的艦載機艦面布防調度方法研究［J］.航空學報，2012，33(11):2048-2056.

［7］ KENNEDY J，EBERH ART R C.A discrete binary version of the particle swarm algorithm［C］∥Proceedings of 1997 Conference on Systems，Man，and Cybernetics.Washington，D.C.，USA:IEEE，1997，5:4104-4108.

［8］ LIAO C J，TSENG C T，LUARN P.A discrete version of particle swarm optimization for flowshop scheduling problems［J］.Computers ＆ Operations Research，2007，34(10):3099-3111.

［9］ 劉志雄.基于粒子群算法的物流配送車輛優(yōu)化調度研究［J］.物流技術，2009，32(6):615-618.

［10］ WANG LAIJUN，SHI ZHONGKE，LEI XIUJUAN.Dynamic tabu search algorithm for solving departure scheduling problem［J］.Journal of southwest jiotong University(Endlish Edition)，2007，15(2):132-137.

［11］ 粒子群優(yōu)化算法［EB/OL］.http:∥www.ipic.njupt.edu.cn/neoxus/index.php，2009-04-28.

［12］ EBERHART R C，SHI Y.Comparing inertia weights and constriction factors in Particle Swarm Optimization［C］∥Proceedings of the Congresson Evolutionary Computating，2000:84-88.