徐柱國，余明暉*，吳靳，戴明強

1 華中科技大學(xué) 人工智能與自動化學(xué)院，湖北 武漢 430074

2 海軍工程大學(xué) 電子工程學(xué)院，湖北 武漢 430033

3 海軍工程大學(xué) 基礎(chǔ)部, 湖北 武漢 430033

0 引 言

艦載機作為航空母艦（以下稱“航母”）的核心作戰(zhàn)裝備，其數(shù)量以及調(diào)運效率與航母綜合作戰(zhàn)能力緊密相關(guān)[1]。作為航母停放艦載機的主要地點，機庫不僅需要盡可能布列更多數(shù)量的艦載機，同時布列方案還需合理滿足艦載機出庫調(diào)運需求。因此，需對艦載機機庫的停放布列問題，即在二維機庫平面內(nèi)對不同種類艦載機（如戰(zhàn)斗機、直升機、預(yù)警機等）進行站位劃分，以提高機庫停放的艦載機數(shù)量并保證艦載機調(diào)運效率。

國內(nèi)外學(xué)者針對機庫布列問題開展了較多研究。美國海軍開發(fā)了航空數(shù)據(jù)管理與控制系統(tǒng)（aviation data management and control system，ADMACS）[2]以及艦船綜合信息系統(tǒng)（integrated shipboard information system，ISIS），通過在艦載機上安裝具有標識的GPS，可實時顯示其位置狀態(tài)信息，進而供相關(guān)人員手動調(diào)控站位，實現(xiàn)艦載機的布列；李耀宇等[3]對艦載機甲板布列調(diào)運業(yè)務(wù)進行分析，總結(jié)了國內(nèi)外相應(yīng)的研究情況；胡玉龍等[4]對機庫進行了模糊建模以求解機庫結(jié)構(gòu)設(shè)計方案，其機庫分段思想對布列問題很有幫助；張思[5]基于臨界多邊形（no-fit polygon，NFP）與遺傳算法（GA），以艦載機數(shù)量為目標對該問題進行了求解；田大肥[6]將該問題轉(zhuǎn)化成二維矩形裝箱問題，以總調(diào)運路程為目標對問題進行了優(yōu)化求解；Li等[7]通過對放置空間和飛機二維幾何模型進行建模，開發(fā)了一種用于解決飛機布列問題的新型遺傳算法。

從機庫布列的2個優(yōu)化目標（即艦載機數(shù)量更多與出動效率更高）出發(fā)，該問題可拆分為兩個優(yōu)化問題，即空間利用率優(yōu)化與考慮調(diào)運效率的空間布局優(yōu)化?？臻g利用率優(yōu)化也稱裝箱問題，屬于一種NP難度問題。機庫空間狹小，將艦載機輪廓凸化處理會導(dǎo)致艦載機間隙過大，機庫空間利用不充分，故若想布列結(jié)果有實際使用價值，需要將機庫布列問題轉(zhuǎn)化為連續(xù)空間下二維凹多面體的裝箱問題，面積利用率越高，則放置的艦載機數(shù)量越多。二維裝箱問題解決方法很多，但目前在艦載機布列問題上應(yīng)用不多。如Burke等[8]基于軌跡線建立臨界多邊形，可以為復(fù)雜二維圖形排樣提供多樣化的運算；Alvarez-Valdes等[9]基于分支定界算法，實現(xiàn)了對二維不規(guī)則形狀圖形的排樣切割；這個問題與Kheirkhah等[10]在動態(tài)設(shè)施布局問題上的研究類似。考慮調(diào)運效率的空間布局優(yōu)化對應(yīng)于倉儲、車庫領(lǐng)域的車位排布問題。Abdelfatah等[11]采用線性規(guī)劃對車庫停車容量進行了優(yōu)化；徐涵喆等[12]提出一種基于規(guī)則的車位排布啟發(fā)式算法，得到了車位數(shù)較多且實用的排布方案。

