李耀宇，朱一凡，齊 鳴，李 群

(1.國(guó)防科技大學(xué)信息系統(tǒng)與管理學(xué)院，湖南 長(zhǎng)沙 410073;2.海軍裝備研究院艦船所，北京 100073)

航空母艦自誕生以來就在戰(zhàn)場(chǎng)上顯示了強(qiáng)大的性能和作用，從某種意義上說，航母已經(jīng)成為一個(gè)國(guó)家科技水平、工業(yè)水平甚至綜合國(guó)力的象征［1］。航母強(qiáng)大的戰(zhàn)斗力來自艦載機(jī)等裝備的科技水平以及航母指揮員的管理和調(diào)度能力。航母甲板空間有限，作戰(zhàn)環(huán)境高度危險(xiǎn)緊張，如果能夠在任務(wù)下達(dá)后最先出動(dòng)戰(zhàn)機(jī)形成戰(zhàn)斗力并且在作戰(zhàn)過程中有條不紊地進(jìn)行甲板作業(yè)，保持持久作戰(zhàn)能力，就能在瞬息萬變的戰(zhàn)場(chǎng)中占據(jù)先機(jī)。作為航空母艦作戰(zhàn)的核心問題，艦載機(jī)的起飛、降落、停泊、維護(hù)等很多工作都要在飛行甲板上完成，有時(shí)還需要調(diào)動(dòng)下層甲板中機(jī)庫(kù)里的飛機(jī)進(jìn)行作戰(zhàn)。如何合理利用飛行甲板有限的空間和資源，快速有效地調(diào)度飛機(jī)執(zhí)行作戰(zhàn)任務(wù)，是世界各航母強(qiáng)國(guó)爭(zhēng)先研究的關(guān)鍵問題［2］。

美國(guó)擁有世界上最強(qiáng)大的航母力量，經(jīng)過70多年的實(shí)戰(zhàn)經(jīng)驗(yàn)積累，已經(jīng)形成一套行之有效的艦載機(jī)布列調(diào)運(yùn)體系和制度。由于艦載機(jī)的甲板調(diào)度一直被各軍事強(qiáng)國(guó)列為航母的關(guān)鍵技術(shù)，幾乎沒有任何文獻(xiàn)或資料介紹航母指揮官如何調(diào)度和管理艦載機(jī)，所以這項(xiàng)技能也被稱為“巫術(shù)”。盡管航母的布列調(diào)運(yùn)一直籠罩著神秘的面紗，但是從最近的一些文獻(xiàn)中可以發(fā)現(xiàn)［3-4］，所謂艦載機(jī)布列調(diào)運(yùn)，實(shí)質(zhì)上就是為艦載機(jī)安排合理的停機(jī)位，方便其出動(dòng)或進(jìn)行各項(xiàng)維修補(bǔ)給作業(yè)，并實(shí)時(shí)規(guī)劃艦載機(jī)移動(dòng)路徑，在避免碰撞等事故的前提下，盡量縮短移動(dòng)距離、減少作業(yè)時(shí)間，為艦載機(jī)的起降及各項(xiàng)作業(yè)做好準(zhǔn)備［5-50］。

最早用計(jì)算機(jī)輔助艦載機(jī)調(diào)度的是Giardina［44］和Johnson［45］等人，1974年他們?cè)O(shè)計(jì)了最早的航母甲板操作控制系統(tǒng)(CADOCS)，但沒有得到充分的應(yīng)用。2002年Timothy［2］提出了美軍航母布列調(diào)運(yùn)智能化的需求，但其只停留在概念設(shè)計(jì)層面上。Jeffrey［43］等人設(shè)計(jì)了一種航母艦載機(jī)甲板持續(xù)監(jiān)控系統(tǒng)，具備艦載機(jī)調(diào)度過程中的危險(xiǎn)預(yù)警和路徑規(guī)劃的能力，但不具備艦載機(jī)的調(diào)度輔助功能。國(guó)內(nèi)的馮強(qiáng)［13］將Multi-Agent技術(shù)應(yīng)用到艦載機(jī)的甲板作業(yè)，設(shè)計(jì)了基于MAS的艦載機(jī)動(dòng)態(tài)調(diào)度模型，但由于只針對(duì)艦載機(jī)各甲板作業(yè)之間的協(xié)調(diào)，對(duì)布列調(diào)運(yùn)的優(yōu)化作用不大。

2009年，MIT的計(jì)算機(jī)科學(xué)與人工智能實(shí)驗(yàn)室(ComputerScience and ArtificialIntelligence Lab，CSAIL)開始為美海軍自動(dòng)項(xiàng)目研究所開發(fā)一款名為航空母艦甲板行動(dòng)過程規(guī)劃者(Aircraft Carrier Deck Course of Action Planner，DCAP)的系統(tǒng)，其規(guī)劃手段基于馬爾可夫決策過程和學(xué)徒強(qiáng)化學(xué)習(xí)方法，旨在為航母甲板指控人員提供艦載機(jī)的作業(yè)流程和調(diào)度輔助方案。目前該系統(tǒng)已經(jīng)進(jìn)入指揮人員的測(cè)試過程，不久將會(huì)在美航母艦隊(duì)上得到應(yīng)用。

