基于空間約束的艦載機出庫調(diào)度

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

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

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

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

1 艦載機出庫問題

1.1 出庫需求分析

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

圖1 飛行甲板停機位

圖2 機庫甲板停機位

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

1.2 出庫流程分析

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

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

2)當(dāng)A機在一號升降機系留后，牽引車返回B停機位，B機開始解系留，駛向調(diào)向轉(zhuǎn)盤，進行系留、轉(zhuǎn)向、解系留，到達一號升降機后進行系留。

3)當(dāng)D機在二號升降機系留后，牽引車返回C停機位，C機開始解系留，駛向調(diào)向轉(zhuǎn)盤，進行系留、轉(zhuǎn)向、解系留，到達二號升降機后進行系留。

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

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

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

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

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

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

2.1 假設(shè)條件

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

2.2 參數(shù)說明

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

2.3 調(diào)度模型

艦載機出庫調(diào)度模型如下。

目標函數(shù):

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

3 出庫調(diào)度問題的粒子群算法

3.1 智能粒子群算法

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

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

其中: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為學(xué)習(xí)因子;rand1，rand2為［0，1］之間均勻分布的隨機數(shù)。艦載機出庫調(diào)度問題是一種組合優(yōu)化問題，具有離散、動態(tài)的特點，應(yīng)用智能粒子群算法求解時，需要注意粒子的編碼問題。

3.2 粒子的編碼與解碼

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

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

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

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

表2 第二維粒子Yi向零取整結(jié)果

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

轉(zhuǎn)盤1:3→1→8→4 轉(zhuǎn)盤2:9→6→10→5→7→2。

3.3 參數(shù)設(shè)置

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

速度更新公式［12］為

3.4 算法步驟

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

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

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

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

5)判斷迭代條件，如果是，輸出結(jié)果，如果不是，轉(zhuǎn)向步驟2)。

4 仿真結(jié)果

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

表3 參數(shù)矩陣

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

1)在不考慮調(diào)整時間條件下，十架艦載機出庫最短用時1850s，其對應(yīng)的轉(zhuǎn)運方案為

轉(zhuǎn)盤1隊列:5→3→1→2→4

轉(zhuǎn)盤2隊列:6→7→8→9→10;

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

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

表4 仿真計算結(jié)果

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

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

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

5 結(jié)束語

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

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

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

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

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

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

［6］ 司維超，韓維，史瑋韋.基于PSO的艦載機艦面布防調(diào)度方法研究［J］.航空學(xué)報，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)化調(diào)度研究［J］.物流技術(shù)，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.