艦載機不僅具有空間輪廓屬性，還有轉(zhuǎn)運的業(yè)務(wù)需求。從現(xiàn)有的研究結(jié)果來看，一方面是弱化艦載機調(diào)度需求，以艦載機數(shù)量為唯一優(yōu)化目標的布列優(yōu)化研究已取得不錯的成果，另一方面是簡化艦載機輪廓和布列算法，以調(diào)運總路程為唯一目標的研究也成果頗豐，但這兩方面都因優(yōu)化目標單一，算法結(jié)果與機庫實際布列方案還存在很大的差距。目前，同時考慮這2個優(yōu)化目標的研究尚屬空白。本文擬通過分析機庫布列問題的特點和業(yè)務(wù)需求，建立基本空間組合關(guān)系庫，計算可能的空間組合，然后基于遺傳算法優(yōu)化布列順序，建立以最大化布列飛機數(shù)目與最大化緊急出動艦載機數(shù)量為優(yōu)化目標的多目標智能算法，優(yōu)化機庫甲板艦載機布列方案。

1 機庫布列問題描述

1.1 機庫環(huán)境描述

與飛行甲板相比，在機庫甲板容納更多艦載機的優(yōu)化目標顯得更為重要。機庫甲板作為航母上空間最大的艙室，無起降跑道與艦島等空間限制，布列自由度高、靈活性強、優(yōu)化空間大。本文將以“尼米茲”級航母作為參考對象，研究艦載機在機庫甲板的布列問題。

“尼米茲”級航母機庫甲板的形狀約為矩形，長208.5 m，寬33 m。其右舷有3部升降機，左舷有1部。升降機是艦載機在機庫甲板與飛行甲板之間轉(zhuǎn)運的唯一途徑，其數(shù)量與位置不僅影響甲板之間的轉(zhuǎn)運效率，而且還會對機庫內(nèi)的布列方案產(chǎn)生影響。在設(shè)計自動布列算法時，應(yīng)當考慮升降機的因素，以提高布列方案的轉(zhuǎn)運效率與業(yè)務(wù)合理性。本文以升降機數(shù)量多的一側(cè)-右舷的升降機為節(jié)點，以相鄰升降機間隔中線為界限，將機庫劃分為3個子艙室，分隔線同時也與航母機庫防火簾的位置大體一致[13]，如圖1所示。

圖 1 “尼米茲”級機庫環(huán)境Fig.1 Hangar environment of USS Nimitz-class aircraft carrier

將機庫甲板劃分成3個子艙室后，每個子艙室僅將其相鄰的升降機作為調(diào)運出口。設(shè)n個單位的布列問題為Gn(x)， 劃分成m個子艙室后，研究問題轉(zhuǎn)化為如式(1)所示的問題：

1.2 艦載機布列資源分配方法

航母攜帶的艦載機數(shù)量多，種類也多。在美軍進行的“高強度演習(xí)”中，“尼米茲”級航母共裝載了F-14A戰(zhàn)斗機、F/A-18C戰(zhàn)斗/攻擊機、EA-6B電子戰(zhàn)機、S-3A反潛/加油機、E-2C預(yù)警機和SH-60B直升機等多種飛機，機庫內(nèi)還放置了少許小艇，這些統(tǒng)稱為布列單位。為保證每部升降機都能出動特定類型的飛機，并保持升降機使用次數(shù)的均衡，本文將機庫總布列需求分配至子艙室。

分配的規(guī)則為：

1) 各子艙室布列的艦載機總數(shù)量不宜相差太大；

2) 同一種類飛機不應(yīng)過于集中。

根據(jù)上述規(guī)則，具體的分配算法流程如圖2所示。

圖 2 艙室需求分配算法流程圖Fig.2 The process of cabin requirement allocation algorithm

上述流程圖中，在對各類艦載機數(shù)量進行判定后，先均勻分配布列需求，再將無法均勻分配的剩余部分與其他數(shù)量少的布列單位合并為新的需求，進行二次分配。

1.3 艦載機幾何描述與布列原則

現(xiàn)有研究普遍采用以五邊形為主的凸多邊形，甚至以矩形來簡化艦載機輪廓，這就導(dǎo)致艦載機間距空間、艦載機機翼與機身所夾空間等空間資源可能出現(xiàn)浪費。本文設(shè)計的算法對艦載機幾何輪廓無要求，可以在同一方案內(nèi)采用多種簡化或原輪廓的圖形來表示艦載機。如圖3所示，分別為簡化輪廓戰(zhàn)斗機（折翼狀態(tài)）、原輪廓戰(zhàn)斗機（展翼狀態(tài)）、原輪廓預(yù)警機和原輪廓直升機（折翼狀態(tài)），這些輪廓均可通過2.1節(jié)中描述的布列算法進行布列。