綜合上述研究可以發(fā)現(xiàn)，布列調(diào)運(yùn)優(yōu)化主要包括艦載機(jī)在甲板的停放布局、甲板移動(dòng)過程的路徑規(guī)劃以及甲板作業(yè)的調(diào)度。本文將這三個(gè)艦載機(jī)布列調(diào)運(yùn)的關(guān)鍵環(huán)節(jié)作為研究?jī)?nèi)容，首先介紹美軍航母艦載機(jī)布列調(diào)運(yùn)的現(xiàn)行管理體系和方法，指出人工調(diào)度的缺陷和不足，然后針對(duì)艦載機(jī)甲板停放布列、移動(dòng)路徑規(guī)劃和甲板作業(yè)調(diào)度的特點(diǎn)介紹目前這幾個(gè)方面的主要研究方法，最后展望了艦載機(jī)布列調(diào)運(yùn)優(yōu)化方法未來的研究方向。

1 航母艦載機(jī)布列調(diào)運(yùn)現(xiàn)狀分析

1.1 航母布列調(diào)運(yùn)組織制度

以美軍為例，航空母艦上負(fù)責(zé)管理飛行甲板布列調(diào)運(yùn)的職位為飛機(jī)調(diào)運(yùn)長(zhǎng)官(ACHO，Aircraft Handling Officer)，其職責(zé)是在飛行準(zhǔn)備期和飛行作戰(zhàn)過程中調(diào)度飛機(jī)在甲板和機(jī)庫(kù)的布列停放和移動(dòng)調(diào)度，避免因有限空間內(nèi)飛機(jī)太多而造成“死鎖”。其詳細(xì)職責(zé)包括:

·監(jiān)督管理編隊(duì)飛機(jī)的維護(hù)保養(yǎng)，確保飛機(jī)在飛行甲板和機(jī)庫(kù)的停放位置和方式能夠快速完成下兩次的飛行出動(dòng)任務(wù);

·時(shí)刻了解飛機(jī)狀況并報(bào)告變更情況;

·時(shí)刻追蹤空中的、飛行甲板上的和機(jī)庫(kù)里的飛機(jī)數(shù)量，飛行甲板和機(jī)庫(kù)中的武器種類和數(shù)量，以及甲板上其他設(shè)備可用情況(如燃油泵等)。

ACHO通過飛行甲板長(zhǎng)官、機(jī)庫(kù)長(zhǎng)官、彈射器長(zhǎng)官等的輔助，實(shí)時(shí)控制所有飛機(jī)的布列狀態(tài)，根據(jù)任務(wù)需要，調(diào)度飛機(jī)進(jìn)行維修保養(yǎng)、入庫(kù)或二次飛行出動(dòng)，并為所有飛機(jī)在甲板和機(jī)庫(kù)的移動(dòng)規(guī)劃路線，確保飛機(jī)能夠在最短的時(shí)間內(nèi)完成飛行準(zhǔn)備任務(wù)。

1.2 “Oui ja”Board與ADMACS

多年來ACHO一直使用一種稱為“占卜板(Oui ja Board)”［6］的航母甲板模擬平臺(tái)記錄并管理艦載機(jī)的停放和調(diào)度，它有上下兩層，分別代表飛行甲板和機(jī)庫(kù)甲板，并用各種顏色、形狀的飛機(jī)模型和圖釘?shù)慕M合來代表甲板上當(dāng)前各飛機(jī)的停放位置和狀態(tài)，如圖1所示。

圖1 “Oui ja”Board

“占卜板”既可以用來代表實(shí)際飛機(jī)的位置，也可用于規(guī)劃飛機(jī)的調(diào)度。飛機(jī)的位置和狀態(tài)信息由地面工作人員通過話筒報(bào)告給ACHO，所以“占卜板”上顯示的僅僅是甲板當(dāng)前的靜態(tài)布局。一般情況下，一艘航母只有一臺(tái)“占卜板”，也就是說，只有ACHO和他的部門人員了解航母的布列狀態(tài)，如果航母司令官想知道當(dāng)前的甲板情況部署戰(zhàn)斗任務(wù)，只能向ACHO咨詢或者親自到布列調(diào)運(yùn)指揮室了解。顯而易見，這種人工的操作方式不僅存在信息延誤和不對(duì)稱的情況，不利于艦載機(jī)布列調(diào)運(yùn)的快速指揮，而且嚴(yán)重影響航空母艦的整體作戰(zhàn)能力。

為了解決“占卜板”信息不對(duì)稱的問題，美國(guó)海軍開發(fā)了航空數(shù)據(jù)管理與控制系統(tǒng)(Aviation Data Management And Control System，ADMACS)和艦船綜合信息系統(tǒng)(Integrated Shipboard Information System，ISIS)，這是第一次嘗試在美海軍艦船上建立整體數(shù)據(jù)庫(kù)和分布式數(shù)據(jù)共享的系統(tǒng)，用來管理艦載機(jī)的飛行與航母甲板的布列調(diào)運(yùn)。

目前ADMACS已升級(jí)至3.0版本。如圖2所示，前兩個(gè)版本通過在艦載機(jī)上安裝具有標(biāo)識(shí)的GPS，提供實(shí)時(shí)顯示位置狀態(tài)信息和數(shù)據(jù)共享的功能以及記錄飛機(jī)的起降操作，但由于沒有智能規(guī)劃和調(diào)度的能力，也經(jīng)常被稱為“數(shù)字化的占卜板”。為彌補(bǔ)這項(xiàng)不足，3.0版本增加了艦載機(jī)輔助定位和移動(dòng)路徑規(guī)劃功能，將一些復(fù)雜的排列和計(jì)算工作交給計(jì)算機(jī)完成，為航母的調(diào)運(yùn)指揮官提供布列調(diào)運(yùn)的意見和方案，2010年“林肯”號(hào)航空母艦已全面安裝該版本系統(tǒng)。由此可見，航母甲板調(diào)度指揮方式向智能自動(dòng)化過渡，已成為不可阻擋的發(fā)展趨勢(shì)。

2 艦載機(jī)甲板停放布列

2.1 艦載機(jī)甲板停放布列的特點(diǎn)

航母的作戰(zhàn)能力主要取決于其搭載的艦載機(jī)，以尼米茲級(jí)航空母艦為例，其飛行甲板停放的艦載機(jī)一般在45～50架左右，占艦載機(jī)總數(shù)的60%以上。飛行甲板能停放飛機(jī)的最大數(shù)量決定了一次放飛和回收飛機(jī)數(shù)量的上限，也就決定了一個(gè)攻擊波次最多能夠出動(dòng)飛機(jī)的數(shù)量。

圖2 ADMACS

通常，飛行甲板停放飛機(jī)有以下特點(diǎn):

1)停放飛機(jī)的機(jī)種應(yīng)能滿足攻擊波次出動(dòng)飛機(jī)的需要，也就是說，停放飛機(jī)的機(jī)種是有一定搭配要求的;

2)停放在飛行甲板上待飛的飛機(jī)一般只需要作一些常規(guī)的檢測(cè)和后勤保障，通常它們是可以隨時(shí)執(zhí)行任務(wù)的;

3)停放在飛行甲板上的飛機(jī)既不能影響機(jī)群的起飛，又不能影響機(jī)群的降落，因而艦載機(jī)的停放布列需要有適合于機(jī)群起飛或機(jī)群降落的幾種不同的方案。

艦載機(jī)在飛行甲板和機(jī)庫(kù)的停放布列研究，目的是針對(duì)不同的任務(wù)需求，充分利用甲板空間，在盡可能多停放艦載機(jī)的情況下，使艦載機(jī)的出動(dòng)能力(速度和數(shù)量)達(dá)到最優(yōu)。

2.2 艦載機(jī)甲板停放布列優(yōu)化方法

2.2.1 空間利用率優(yōu)化方法

空間利用率優(yōu)化問題也稱裝箱問題(Bin Packing，BP)，屬于一種 NP難度問題［7-8］。按空間性質(zhì)可以劃分為三維BP問題和二維BP問題，按裝載物的形狀特性又可以劃分為規(guī)則體的BP問題和不規(guī)則體的BP問題［9］。由于艦載機(jī)在飛行甲板的停放布列采用平面的方式，所以可以劃分為一類特殊二維不規(guī)則體的BP問題。

目前二維不規(guī)則物體的空間利用率方法有很多，但沒有在艦載機(jī)布列問題上得到應(yīng)用。Ugur對(duì)比了多種二維BP算法，并詳細(xì)分析了影響這些算法效果的參數(shù)［17］。Epstein用圖形著色方法研究帶沖突的二維正方形BP問題，計(jì)算速度快，但應(yīng)用范圍很難擴(kuò)展［18］。Ping Chen分別采用禁忌搜索、遺傳算法和貪婪法研究二維不規(guī)則形狀的BP問題，詳細(xì)給出了求解過程，并列出了貪婪法的實(shí)驗(yàn)結(jié)果［19］。Hirokazu用模擬退火方法研究工業(yè)制造領(lǐng)域中的三維模塊BP問題，并提出一種擴(kuò)展的邊界切割網(wǎng)格方法(Bounded-Sliceline Grid)作為新的拓?fù)浣Y(jié)構(gòu)編碼方式［20］。Vincent Y等人采用啟發(fā)式順序遺傳算法研究三維BP問題，避免了沖突檢測(cè)過程，提高了計(jì)算效率［21］。Gyorgy研究了帶拒絕懲罰的BP問題，其目標(biāo)是使所用容器數(shù)量與被拒絕裝載物懲罰值的乘積最小，此外他還分別設(shè)計(jì)了適用于在線和離線的BP算法［22］。Correa隨后進(jìn)一步優(yōu)化了在線離線 BP算法，并考慮了可變?nèi)莘e的 BP問題［23］。Stefan考慮裝填物體是否可旋轉(zhuǎn)而用相應(yīng)的矩形代替原不規(guī)則物體［10］。

綜合上述研究，對(duì)于像艦載機(jī)這樣的復(fù)雜不規(guī)則物體，目前的一般做法是將原物體簡(jiǎn)化(如矩形)，建立其數(shù)學(xué)、仿真模型提出的算法進(jìn)行布置，然后結(jié)果中的簡(jiǎn)化物體還原為實(shí)際物體，最后通過實(shí)驗(yàn)驗(yàn)證。

2.2.2 空間布局設(shè)計(jì)方法