圖 3 部分艦載機輪廓圖Fig.3 Outline drawing of some carrier aircrafts

在本文研究工作中，圖形處理算法引用了Burke等[8]的研究成果：基于移動碰撞算法，求解出NFP，從而實現(xiàn)二維排樣。NFP是二維排樣問題中關(guān)鍵的幾何工具，可以用于求解圖形間最優(yōu)靠接位置、重疊判斷、定位等。根據(jù)內(nèi)靠接NFP原理，基于最左最下原則（bottom left，BL）、最左最下填充原則（bottom left fill，BLF）、最合適位置原則（best fit，BF）及最低重心原則等多種定位策略，可以為布列單位選取比較有優(yōu)勢的布列位置。

1.4 艦載機機庫布列特點

艦載機在航母飛行甲板和機庫甲板上的約束有許多差異。通過分析機庫使用的特點，得出在機庫劃分艦載機站位時，需要考慮以下布列特點：

1) 機庫內(nèi)艦載機調(diào)運全部靠牽引車實現(xiàn)，不需要考慮艦載機發(fā)動機尾焰對機尾朝向的影響。

2) 單類型艦載機不應(yīng)全部依賴于特定的升降機轉(zhuǎn)運，以防止在該升降機發(fā)生故障時無法出動該類型艦載機。

3) 機庫的主要功能是存儲與維修，緊急出動的艦載機是用來替換飛行甲板上發(fā)生故障的艦載機。不需要緊急出動的艦載機無需考慮轉(zhuǎn)運成本，這些飛機有足夠的時間在機庫內(nèi)完成運動姿態(tài)的轉(zhuǎn)換。

4) 緊急出動艦載機的尾部應(yīng)朝向升降機，以便緊急出動時由牽引車將其推入升降機，并牽引至飛行甲板指定保障站位進行保障。

5) 緊急出動艦載機的尾部不應(yīng)被任何障礙物阻攔，即無需移動其他艦載機便可將其移動至升降機，且應(yīng)盡可能避免正反向行駛多次切換。

6) 在不考慮飛行甲板使用的情況下，每部升降機都能用來緊急出動艦載機。

7) 艦載機擺放在機庫甲板規(guī)定的區(qū)域內(nèi)。

8) 艦載機不可互相重疊。

9) 為方便管理與擺放美觀，艦載機劃分的站位需盡可能具有整齊劃一、朝向有規(guī)律等特點。

2 機庫布列問題建模

2.1 基于基本空間組合關(guān)系的艦載機組合生成算法

對于如航母機庫等自由空間下布列多類不規(guī)則輪廓物體的問題，巧妙利用艦載機等單位不規(guī)則輪廓間的鑲嵌，建立更緊密的組合關(guān)系是增加布列飛機數(shù)量、提高空間利用率的有效方法。艦載機的組合方式與業(yè)務(wù)強相關(guān)，涉及管理、安全、美觀等多個因素。本文依據(jù)實際業(yè)務(wù)，以提取艦載機等物體常用的、可靠的組合方式為規(guī)則來建立基本組合關(guān)系庫。

在基本組合關(guān)系庫中以類型為節(jié)點，記錄各類型間是否存在推薦的組合關(guān)系。將可以相互組合的布列單位放入集合中，再基于以整數(shù)拆分思想為基礎(chǔ)的搜索算法計算集合內(nèi)可能存在的組合分配方案。同時，基本組合關(guān)系庫可以支持新機型的布列設(shè)計，使算法具有一定的可擴展性。

下面，以“尼米茲”級航母的主要固定翼艦載機機型為例來說明組合關(guān)系的建模。主要考慮F-14A，F(xiàn)/A-18C，EA-2C這3種機型，可能的組合關(guān)系包括對式和齊頭式，不同機型的組合關(guān)系如表1所示。

表 1 部分組合關(guān)系Table 1 Partial combination relationship of aircrafts

部分組合類型樣式如圖4所示。