空間布局設(shè)計(jì)(Layout Design)主要面向物流倉(cāng)儲(chǔ)領(lǐng)域中的訂單揀貨問題(Order Picking)，即設(shè)計(jì)一種倉(cāng)儲(chǔ)空間布局模型，使揀貨的成本最優(yōu)化。也可稱作內(nèi)部布局設(shè)計(jì)或巷道結(jié)構(gòu)問題，涉及存儲(chǔ)區(qū)塊數(shù)量的確定，每個(gè)揀貨區(qū)中巷道數(shù)量、長(zhǎng)度和寬度的確定，如圖3所示，目的就是在給定的約束條件和需求情況下，關(guān)于某個(gè)確定的目標(biāo)函數(shù)，找到一個(gè)最好的倉(cāng)儲(chǔ)布局，一般其目標(biāo)函數(shù)就是行走距離［23］。

圖3 訂單揀貨倉(cāng)儲(chǔ)的布局設(shè)計(jì)

關(guān)于空間布局設(shè)計(jì)的文獻(xiàn)并不豐富。1980年Bassan研究了不同的平行通道布局以及路徑對(duì)綜合成本的影響［24］。Rosenblatt利用分析和仿真方法研究?jī)?nèi)部存儲(chǔ)策略對(duì)揀貨成本的影響［25］，隨后他又檢驗(yàn)了隨機(jī)需求對(duì)布局和存儲(chǔ)容量的影響［26］。Petersen提出了一個(gè)非線性目標(biāo)函數(shù)，用來確定隨機(jī)存儲(chǔ)倉(cāng)庫(kù)內(nèi)使平均揀貨距離最小的通道結(jié)構(gòu)［27］。Roodbergen同樣把最小化平均路徑長(zhǎng)度作為主要目標(biāo)，通過仿真，針對(duì)隨機(jī)存儲(chǔ)策略和基于周轉(zhuǎn)率的儲(chǔ)位分配策略，研究了巷道的長(zhǎng)度和數(shù)量對(duì)總行走時(shí)間的影響［28］。Carom F在基于體積指標(biāo)的存儲(chǔ)分配策略下考慮了一個(gè)具有中間橫道的兩個(gè)區(qū)的倉(cāng)庫(kù) ，而Tho Le則主要關(guān)注分類存儲(chǔ)策略［30］。Kevin對(duì)人們一直用平行通道設(shè)計(jì)倉(cāng)庫(kù)布局這一傳統(tǒng)提出了質(zhì)疑，研究了用斜線通道布局結(jié)構(gòu)優(yōu)化訂單揀貨系統(tǒng)［31］。

2.3 小結(jié)

艦載機(jī)的停放布列設(shè)計(jì)與倉(cāng)庫(kù)的空間布局設(shè)計(jì)有些相似，其目的都是通過對(duì)空間布局的設(shè)計(jì)，獲得對(duì)期望目標(biāo)(出動(dòng)時(shí)間和搬運(yùn)成本)的優(yōu)化，但二者之間又存在很大的區(qū)別。

首先，航母甲板的空間環(huán)境比倉(cāng)庫(kù)要復(fù)雜得多，要考慮的因素更多，必須按照一定的規(guī)則在某些指定的停機(jī)位停放。其次，飛行甲板和機(jī)庫(kù)甲板空間相對(duì)與一般的倉(cāng)庫(kù)比較狹小，靈活性、安全性等方面的要求卻比倉(cāng)庫(kù)嚴(yán)格很多。在停放數(shù)量和移動(dòng)通道的取舍方面，必須做出合理的分配，要求在緊急情況時(shí)能夠快速出動(dòng)的條件下，盡可能多停放飛機(jī)。第三，航母甲板的空間比較難劃分，且一般存在多種用途(如尼米茲級(jí)航母的前跑道在非緊急情況下經(jīng)常停放大量的艦載機(jī)，而且飛機(jī)之間不留通道);倉(cāng)庫(kù)則一般采用規(guī)則的布局方式，需要考慮的因素相對(duì)較少。

雖然艦載機(jī)的停放布列設(shè)計(jì)與倉(cāng)庫(kù)的空間布局設(shè)計(jì)有許多的不同之處，但二者在本質(zhì)上屬于同一種空間布局問題，只要將航母甲板的空間環(huán)境分析清楚，確定各種約束條件，建立合適的空間布局模型，再經(jīng)過多次的仿真實(shí)驗(yàn)和改進(jìn)，可以達(dá)到對(duì)艦載機(jī)停放布列的優(yōu)化研究目的。

3 艦載機(jī)甲板移動(dòng)路徑規(guī)劃

3.1 艦載機(jī)甲板移動(dòng)路徑規(guī)劃特點(diǎn)

艦載機(jī)的甲板移動(dòng)路徑規(guī)劃是指艦載機(jī)遵循某些規(guī)則，采用滑行或牽引的方式，從甲板上的一個(gè)地方到另一個(gè)地方的路徑規(guī)劃過程，屬于二維空間的線性移動(dòng)問題。航母甲板空間相對(duì)比較狹小、設(shè)備復(fù)雜、人員眾多，艦載機(jī)的調(diào)動(dòng)過程除了要求盡量縮短路徑外，更需要避免相互碰撞并確保人員安全。