圖 4 部分組合結(jié)果Fig.4 Partial combination results

以計算1架EA-2C和4架F-14A的組合方案結(jié)果集為例來介紹算法流程，流程圖如圖5所示。圖中，“*”后面的數(shù)字表示該機型的數(shù)量。

圖 5 組合算法流程圖Fig.5 The flow chart of combinatorial search

表 2 結(jié)果集Table 2 The result set

多個布列單位組合成布列模塊，各布列模塊中布列單位的數(shù)量如表2所示。表2中，“F-14A*4”表示4架F-14A組合擺放，為1個布列模塊，“F-14A*1+F-14A*1+F-14A*1+F-14A*1”表示4架F-14A單獨擺放，為4個布列模塊。兩者的區(qū)別在于布列模塊之間以最小包絡(luò)矩形的形式堆疊，沒有采用組合關(guān)系的4個布列模塊堆疊導(dǎo)致相鄰的“F-14A”的間隙空間不會被利用。提高面積利用率的唯一途徑在于建立布列模塊之間緊密的組合關(guān)系，即通過減少浪費面積來實現(xiàn)。

由于組合關(guān)系固定，基于同種組合關(guān)系組合成的布列模塊內(nèi)停機密度一定相等。

原問題為有限空間內(nèi)多個不規(guī)則物體的二維連續(xù)排樣問題，上述算法將該問題通過基本組合關(guān)系庫離散化，將問題轉(zhuǎn)化為了組合優(yōu)化問題。在轉(zhuǎn)化過程中，嘗試從有限的合理組合關(guān)系來分析問題，將解空間由連續(xù)解空間離散化至可求解程度。被舍棄的解空間中不會存在滿足業(yè)務(wù)需求的最優(yōu)解。

2.2 組合布列優(yōu)化模型建立

根據(jù)前面的研究，艦載機布列方案有2個優(yōu)化目標：布列數(shù)量更多與緊急出動艦載機數(shù)量更多。通過對布列資源進行分析，由搜索算法得出的結(jié)果集中包含了該布列資源下全部的組合方案。組合方案中的元素被命名為布列模塊，這在2.1節(jié)中已有介紹。通過為各模塊編號，基于LB（left bottom）策略，按編號順序迭代擺放至機庫空間即可實現(xiàn)一個完整的布列方案。LB策略意為將需要放置的模塊先向左移動至邊界，再向下移動至邊界。通過該策略實現(xiàn)擺放定位。通常LB策略會造成很明顯的元素分布不均勻問題，但在本文研究內(nèi)容中，由于布列模塊內(nèi)部停機密度固定、布列模塊之間間隙基本相同，因此LB策略基本滿足此業(yè)務(wù)需求。

根據(jù)總體業(yè)務(wù)優(yōu)化目標以及布列中的約束條件，可得到優(yōu)化問題的數(shù)學(xué)模型。

目標函數(shù)為：

約束條件為：

式中：S為機庫甲板總空間；Si為編號為i的飛機所占空間，在機庫內(nèi)布列單位不僅不可互相重疊，也不可超出機庫空間；f1(x)為所有布列單位占用的面積，其只與布列資源中的布列單位數(shù)量有關(guān)；Bt為t類型布列單位經(jīng)路徑規(guī)劃模塊判斷后可直接出動的數(shù)量。飛機是否能夠直接出動的判斷邏輯是：單架艦載機在將其他布列單位視為障礙物且不超過邊界的條件下，是否可以完成前往指定升降機的路徑規(guī)劃。

在這種情況下，路徑規(guī)劃只需要回答“可以”或“不可以”即可?！翱梢浴钡臄?shù)量與優(yōu)化目標f2(x)密切相關(guān)，而路徑的長度優(yōu)化從業(yè)務(wù)角度來看并無太大意義：機庫內(nèi)空間狹小，不同路徑間長度差額的絕對值不大，不會對調(diào)運效率產(chǎn)生明顯影響。本文基于Reed-Shepp算法實現(xiàn)路徑規(guī)劃進而完成邏輯判斷。Reed-Shepp算法理論成熟，運算速度快，且具有考慮運動學(xué)約束等特點。對升降機附近的布列模型進行倒車路徑判定可迅速評估布列方案的緊急出動能力。