目前的艦載機(jī)在甲板的移動(dòng)過程一般采用人工指揮的方式，由甲板操作人員指揮艦載機(jī)或牽引車進(jìn)行移動(dòng)。這種方式不僅效率低，而且由于指揮員視線阻擋等問題，經(jīng)常造成飛機(jī)的刮擦碰撞甚至人員的傷亡。美軍為減少艦載機(jī)甲板操作中的事故發(fā)生，應(yīng)用了一種持續(xù)監(jiān)控系統(tǒng)(Persistent Monitoring System)［6］。該系統(tǒng)結(jié)合了艦載機(jī)GPS定位、甲板移動(dòng)路徑規(guī)劃、碰撞事故檢測(cè)與報(bào)警等功能，為提高艦載機(jī)甲板作業(yè)效率和減少事故發(fā)生起到了一定的積極作用。

由于航母甲板環(huán)境的特殊性，特別是作戰(zhàn)時(shí)的高度動(dòng)態(tài)和不確定性，艦載機(jī)在甲板的移動(dòng)路徑問題屬于局部環(huán)境已知，但移動(dòng)過程中的變量、條件不確定的實(shí)時(shí)路徑優(yōu)化問題，該問題包括空間環(huán)境的判斷和建模、碰撞檢測(cè)和路徑規(guī)劃算法的選擇等方面。

3.2 移動(dòng)路徑規(guī)劃研究方法

國(guó)內(nèi)外對(duì)路徑規(guī)劃方法進(jìn)行過大量的研究，主要包括:人工勢(shì)場(chǎng)法、模糊邏輯算法、智能計(jì)算方法、路標(biāo)法以及基于偽譜法的最優(yōu)控制方法等。

人工勢(shì)場(chǎng)法最先由Khatib于20世紀(jì)80年代中期提出，它不需要利用圖形的形式表示規(guī)劃空間，而是將物體的運(yùn)動(dòng)看成是兩種力作用的結(jié)果［32］。其運(yùn)動(dòng)軌跡就是最終要找的路線，該方法規(guī)劃速度快，但可能找不到路徑。

模糊邏輯算法［33］基于實(shí)時(shí)傳感信息，參考人的駕駛經(jīng)驗(yàn)，通過查表得到規(guī)劃信息，實(shí)現(xiàn)局部路徑規(guī)劃。該方法克服了人工勢(shì)場(chǎng)法易產(chǎn)生的局部極值問題，適用于時(shí)變未知環(huán)境下的路徑規(guī)劃，實(shí)時(shí)性較好。

智能計(jì)算方法主要包括神經(jīng)網(wǎng)絡(luò)算法、蟻群算法、進(jìn)化算法和粒子群算法等。神經(jīng)網(wǎng)絡(luò)是在生物功能啟示下建立起來的一種計(jì)算方法，Hopfield利用神經(jīng)網(wǎng)絡(luò)成功解決旅行商問題，其缺點(diǎn)是計(jì)算量太大［34］。蟻群算法模擬蟻群的行為尋找優(yōu)化路徑［35］，具有很強(qiáng)的發(fā)現(xiàn)較好解的能力，不容易陷入局部最優(yōu)，但搜索時(shí)間較長(zhǎng)。進(jìn)化計(jì)算［36］和粒子群算法［37］具有較強(qiáng)的魯棒性，對(duì)于無法用數(shù)學(xué)模型精確描述或參數(shù)事先無法知道的情況也有較好的應(yīng)用效果，但問題規(guī)模過大時(shí)經(jīng)常導(dǎo)致算法收斂速度過慢或者得到的解不準(zhǔn)確，此外還需要調(diào)整許多參數(shù)。

表1 各種方法的對(duì)比

路標(biāo)法(Roadmap)通過建立不與障礙碰撞的全局子目標(biāo)，再用局部規(guī)劃方法搜索［38］。這種方法計(jì)算代價(jià)較高，而且不保證具備完備解，適用于靜態(tài)環(huán)境而不適合在線規(guī)劃。

基于偽譜法的最優(yōu)控制方法解決路徑規(guī)劃問題是近幾年發(fā)展起來的一種新的優(yōu)化方法，優(yōu)點(diǎn)是求解精度高、收斂速度快。常見的偽譜法包括:Chebyshev偽譜法(CPM)、Legendre偽譜法(LPM)、Radau偽譜法(RPM)和Gauss偽譜法(GPM)，Huntington對(duì)比了上述幾種方法，證明了GPM具備較高的精度和收斂速度，而且在處理初始終端約束方面具有一定的優(yōu)勢(shì)［39］。Ross等人開發(fā)了基于偽譜法的Matlab插件DIDO［40-42］，并將其應(yīng)用在了艦載機(jī)甲板移動(dòng)問題上，如圖4所示。

圖4 基于DIDO的艦載機(jī)甲板移動(dòng)路徑規(guī)劃仿真應(yīng)用

3.3 小結(jié)

艦載機(jī)在甲板的移動(dòng)路徑規(guī)劃是路徑規(guī)劃領(lǐng)域的新問題，主要難點(diǎn)在于飛行甲板環(huán)境復(fù)雜，艦載機(jī)移動(dòng)需要根據(jù)環(huán)境動(dòng)態(tài)變化。此外，甲板空間的構(gòu)造，艦載機(jī)和牽引車的運(yùn)動(dòng)學(xué)特性，以及人員活動(dòng)和各種資源的約束都是解決這一問題必須考慮的內(nèi)容。