當布列資源確定時，機庫甲板內(nèi)面積利用率也可同時確定。兩目標優(yōu)化問題此時成為單目標優(yōu)化問題，即鎖定了布列資源后只需要對f2(x)求解即可。

此時，對于確定了布列資源后的模型，有

式中：C為機庫布列問題解集；D為組合方案集解集；E為布列順序解集。

3 機庫布列的多目標啟發(fā)式算法設(shè)計

3.1 啟發(fā)式算法設(shè)計

基于搜索得出眾多組合方案后，需要對每個組合方案的最優(yōu)布列進行優(yōu)化求解。同一組合方案下各模塊不同順序的擺放會得到不同的結(jié)果，模塊數(shù)決定了解空間大小。不同組合方案中模塊數(shù)量n并 不相同，解空間的大小為n!。本文基于遺傳算法來求解該模型。

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法，其求解過程不受搜索空間的限制，也不要求解具有連續(xù)性，在組合優(yōu)化問題上具有很大優(yōu)勢。遺傳算法具有很強的魯棒性，能夠面對不同的解空間保持較穩(wěn)定的求解效率。

下面，具體說明為求解布列順序設(shè)計的遺傳算法內(nèi)容。

本文采用十進制編碼方式，染色體長度值為模塊數(shù)量m值的2倍。每個模塊具有2個變量：布列順序與布列角度。所有的模塊只考慮垂直與水平2種擺放形式。某含有9個模塊的組合方案的染色體編碼為[(2,0),(3,1),(4,0),(5,1),(1,0),(6,1),(7,0),(8,1),(0,0)]，其含義為布列順序(2,3,4,5,1,6,7,8,0)，布列角度編碼0代表水平擺放，1代表垂直擺放。基于Abdoun等[14]的研究成果，本文采用“順序交叉”（order crossover，OX）規(guī)則對染色體進行交叉操作。第1步，隨機選擇一對染色體（父代）中幾個基因的起止位置（兩染色體被選位置相同）；第2步，生成一個子代，并保證子代中被選中基因的位置與父代相同；第3步，先找出第1步選中的基因在另一個父代中的位置，再將其余基因按順序放入上一步生成的子代中，如圖6所示。

圖 6 編碼流程Fig.6 Encoding process

變異選用單點突變，即隨機選取要突變的基因位點，然后突變成與剩余的其他基因不同的基因。

通過對布列方案中的每架艦載機（只計算F-14A，F(xiàn)/A-18C等戰(zhàn)斗機型，不計算預(yù)警機、救生艇、直升機等非戰(zhàn)斗機型）遍歷調(diào)用路徑規(guī)劃算法，計算可緊急出動的艦載機數(shù)量，將其作為適應(yīng)度值。

遺傳算法流程圖如圖7所示。

圖 7 遺傳算法求解流程Fig.7 Solving process of GA

在算法運行中，若某一編碼對應(yīng)的布列方案因機庫空間幾何約束導(dǎo)致空間不足而無法完成放置，則會放棄該編碼。通過將機庫幾何輪廓作為二維排樣中的約束不斷淘汰不合格的編碼。

3.2 迭代調(diào)用算法實現(xiàn)兩目標優(yōu)化

當機庫內(nèi)擺放一定數(shù)量的艦載機時，利用遺傳算法可以計算出最大緊急出動飛機數(shù)量以及其對應(yīng)的布列方案。本文為遺傳算法設(shè)置適應(yīng)度閾值，當達到閾值時提前終止遺傳算法，以使機庫完全能夠滿足該數(shù)量布列需求下對于緊急出動的業(yè)務(wù)需求。終止算法后，在布列需求中添加一架默認的戰(zhàn)斗機型，如F-14A或F/A-18C，繼續(xù)進行布列方案探究。迭代多次后，混合算法能夠輸出布列數(shù)量與最大緊急出動能力平衡的布列方案。m個子艙室的滿意解構(gòu)成總機庫的滿意解。

兩目標迭代算法流程如圖8所示。

4 仿真實驗

由文獻[13]，得到美海軍“尼米茲”級航母機庫的布列圖如圖9所示。

圖 8 迭代算法流程Fig.8 Solving process of iterative algorithm

圖 9 “尼米茲”級航母機庫布列方案Fig.9 The hangar layout scheme of Nimitz-class aircraft carrier

本文設(shè)計了“尼米茲”級航母在類似戰(zhàn)斗模式下機庫的布列需求，并對算法有效性進行驗證。算法采用C++編程實現(xiàn)，運行在CPU為i5-6500(4核，3.2 GHz)、內(nèi)存8 GB的計算機上。該布列需求包括7種布列單位，初始布列需求與美軍方案保持一致，經(jīng)過任務(wù)分配后得到具體子艙室的布列需求如表3所示。

表 3 艦載機機庫基本布列需求表Table 3 Basic layout requirements of aircraft hangar

在本次算法運行中，設(shè)最大遺傳代數(shù)Genmax=100，種群空間Popmax=50，變異率pm=0.02，交叉率pc=0.6，設(shè)置閾值為

式中：Ek為第k個艙室緊急出動的艦載機數(shù)量；Fk為第k個艙室擁有的升降機數(shù)量。每個艙室單獨求解。

在算法運行過程中，優(yōu)化算法表現(xiàn)出較好的收斂性，不同子艙室的求解時間接近，求解出的總布列方案如圖10所示。

圖 10 最終布列結(jié)果Fig.10 The final layout result

在計算美軍布列方案利用率時，需將各艦載機占用面積替換為本文布列算法中同類型艦載機采用的輪廓的占用面積，以保證結(jié)果不受輪廓因素的干擾。經(jīng)計算，得到美軍布列方案面積利用率為36.54%。

在本文得出的方案中，各布列單位長、寬參數(shù)經(jīng)過核對，符合實際尺寸。在計算中，通過多次迭代加入F/A-18C來增加布列數(shù)量，使機庫總布列單位數(shù)量達到44架，其中F/A-18C為27架，面積利用率為53.46%，與美軍布列方案相比提高了16.92%。各升降機均保證了一定的緊急出動能力?？紤]到可能會因擺放規(guī)則而出現(xiàn)右上方區(qū)域利用率不夠高的情況，可人工對生成的方案進行艦載機間距調(diào)整，使之分布均勻。

5 結(jié) 論

本文通過對機庫環(huán)境進行分析，對艦載機常用擺放形式進行了歸納整理；通過對基本組合關(guān)系庫進行組合關(guān)系搜索，實現(xiàn)布列資源預(yù)處理，得到了所有可能的布列區(qū)塊組合；以布列面積利用率最大化與艦載機可直接出動數(shù)量最大化為目標，通過遺傳算法對組合模塊進行布列順序優(yōu)化，與美軍布列方案對比驗證了算法的有效性。通過研究，得到如下結(jié)論：

1) 本文提出的布列算法能夠應(yīng)對不同類型機庫、不同布列需求下同類問題的計算與優(yōu)化；

2) 基于基本組合關(guān)系庫得到的組合方案使得布列結(jié)果具有較高的實用性、安全性與美觀性；

3) 啟發(fā)式算法不僅能夠盡可能提高機庫存放艦載機數(shù)量，同時能夠保證艦載機緊急出動能力；

4) 可視化輸出的布列結(jié)果，可以為機庫管理員提供站位劃分的輔助決策依據(jù)。

由于艦載機組合關(guān)系十分復(fù)雜，本文多以同類機型組合為主進行研究?；窘M合關(guān)系庫需要在后續(xù)的工作中繼續(xù)豐富，同時組合的角度也可從離散化向連續(xù)化繼續(xù)深入研究。目前，基本組合關(guān)系庫需要用戶手動輸入，若能依據(jù)外形輪廓智能生成則更方便、更全面，更豐富的組合關(guān)系可以得到更優(yōu)秀的布列方案。組合關(guān)系與艦載機實際業(yè)務(wù)密切相關(guān)，且不同戰(zhàn)斗模式下機庫對組合關(guān)系有不同的要求，特定區(qū)域?qū)ε艠咏嵌纫灿屑s束，需要建立更復(fù)雜的業(yè)務(wù)模型。此外，啟發(fā)式算法的設(shè)計與優(yōu)化空間巨大，與求解效率緊密相關(guān)，還需進行大量的研究。