4 艦載機(jī)甲板作業(yè)調(diào)度優(yōu)化

航母艦載機(jī)的甲板作業(yè)調(diào)度是指在有限的時(shí)間、空間和資源約束條件下，以提高飛機(jī)的起降能力和保障作戰(zhàn)效果為目標(biāo)，對(duì)艦載機(jī)的甲板操作流程或者行動(dòng)過程進(jìn)行優(yōu)化，是航空母艦布列調(diào)運(yùn)乃至作戰(zhàn)指揮的關(guān)鍵問題。它涉及多架艦載機(jī)在多種資源之間的協(xié)調(diào)、駐留、起降以及維修保障等甲板作業(yè)，屬于運(yùn)籌學(xué)中的動(dòng)態(tài)調(diào)度問題。目前常用的動(dòng)態(tài)調(diào)度方法包括:最優(yōu)化方法、啟發(fā)式方法、仿真方法、神經(jīng)網(wǎng)絡(luò)方法、智能搜索方法以及Multi-Agent方法。

最優(yōu)化方法主要包括數(shù)學(xué)規(guī)劃(動(dòng)態(tài)規(guī)劃、混合整數(shù)線型規(guī)劃等)、分支定界法和削去法等。這類方法通常基于某些簡(jiǎn)化的假設(shè)，進(jìn)而產(chǎn)生一個(gè)最優(yōu)化調(diào)度方案。但這類方法大多基于某些理想化的假設(shè)，不能充分表達(dá)航母甲板復(fù)雜環(huán)境的隨機(jī)性和動(dòng)態(tài)性，所以單獨(dú)使用這類方法解決動(dòng)態(tài)調(diào)度方法是不現(xiàn)實(shí)的［46］。

啟發(fā)式方法并不企圖在多項(xiàng)式時(shí)間內(nèi)求得問題的最優(yōu)解，而是在計(jì)算時(shí)間和調(diào)度效果之間進(jìn)行折中，以較小的計(jì)算量來得到滿意結(jié)果［47］。但由于它通常僅對(duì)一個(gè)目標(biāo)提供可行解，并且缺乏對(duì)整體性能的有效把握和預(yù)見，所以在實(shí)際應(yīng)用中常將它與其他方法結(jié)合使用。

仿真方法是動(dòng)態(tài)調(diào)度研究中最常用的方法。該方法通過建模對(duì)實(shí)際調(diào)度環(huán)境進(jìn)行模擬［48］，從而避開了對(duì)調(diào)度問題進(jìn)行理論分析的困難。在缺乏有效的理論分析的情況下，仿真是一種比較好的方法。

神經(jīng)網(wǎng)絡(luò)方法和職能搜索方法是研究動(dòng)態(tài)調(diào)度問題常用的方法，研究中應(yīng)用最多的是BP網(wǎng)［49］、模擬退火、禁忌搜索和遺傳算法等［50］，由于這些方法具有計(jì)算速度快且易與其它算法相結(jié)合的優(yōu)點(diǎn)，非常適合于解決動(dòng)態(tài)調(diào)度問題。

Multi-Agent方法特別適用于解決復(fù)雜問題，尤其是那些經(jīng)典方法無法解決的單元間有大量交互作用的問題［51］。其優(yōu)點(diǎn)是速度快、可靠性高、可擴(kuò)展性強(qiáng)、能處理帶有空間分布的問題、對(duì)不確定性數(shù)據(jù)和知識(shí)有較好的容錯(cuò)性。

目前關(guān)于艦載機(jī)的調(diào)度問題研究主要偏向如何使跑道利用率最高或者飛機(jī)著陸時(shí)間最短等問題［11-12］，與航母艦載機(jī)作業(yè)這種需要實(shí)時(shí)、自適應(yīng)并且多階段的動(dòng)態(tài)調(diào)度還有一定距離。針對(duì)這一問題，MIT的Ryan等人［14-16］通過參與DCAP的開發(fā)，研究基于Markov決策過程的艦載機(jī)甲板作業(yè)行動(dòng)過程優(yōu)化(如圖5所示)。他們根據(jù)航母甲板特點(diǎn)，將各艦載機(jī)、彈射器、阻攔裝置狀態(tài)細(xì)分，建立Markov狀態(tài)轉(zhuǎn)移模型，最后采用反向強(qiáng)化學(xué)習(xí)(或稱為學(xué)徒學(xué)習(xí))方法獲取行動(dòng)過程優(yōu)化方案。馮強(qiáng)［13］應(yīng)用多Agent技術(shù)分析建立了艦載機(jī)動(dòng)態(tài)調(diào)度模型，研究其協(xié)同機(jī)制和調(diào)度算法并進(jìn)行了仿真驗(yàn)證。

圖5 DCAP

5 結(jié)束語(yǔ)

本文在分析美軍現(xiàn)代航空母艦布列調(diào)運(yùn)管理方式和發(fā)展趨勢(shì)的基礎(chǔ)上，將空間布局、路徑規(guī)劃以及甲板作業(yè)調(diào)度作為研究艦載機(jī)布列調(diào)運(yùn)優(yōu)化的主要途徑，總結(jié)了目前國(guó)內(nèi)外對(duì)這三方面研究的情況。由于美軍航母極具代表性，本文并未介紹其他國(guó)家航母的布列調(diào)運(yùn)情況。對(duì)于我國(guó)正在進(jìn)行的航母發(fā)展事業(yè)，應(yīng)從美航母的作戰(zhàn)應(yīng)用中汲取經(jīng)驗(yàn)，在艦載機(jī)的布列調(diào)運(yùn)優(yōu)化方面，可進(jìn)一步開展以下研究:

1)提高停放布列和路徑規(guī)劃的智能化程度

利用空間布局和路徑規(guī)劃技術(shù)，結(jié)合數(shù)據(jù)處理能力，由計(jì)算機(jī)快速為艦載機(jī)指定停放位，減少人工規(guī)劃造成的重定位問題;根據(jù)艦載機(jī)的環(huán)境信息，實(shí)時(shí)規(guī)劃調(diào)運(yùn)路徑，縮短移動(dòng)時(shí)間，避免碰撞等事故的發(fā)生。

2)提高甲板作業(yè)的動(dòng)態(tài)調(diào)度能力

航母的甲板作業(yè)涉及多艦載機(jī)與多資源之間的協(xié)調(diào)，包括起降、停放、調(diào)運(yùn)以及維護(hù)保障等多種作業(yè)。運(yùn)用多種動(dòng)態(tài)調(diào)度方法優(yōu)化甲板作業(yè)和行動(dòng)過程，將對(duì)提高航母的作戰(zhàn)能力起到重要的作用。

［1］孫詩(shī)南.現(xiàn)代航空母艦［M］.上海:上海科學(xué)普及出版社，1998.

［2］Timothy Thate.Requirements for Digitized Aircraft Spotting(OUIJA)Board for Use on U.S.Navy Aircraft Carriers［D］.Naval Postgraduate School，2002.

［3］Navair 00-80T-105，CV Natops Manual.Department of the Navy Chief of Naval Operations 2000，Navy Pentagon Washington［S］.D.C.20350-2000.

［4］Commander，Naval Air Systems Command.“CV Flight/Hangar Deck NATOPS Manual”［S］.2005.NAVAIR 00-80T-120.

［5］李正國(guó).美海軍航母戰(zhàn)斗群戰(zhàn)術(shù)［M］.北京:空軍指揮學(xué)院，2005.

［6］Jeffrey S.Johnston.A Feasibility Study of a Persistent Monitoring System for the Flight Deck of U.S.Navy Aircraft Carriers［D］.DEPARTMENT OF THE AIR FORCE AIR UNIVERSITY，2009.

［7］Dowsland KA，Dowsland W B.Packing problems Journal of Operational Research［J］.1992，56:2-14.

［8］Garey M R and Johnson D S.Computer and Intractability:A Guide to the Theory of NP-Completeness［J］.New York，1979.

［9］王彩紅.分布式環(huán)境下人機(jī)協(xié)同的智能布置設(shè)計(jì)理論與方法的研究［D］.北京:北京交通大學(xué)，2007.

［10］Stefan Jakobs.Theory and Methodology on genetic algorithms polygons［J］.European Journal of Operational Research，1996:88.

［11］Irene Moser.Solving Dynamic Single-Runway Aircraft Landing Problems With Extremal Optimisation［C］.Proceedings of the 2007 IEEE Symposium on Computational Intelligence in Scheduling，2007.

［12］張洪海.多跑道著陸飛機(jī)協(xié)同調(diào)度多目標(biāo)優(yōu)化［J］.西南交通大學(xué)學(xué)報(bào)，2009，44(3):6-7.

［13］馮強(qiáng).基于MAS的艦載機(jī)動(dòng)態(tài)調(diào)度模型研究［J］，航空學(xué)報(bào)，2009(9):6-11.

［14］Jason C.Ryana.Designing an Interactive Local and Global Decision Support System for Aircraft Carrier Deck Scheduling［C］.AIAA，2011.

［15］Bernard Michini.A Human-Interactive Course of Action Planner forAircraftCarrierDeck Operations［C］.AIAA，2011.

［16］Rajarshi Ghosh Dastidar.A Queueing Network Based Approach to Distributed Aircraft Carrier Deck Scheduling［C］.AIAA:2011-1514.

［17］Ugur Dogrusoz.Two-dimensional Packing Algorithms for Layout of Disconnected Graphs［J］.Information Sciences，143(2002):147-158.

［18］Leah Epstein，Asaf Levin.Two-dimensional packing with conflicts［C］.Acta Informatica(2008)45:155-175 DOI 10.1007/s00236-007.

［19］Ping Chen，Zhaohui Fu.Two-Dimensional Packing For Irregular Shaped Objects［C］.Proceedings of the 36th Hawaii International Conference on System Sciences(HICSS'03)0-7695-1874-5/0.

［20］Hirokazu Yamagishi.Three Dimensional Module Packing by Simulated Annealing［J］.0-7803-9363-5/05 IEEE.

［21］Vincent Y.Blouin.Three-Dimensional Packing by a Heuristic-based Sequential Genetic Algorithm［C］.11th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference 6-8 September 2006，Portsmouth，Virginia.

［22］Gyorgy Dosa.Bin Packing Problems with Rejection Penalties and Their Dual Problems［J］.Information and Computation，204(2006):795-815.

［23］Correa.Bin Packing with Controllable Item Sizes［J］.Information and Computation，206(2008):1003-1016.

［24］Bassan，Y.，Roll，Y.，Rosenblatt，M.J.Internal layout design of a warehouse［J］.IIE Transactions，1980，12(4):317-322.

［25］Rosenblatt，M.J.and Roll，Warehouse design with storage policy considerations［J］.International Journal of Production Research，1984，22(5):809-821.

［26］Rosenblatt，M.J.and Roll，Y.Warehouse capacity in a stochastic environment［J］.International Journal of Production Research，1988，26(12):1847-1851.

［27］Petersen，C.G.Considerations in order picking zone configuration［J］.InternationalJournalofOperations＆Production Management，2002，27(7):793-805.

［28］Roodbergen，K.J.Layout and routing methods for warehouses［D］.Erasmus Research Institute of Management(ERIM)，2001.

［29］Carom F.，Marchet，G and Perego，A.Optimal layout in low-level picker-to-part systems［J］，International Journal of Production Research，2000，38(1):101-117.

［30］Tho Le-Due，Design and control of efficient order picking processes［D］，Erasmus University Rotterdam，2005.

［31］KEVIN R.GUE，Aisle configurations for unit-load warehouses［J］，IIE Transactions(2009)41，171-182

［32］Khatib，O，Real-time obstacle avoidance for manipulators and mobile robots，The International Journal Robotics Research［J］，5(1):90-98，1986.

［33］Nelson，H.C.，Ye，Y C.，An intelligent mobile vehicle navigator based on fuzzy logic and reinforcement learning［J］，IEEE Trans.on Systems，Man and Cybernetics，Part B:Cybernetics，29(2):314-321，1999.

［34］Lu W C，Mora-Camino F，Achaibou K.A flatness based flight guidance control using neural networka［C］//IEEE the 24th DigitalAvionics Systems Conference，2005.

［35］V Nauyen H，V Ngo A，L SeungGwan，et al.Obstacle A-voidance Path Planning for Mobile Robot Based on Multi Colony Ant Algorithm［C］.First International Conference on Advances in Computer-Human Interaction，2008.

［36］Nikolos I K，Valavanis K P.Evolutionary algorithm based offline/online path planner for OAV navigation［J］.IEEE Transactions on Systems，Man，and Cybernetics，2003，33(6):898-912.

［37］Foo J L，Knutzon J，Kalivarapu V，et al.Path planning of unmanned aerial vehicles using E-splines and particle swarm optimization［J］.Journal of Aerospace Computing，Information，and Communication，2009(6):271-290.

［38］Kavraki，L.E.，5vestka，P.，Latombe，J.C.and Overmars，M.H.，Probabilistic roadmaps for path planning in high-dimensional configuration spaces［J］，IEEE Trcans.on Robotics and Automation，12(4):566-580，1996.

［39］Huntington G T，Benson D，Rao A V.A comparison of accuracy and computational efficiency of three pseudospectral methods［R］.AIAA-2007-6405，2007.

［40］Ross，I.M.User's Manual for DIDO:A MATLAB Application Package for Solving Optimal Control Problems［R］.Elissar，Monterey，CA，2007.Document TR 705.

［41］L.Ryan Lewis，I.Michael Ross.Pseudospectral Motion Planning Techniques for Autonomous Obstacle［J］.Proceedings of the 46th IEEE Conference on Decision and Control New Orleans，LA，USA，Dec.12-14，2007.

［42］Michael A.Hurni，Pooya Sekhavat，Mark Karpenko，and I.Michael Ross.Autonomous Multi-Vehicle Formations Using A Pseuodospectral Optimal Control Framework［C］.2010 IEEE/ASME International Conference on Advanced IntelligentMechatronicsMontreal， Canada， July 6-9，2010.

［43］Jeffrey S.Feasibility Study of Global-Positioning-System-Based Aircraft-Carrier Flight-Deck Persistent Monitoring System［C］.JOURNAL OF AIRCRAFT Vol.47，No.5，September—October 2010.

［44］Giardina，Thomas J.An Interactive Graphics Approach to the Flight Deck Handling Problem.Master's thesis［R］，Naval Postgraduate School，1974.

［45］Johnson，Alan K.and Kriston P.Woolley.A Simulation of a Computer Graphics-Aided Aircraft Handling System［R］.Master's thesis，Naval Postgraduate School，1975.

［46］Matsuura H，Tsubone H，Kanezashi M.Sequencing，dispatching and switching in dynamic manufacturing environment［J］.Int J of Prod Res，1993，31(7):1671-1688.

［47］Johnson S M.Optimal two and three-stage production schedules with setup times included［J］.Naval Res Log Quart，1954，1(1):61-8.

［48］Liu H J，artificial Dong Jian.Dispatching rule selection using neural scheduling［J］networks for dynamic planning and J of Intel Manuf，1996，7(2):243-50.

［49］Sim S K，Yeo K T，Lee W H.An expert neural network system for dynamic job shop scheduling［J］.Int J of Prod Res，1994，32(8):1759-1773.

［50］Lee C Y，Piramuthu S，Tsai Y K.Job shop scheduling with a genetic algorithm and machine learning［J］.Int J of Prod Res，1997，35(4):1171-1191.

［51］錢曉龍，唐立新，劉文新，動(dòng)態(tài)調(diào)度的研究方法綜述［J］.控制與決策，2001，16(2):3-5.