崔凱凱, 崔榮偉, 韓 維, 郭 放, 王毓麟, 劉 潔

(1. 海軍航空大學(xué)航空基礎(chǔ)學(xué)院, 山東 煙臺(tái) 264001; 2. 中國(guó)人民解放軍92942部隊(duì), 北京 100161; 3. 軍事科學(xué)院戰(zhàn)爭(zhēng)研究院, 北京 100850)

0 引 言

由于艦載機(jī)通常采用大機(jī)群回收的方式,其在進(jìn)入最終的著艦下滑道之前必須要根據(jù)相應(yīng)的指標(biāo)要求進(jìn)行回收排序,以確定機(jī)群中各架艦載機(jī)的著艦順序。因此,對(duì)著艦回收排序算法的研究有利于減少艦載機(jī)的回收耗時(shí),提高回收任務(wù)的效能,保證飛行安全,同時(shí)也有利于后續(xù)保障和再出動(dòng)任務(wù)的進(jìn)行。飛機(jī)著陸調(diào)度(aircraft landing scheduling, ALS)是空中交通管制領(lǐng)域中的一個(gè)復(fù)雜問題[1],目前相關(guān)的研究主要集中在民用航空領(lǐng)域[2-6]。

文獻(xiàn)[2]通過序列二次規(guī)劃確定了高密度運(yùn)行條件下的最優(yōu)飛機(jī)著陸序列及相應(yīng)的飛行時(shí)間,并基于對(duì)排序結(jié)果的分析提出了3種排序規(guī)則。相關(guān)的蒙特卡羅模擬結(jié)果表明,通過2次簡(jiǎn)單的著陸順序交換,最多可節(jié)省17%的燃油消耗。文獻(xiàn)[3]基于任務(wù)完成總時(shí)間最短的目標(biāo)和滾動(dòng)時(shí)域思想設(shè)計(jì)了一種結(jié)合人工魚群和粒子群優(yōu)化(artificial fish particle swarm optimization, AFPSO)的飛機(jī)降落排序算法。與先到先服務(wù)方法相比,AFPSO算法在單跑道情況下可以使航班隊(duì)列著陸的總延遲時(shí)間減少36%。文獻(xiàn)[4]設(shè)計(jì)了一種用于減小飛機(jī)著陸總延遲時(shí)間的線性規(guī)劃方法,該方法通過貪婪式啟發(fā)算法給出了最大延遲時(shí)間上界的估計(jì)值,確保了混合整數(shù)線性規(guī)劃模型具有可行解,且該算法采用分枝定界策略對(duì)搜索樹節(jié)點(diǎn)進(jìn)行了修剪,提高了搜索效率,機(jī)場(chǎng)實(shí)際數(shù)據(jù)驗(yàn)算結(jié)果表明該算法相對(duì)于普通的線性規(guī)劃算法具有更強(qiáng)的優(yōu)化能力。文獻(xiàn)[5]借助單機(jī)調(diào)度中的準(zhǔn)則選擇方法確定了ALS問題中的多個(gè)待優(yōu)化目標(biāo)函數(shù),并采用包括帝國(guó)競(jìng)爭(zhēng)算法(imperialist competitive algorithm, ICA)在內(nèi)的多種求解算法對(duì)多目標(biāo)ALS問題進(jìn)行了求解。仿真計(jì)算結(jié)果表明,該方法能夠有效解決ALS多目標(biāo)優(yōu)化問題,在提高航班的準(zhǔn)點(diǎn)率和跑道利用率的同時(shí)減少了空中交管人員的工作量。文獻(xiàn)[6]基于ALS復(fù)合分派規(guī)則,設(shè)計(jì)了針對(duì)ALS問題的啟發(fā)式算法。仿真計(jì)算結(jié)果表明其所提出的算法相較于Lingo軟件的求解結(jié)果而言,平均每架航班的降落時(shí)間可以提前2.4 min。而文獻(xiàn)[7]則提出了一種CGIC(costs, generation rule, improvement heuristic, connection rule)啟發(fā)式算法以解決ALS問題。CGIC基于4種操作規(guī)則將ALS問題分解為兩個(gè)或多個(gè)子問題,從而降低了ALS問題的復(fù)雜性。仿真結(jié)果表明,即使在動(dòng)態(tài)情況下,CGIC依然可以獲得高質(zhì)量的調(diào)度求解方案,且計(jì)算時(shí)間滿足實(shí)時(shí)性要求。

與民航飛機(jī)有所不同,艦載機(jī)著艦時(shí)只有一條著艦跑道可以使用,且跑道的距離遠(yuǎn)遠(yuǎn)短于陸基機(jī)場(chǎng),發(fā)生逃逸或者復(fù)飛的概率要遠(yuǎn)遠(yuǎn)大于陸基飛機(jī)。同時(shí),艦載機(jī)執(zhí)行的是戰(zhàn)斗任務(wù),其在返航時(shí)很有可能存在戰(zhàn)損,且由于戰(zhàn)場(chǎng)形勢(shì)的多變,作戰(zhàn)任務(wù)時(shí)長(zhǎng)可能會(huì)超出預(yù)期,這將導(dǎo)致返航油量過低的情況。相比于經(jīng)濟(jì)效益,航母艦載機(jī)在進(jìn)行回收著艦時(shí)更加注重著艦方案是否有利于后續(xù)作戰(zhàn)和保障任務(wù)的高效執(zhí)行。目前來看,艦載機(jī)機(jī)群的著艦回收排序主要依靠人工調(diào)度實(shí)現(xiàn),即空管人員利用其所掌握的回收機(jī)群信息和以往的經(jīng)驗(yàn)綜合進(jìn)行判斷[8]。但采用人工調(diào)度的方式不僅增加了航母空管人員的負(fù)擔(dān),且當(dāng)待回收的艦載機(jī)種類較多、數(shù)量規(guī)模較大時(shí),該方式難以在短時(shí)間內(nèi)給出高效的著艦方案。此時(shí),空管人員為了保證回收安全,往往采用讓剩余油量少的艦載機(jī)先行著艦的方式[9],該方式雖然簡(jiǎn)單易行,但無法從整體上綜合考慮機(jī)群的著艦回收效能,局限性較大。

因而近年來,部分學(xué)者針對(duì)艦載機(jī)著艦回收調(diào)度問題也進(jìn)行了一定的研究。文獻(xiàn)[10]考慮了艦載機(jī)回收時(shí)的排隊(duì)特性以及著艦失敗的可能,對(duì)艦載機(jī)的著艦回收調(diào)度問題進(jìn)行了分析。文獻(xiàn)[11]針對(duì)艦載機(jī)回收時(shí)甲板跑道容量受限問題,比較了先到先服務(wù)、依據(jù)最早到達(dá)時(shí)間、滑動(dòng)時(shí)間窗口等3種算法的回收排序效果。仿真結(jié)果顯示滑動(dòng)時(shí)間窗口排序法計(jì)算量較小且具有較好的優(yōu)化效果,但文獻(xiàn)中所用的排序算法均利用了艦載機(jī)的預(yù)計(jì)到達(dá)時(shí)間,難以適用于艦載機(jī)大機(jī)群到達(dá)的情況[12]。文獻(xiàn)[13]針對(duì)典型的艦載機(jī)回收模式提出了一種考慮著艦失敗架次飽和度的回收調(diào)度策略,解決了著艦失敗隊(duì)列與首次著艦待機(jī)隊(duì)列之間可能出現(xiàn)的資源點(diǎn)爭(zhēng)奪問題。文獻(xiàn)[11,13]所提到的幾種排序算法以及空管人員所使用的“油少先著艦”排序方式本質(zhì)上都屬于啟發(fā)式算法,此類算法具有快速的響應(yīng)能力,但求解效果受主觀確定的啟發(fā)式規(guī)則的影響較大,且不能夠進(jìn)行迭代優(yōu)化。文獻(xiàn)[14]針對(duì)機(jī)群著艦回收排序問題,提出了一種基于蟻群算法的動(dòng)態(tài)排序算法,使艦載機(jī)機(jī)群能夠以最優(yōu)順序著艦。通過與最少燃料優(yōu)先服務(wù)的方法和靜態(tài)蟻群排序算法相比較,驗(yàn)證了基于蟻群算法的動(dòng)態(tài)排序算法的優(yōu)勢(shì)。文獻(xiàn)[15]綜合考慮了著艦返航時(shí)艦載機(jī)的剩余油量、戰(zhàn)損情況等隨機(jī)性因素的影響,建立了相應(yīng)的著艦回收模型,用于對(duì)回收著艦的風(fēng)險(xiǎn)成本進(jìn)行優(yōu)化,并提出了一種帶有模擬退火機(jī)制的粒子群算法以對(duì)著艦回收排序問題進(jìn)行求解。文獻(xiàn)[16]將艦載機(jī)著艦回收調(diào)度問題抽象為隨機(jī)規(guī)劃問題,并提出了一種基于著艦優(yōu)先序指標(biāo)的蒙特卡羅-差分進(jìn)化實(shí)時(shí)排序調(diào)度算法。仿真結(jié)果顯示在相同的初始條件下,利用蒙特卡羅-差分進(jìn)化算法求解得到的目標(biāo)函數(shù)值呈現(xiàn)出了較好的統(tǒng)計(jì)特性,且算法的收斂速度較快。文獻(xiàn)[12]針對(duì)艦載機(jī)著艦回收調(diào)度問題,構(gòu)造了一種考慮加權(quán)完成時(shí)間的目標(biāo)函數(shù),并設(shè)計(jì)了一種經(jīng)過改進(jìn)的人工蜂群算法對(duì)該問題進(jìn)行求解,經(jīng)仿真對(duì)比驗(yàn)證了其所提出的算法具備較強(qiáng)的優(yōu)化能力和魯棒性。

上述研究很少考慮空中加油對(duì)著艦方案的影響,使得其對(duì)返航艦載機(jī)油量有著較大的限制,適用場(chǎng)景相對(duì)受限。且上述調(diào)度求解方法從本質(zhì)上而言大多屬于元啟發(fā)式算法,而元啟發(fā)式算法在迭代求解的過程中需要進(jìn)行大量的隨機(jī)搜索操作,當(dāng)問題規(guī)模較大時(shí),其搜索效率和搜索穩(wěn)定性會(huì)變差[17]。

針對(duì)啟發(fā)式算法以及元啟發(fā)式算法的不足,文獻(xiàn)[18]提出了超啟發(fā)式算法的概念,超啟發(fā)式算法的提出為復(fù)雜調(diào)度問題提供了一種新的求解思路。該算法通過高層次的啟發(fā)式策略來操縱若干個(gè)低層次啟發(fā)式方法,從而生成新的尋優(yōu)算法,超參少且實(shí)用性較強(qiáng)[19],在近年來引起了廣泛的關(guān)注。其已被用于求解航母甲板作業(yè)調(diào)度[20]、自動(dòng)化碼頭箱位分配[21]、車輛取送貨路徑規(guī)劃[22]以及云計(jì)算調(diào)度[23]等眾多工程實(shí)踐領(lǐng)域,取得了理想的效果。進(jìn)一步,學(xué)者們將遺傳算法的優(yōu)化過程模擬到超啟發(fā)式算法上,形成了遺傳規(guī)劃(genetic programming, GP)算法[24],并將其廣泛應(yīng)用于項(xiàng)目調(diào)度問題。文獻(xiàn)[25]首次將超啟發(fā)式調(diào)度算法應(yīng)用于具有隨機(jī)工時(shí)的項(xiàng)目調(diào)度問題中,提出一種超啟發(fā)式集成遺傳規(guī)劃方法,通過進(jìn)化優(yōu)先級(jí)規(guī)則組合來求解隨機(jī)資源受限的項(xiàng)目調(diào)度問題。該算法通過3種不同的局部搜索方法來增加各代種群的多樣性。此外,算法還設(shè)計(jì)了一種序列投票機(jī)制來處理隨機(jī)資源受限的項(xiàng)目調(diào)度過程中的協(xié)同決策問題,仿真驗(yàn)證表明該算法相對(duì)于啟發(fā)式、元啟發(fā)式和單一超啟發(fā)式算法具有一定的優(yōu)勢(shì)。文獻(xiàn)[26]提出一種基于遺傳規(guī)劃的動(dòng)態(tài)車間調(diào)度算法,對(duì)最長(zhǎng)完工時(shí)間和平均延遲時(shí)間進(jìn)行了優(yōu)化,并借助排序規(guī)則的自動(dòng)生成機(jī)制,提高了車間調(diào)度算法在不同場(chǎng)景中的動(dòng)態(tài)適應(yīng)性。文獻(xiàn)[27]針對(duì)多技能資源約束項(xiàng)目調(diào)度問題提出了一種遺傳規(guī)劃超啟發(fā)式算法,其通過使用單個(gè)任務(wù)序列向量進(jìn)行編碼,并基于修復(fù)的解碼方式來生成可行的調(diào)度方案,仿真對(duì)比實(shí)驗(yàn)驗(yàn)證了該算法在求解效果和收斂速度方面的優(yōu)勢(shì)。除此之外,GP算法在其他一些項(xiàng)目調(diào)度問題中也獲得了良好的效果[28-30]。但目前尚未見有利用超啟發(fā)式算法對(duì)著艦回收調(diào)度問題進(jìn)行求解的相關(guān)文獻(xiàn)。

針對(duì)當(dāng)前艦載機(jī)著艦回收調(diào)度問題研究過程中存在的不足,本文建立了考慮空中加油條件的艦載機(jī)機(jī)群著艦回收調(diào)度問題模型,同時(shí)基于超啟發(fā)式思想設(shè)計(jì)了一種帶強(qiáng)制著艦規(guī)則的GP (GP with mandatory landing rules, MGP)算法,用于對(duì)著艦回收排序問題進(jìn)行求解。

1 艦載機(jī)機(jī)群回收排序問題模型

1.1 艦載機(jī)著艦回收排序問題分析

通常而言,艦載機(jī)返航的過程可分為4個(gè)階段,即引導(dǎo)段、待機(jī)段、進(jìn)場(chǎng)段和著艦段[31]。在通常情況下,當(dāng)艦載機(jī)飛行至距航母200 n mile的位置后,艦上的航管中心開始接管艦載機(jī)。

一般情況下,根據(jù)不同的天氣狀況及晝夜情況,固定翼艦載機(jī)的回收著艦?zāi)Ｊ娇煞譃?類。其中,第一類回收著艦?zāi)Ｊ揭髸冮g天氣狀況良好,能見度大于5 km,此時(shí)可采用目視進(jìn)場(chǎng)以及人工著艦的方式;當(dāng)航母上方云層的遮擋范圍大于5/8時(shí),一般采用第二類回收著艦?zāi)Ｊ?即采用儀表引導(dǎo)系統(tǒng)進(jìn)場(chǎng),并利用自動(dòng)著艦系統(tǒng)進(jìn)行著艦;當(dāng)航母上空300 m以上有云層或夜間著艦時(shí),通常采用第三類回收著艦?zāi)Ｊ健？梢?第三類回收方式適用于夜間和惡劣氣象條件下的著艦回收任務(wù),因此本文以第三類回收著艦?zāi)Ｊ綖槔芯颗炤d機(jī)的回收排序問題。

第三類回收著艦?zāi)Ｊ降娘w行航線如圖1所示。通常情況下,在航母左側(cè)距離航母約20 n mile的位置設(shè)置馬歇爾等待航線,即在1 800 m以上的空域按照300 m的高度差設(shè)計(jì)多層等待航線。相鄰馬歇爾等待航線之間的水平間隔為1 n mile。在未接到著艦指令時(shí),艦載機(jī)在馬歇爾等待航線上盤旋飛行,當(dāng)接到著艦許可指令后,艦載機(jī)從等待航線偏離點(diǎn)A處離開當(dāng)前等待航線,并以20 m/s的下滑速度經(jīng)過最底層等待航線的脫離點(diǎn)B(馬歇爾點(diǎn))后飛至進(jìn)場(chǎng)始發(fā)點(diǎn)C,之后以10 m/s的下滑速度左盤旋飛行,當(dāng)飛至艦尾后方約10 n mile的位置D時(shí),飛機(jī)的高度降至365 m,飛機(jī)轉(zhuǎn)入平飛狀態(tài),直至飛到艦尾后方3 n mile處的E點(diǎn)時(shí),自動(dòng)著艦系統(tǒng)開始工作,艦載機(jī)進(jìn)行下滑著艦飛行。如出現(xiàn)逃逸或復(fù)飛的情況,艦載機(jī)需要再次爬升至365 m的高度,之后按照復(fù)飛航線飛行并再次進(jìn)行著艦。

圖1 第三類回收著艦?zāi)Ｊ较碌娘w行航線圖Fig.1 Flight route map under the third type of carrier landing recovery mode

1.2 機(jī)群回收約束條件分析

為了保證機(jī)群的安全,艦載機(jī)在進(jìn)行回收排序的過程中,會(huì)面臨許多限制條件,本節(jié)將對(duì)該問題所涉及的限制條件逐個(gè)進(jìn)行分析。

1.2.1 完整度約束條件

艦載機(jī)在執(zhí)行作戰(zhàn)任務(wù)的過程中,經(jīng)常會(huì)出現(xiàn)一定程度的損傷,若損傷情況較為嚴(yán)重,則可能會(huì)影響艦載機(jī)的正常飛行或操縱。當(dāng)出現(xiàn)艦載機(jī)無法穩(wěn)定飛行或不能正常操縱艦載機(jī)的情況時(shí),通常需要聯(lián)系陸基機(jī)場(chǎng)進(jìn)行降落,但當(dāng)航母艦隊(duì)執(zhí)行遠(yuǎn)海作戰(zhàn)任務(wù)且在艦載機(jī)航程內(nèi)無可用的陸基機(jī)場(chǎng)時(shí),只能在航母甲板上進(jìn)行緊急降落。在緊急降落時(shí),需要將跑道附近的艦載機(jī)迅速轉(zhuǎn)運(yùn)至安全區(qū)域,并架起尼龍阻攔網(wǎng),待故障機(jī)拋掉其所搭載的武器燃料后實(shí)施緊急著艦。在故障機(jī)完成著艦后,甲板上的人員還要針對(duì)可能出現(xiàn)的突發(fā)狀況進(jìn)行滅活和人員救助等工作。由此可見,若將無法正常著艦的故障機(jī)安排在著艦回收序列中,會(huì)使機(jī)群著艦的連續(xù)性受到較大影響。因此,通常的處理方式是:① 若故障機(jī)具備空中逗留能力,則先讓其在空中盤旋等待,待其他正常機(jī)完成著艦后再安排故障機(jī)進(jìn)行著艦;② 若故障機(jī)無法在空中穩(wěn)定飛行,則將其安排在大機(jī)群之前進(jìn)行著艦。

本文中,用完整度WZi表示艦載機(jī)i的受損程度。完整度越高,表示受損程度越小,且只有當(dāng)完整度滿足一定的條件時(shí),才能將其安排進(jìn)著艦序列中,即WZi>WZmin。本文中,取WZmin=60%。

1.2.2 剩余油量約束條件

受艦載機(jī)起落架以及阻攔索承載能力的限制,艦載機(jī)在進(jìn)行著艦時(shí)通常面臨最大油量限制,即著艦載機(jī)i在其著艦時(shí)刻的剩余油量Ozj,i必須小于最大允許著艦油量Omax。同時(shí),由于艦載機(jī)在著艦過程中無法保證一次著艦成功,且當(dāng)前序飛機(jī)在著艦失敗后進(jìn)行二次著艦時(shí)有可能會(huì)占據(jù)后續(xù)飛機(jī)的航線。因此,在初始的著艦方案中,Ozj,i均應(yīng)大于某一最小安全裕度值Osafe。當(dāng)著艦方案生成后,由于著艦隊(duì)列內(nèi)可能會(huì)出現(xiàn)復(fù)飛或者逃逸的情況,這將會(huì)導(dǎo)致后續(xù)艦載機(jī)的實(shí)際著艦時(shí)刻較原有著艦方案有所推遲,但無論如何應(yīng)保證艦載機(jī)在進(jìn)行著艦時(shí),其剩余油量大于最小極限油量Omin。若經(jīng)判斷當(dāng)前飛機(jī)i的Ozj,i

Osafe=Off+Ocr+Omin

(1)

式中:Off、Ocr分別表示最長(zhǎng)復(fù)飛航線所需油耗和前序某一架次飛機(jī)復(fù)飛可能給后續(xù)飛機(jī)帶來的額外最大油耗。按照式(1)選取Osafe的實(shí)際意義在于:初始著艦方案中的飛機(jī)在不依賴空中加油的條件下,當(dāng)前序飛機(jī)中出現(xiàn)一次著艦失敗并重新著艦后,該架次飛機(jī)仍有一次著艦失敗并重新著艦的機(jī)會(huì),且其剩余油量可以保證艦載機(jī)在二次著艦仍然失敗后可以安全抵達(dá)空中加油位置,而不會(huì)出現(xiàn)油量耗盡的情況?？紤]到機(jī)群回收過程涉及到多種機(jī)型,且各機(jī)型的油耗速率不同,式(1)中的變量數(shù)值與飛機(jī)機(jī)型直接相關(guān)。為了便于處理,后續(xù)將剩余燃油油量轉(zhuǎn)換為剩余燃油可用時(shí)間來進(jìn)行處理。相應(yīng)地,Omin、Omax、Osafe、Off、Ocr可轉(zhuǎn)換為TOmin、TOmax、TOsafe、TOff、TOcr,即在后續(xù)的研究中,用剩余燃油可用時(shí)間來描述艦載機(jī)的剩余油量約束條件。記TOi為艦載機(jī)i在初始時(shí)刻的剩余燃油可用時(shí)間,則有:

(2)

式中:Oi表示艦載機(jī)i在初始時(shí)刻的剩余油量;yhi表示艦載機(jī)i的耗油率,其具體數(shù)值與艦載機(jī)的類型有關(guān)。

1.2.3 尾流間隔時(shí)間約束條件

艦載機(jī)在進(jìn)行順序著艦的過程中,為了避免由前序艦載機(jī)i所產(chǎn)生的飛行尾流對(duì)后續(xù)飛機(jī)j的影響,相鄰兩架飛機(jī)經(jīng)過航線上相同位置的時(shí)間必須滿足一定的間隔要求,這一限制即尾流間隔時(shí)間限制。一般情況下,尾流間隔時(shí)間的限制要求與前后兩架次飛機(jī)的類型有關(guān),表1給出了不同類型飛機(jī)之間的尾流間隔時(shí)間限制要求[8]。

表1 尾流間隔時(shí)間限制Table 1 Wake interval time limit

表1中的S、M和L分別表示小型、中型和大型艦載機(jī)。在實(shí)際著艦過程中,當(dāng)前續(xù)飛機(jī)完成著艦后,甲板上的工作人員需要進(jìn)行跑道清空以及阻攔索復(fù)位的工作。在此期間,不允許其他艦載機(jī)進(jìn)行著艦,但由于跑道清空的時(shí)間一般要小于艦載機(jī)尾流間隔時(shí)間限制[16],所以可認(rèn)為該約束已包含于尾流間隔約束中,而無需再進(jìn)行單獨(dú)考慮。

1.3 基于加權(quán)等待時(shí)間的回收調(diào)度評(píng)價(jià)指標(biāo)

第1.2節(jié)對(duì)艦載機(jī)機(jī)群回收排序問題中的約束條件進(jìn)行了分析,本節(jié)基于前述分析,建立了基于艦載機(jī)完整度、任務(wù)優(yōu)先級(jí)、剩余油量飛行時(shí)間、回收等待時(shí)間以及空中加油次數(shù)的回收排序調(diào)度評(píng)價(jià)指標(biāo)。下面對(duì)上述因素展開分析。

(1) 剩余油量飛行時(shí)間

基于第1.2節(jié)中的分析可知,在艦載機(jī)進(jìn)行著艦時(shí),其剩余油量必須滿足一定的限制,設(shè)有n架艦載機(jī)需要進(jìn)行回收,則在回收起始時(shí)刻,各架艦載機(jī)的剩余油量可飛行時(shí)間應(yīng)滿足TOsafe+TML

(3)

式中:j=1,2,…,n,表示艦載機(jī)的編號(hào)。由式(3)可知,艦載機(jī)的剩余油量可飛行時(shí)間越短,其著艦的緊迫度越高。

(2) 艦載機(jī)完整度

基于第1.2節(jié)中的分析可知,各架艦載機(jī)在參與回收時(shí),其完整度必須滿足WZi>WZmin,i=1,2,…,n。與剩余油量可飛行時(shí)間類似,當(dāng)艦載機(jī)的受損情況較為嚴(yán)重(即艦載機(jī)的完整度較小)時(shí),其所對(duì)應(yīng)的著艦緊迫度較高。所以,由WZi所決定的第i架艦載機(jī)的著艦緊迫度可表示為

(4)

(3) 后續(xù)任務(wù)優(yōu)先級(jí)

當(dāng)艦載機(jī)完成回收任務(wù)后,一般需要進(jìn)行機(jī)務(wù)檢查和保障,以使其快速恢復(fù)作戰(zhàn)能力并等待下次出動(dòng)。同時(shí),當(dāng)前波次返回的艦載機(jī)在后續(xù)階段可能需要執(zhí)行不同的任務(wù),而這些任務(wù)的緊迫程度往往也存在差異。這里將艦載機(jī)后續(xù)任務(wù)的緊迫程度用優(yōu)先級(jí)YXJi來表示,其中YXJi的取值為1～5的整數(shù),且取值越小,表示任務(wù)的緊迫程度越高,YXJi的具體數(shù)值可提前由艦面調(diào)度指揮人員根據(jù)任務(wù)的執(zhí)行需求情況給出?？紤]YXJi對(duì)著艦回收排序方案的影響,要求后續(xù)任務(wù)優(yōu)先級(jí)高的艦載機(jī)盡量先著艦?；诖?可以給出由YXJi所決定的第i架艦載機(jī)的著艦緊迫度:

(5)

(4) 回收等待時(shí)間

在艦載機(jī)機(jī)群進(jìn)行回收著艦的過程中,艦載機(jī)在著艦前的等待時(shí)間DTi是一項(xiàng)極為重要的指標(biāo)。嚴(yán)格來講,艦載機(jī)的等待時(shí)間應(yīng)記為從其進(jìn)入返航待機(jī)區(qū)開始到完成著艦的時(shí)間,但這樣一來,就需要考慮艦載機(jī)從進(jìn)入返航等待區(qū)到進(jìn)入相應(yīng)的馬歇爾等待航線的具體路線,這一過程的隨機(jī)性較大,且不屬于本文的研究范疇。進(jìn)一步,考慮到機(jī)群返回時(shí)各架飛機(jī)進(jìn)入返航區(qū)的時(shí)間差異較小,這里為了簡(jiǎn)化問題,以首架著艦機(jī)經(jīng)過馬歇爾點(diǎn)的時(shí)刻T0為計(jì)時(shí)起點(diǎn),計(jì)算艦載機(jī)的等待時(shí)間,即DTi=ZTi-T0。其中,ZTi表示第i架艦載機(jī)的著艦時(shí)刻。

基于上述指標(biāo)影響因素,設(shè)計(jì)如下回收著艦排序評(píng)價(jià)指標(biāo):

(6)

(5) 空中加油次數(shù)

雖然在剩余油量飛行時(shí)間部分已經(jīng)對(duì)艦載機(jī)的油量進(jìn)行了一定的限制,但是上述限制并不能保證每一架飛機(jī)都能夠?qū)崿F(xiàn)安全油量著艦,尤其是在機(jī)群規(guī)模較大或艦載機(jī)剩余油量普遍較少的情況下。此時(shí),在生成著艦排序方案時(shí),就極有可能出現(xiàn)部分艦載機(jī)燃油不足,無法實(shí)現(xiàn)安全油量著艦的情況。在不考慮前序飛機(jī)著艦失敗的情況下,若著艦方案中仍有艦載機(jī)無法實(shí)現(xiàn)安全油量著艦,則需要在著艦方案執(zhí)行的同時(shí)安排油量不足的艦載機(jī)進(jìn)行空中加油,待空中加油完畢后令其重新返回著艦序列,待未加油的艦載機(jī)完成著艦后再進(jìn)行著艦。

(7)

式中:nkj表示在著艦方案中需要進(jìn)行空中加油的艦載機(jī)數(shù)量。

1.4 艦載機(jī)機(jī)群回收排序調(diào)度模型

基于第1.2節(jié)和第1.3節(jié)的分析,可以將艦載機(jī)機(jī)群回收著艦排序調(diào)度問題概括為在保證飛行安全的前提下,通過合理安排艦載機(jī)的著艦順序,使得著艦排序評(píng)價(jià)指標(biāo)式(7)盡可能小。其決策變量可以用混合整數(shù)規(guī)劃(mixed integer programming, MIP)模型表示如下:

(8)

為了表達(dá)方便,式(8)中引入了編號(hào)i=0的虛擬機(jī)Jzj0,該虛擬機(jī)作為著艦序列的首架機(jī),且真實(shí)飛機(jī)k在虛擬機(jī)后的安全尾流間隔時(shí)間WLT0,k均相同,具體數(shù)值WLT0為

(9)

借助式(8)可以將艦載機(jī)機(jī)群回收調(diào)度問題的數(shù)學(xué)模型表示為

MinJ(xi,j)=

(10)

(11)

TOsafe+DTi

(12)

TOmin

(13)

xi,j=0,i∈N1;j∈N0

(14)

minDTi≥JTmin+TML,i∈N1

(15)

(16)

(17)

其中,式(11)表示著艦方案中前后兩架相鄰的艦載機(jī)之間要滿足尾流安全要求;式(12)表示在不進(jìn)行空中加油的艦載機(jī)集合N0中,所有的艦載機(jī)都必須滿足安全油量著艦的要求;式(13)表示在著艦方案中,只有當(dāng)艦載機(jī)無法實(shí)現(xiàn)安全油量著艦的情況下才會(huì)進(jìn)行空中加油,且在著艦方案開始時(shí)刻,在需要進(jìn)行空中加油的艦載機(jī)集合N1中,艦載機(jī)都必須有充足油量以滿足空中加油航線的需求;式(14)表示在著艦方案中需要進(jìn)行空中加油的艦載機(jī)在完成加油后需排在未加油的艦載機(jī)之后進(jìn)行著艦;式(15)表示進(jìn)行空中加油的艦載機(jī)著艦等待時(shí)間大于馬歇爾點(diǎn)至著艦點(diǎn)的飛行時(shí)間與完成空中加油的時(shí)間之和。其中,JTmin表示完成空中加油任務(wù)的最短耗時(shí);式(16)表示除了虛擬機(jī),每架飛機(jī)緊鄰的前序飛機(jī)有且只有一架;式(17)表示包括虛擬機(jī)在內(nèi),每架飛機(jī)緊鄰的后續(xù)飛機(jī)不多于一架(即最后著艦的飛機(jī)后續(xù)無緊鄰飛機(jī))。

2 基于MGP的艦載機(jī)機(jī)群回收排序方法

艦載機(jī)機(jī)群回收調(diào)度從本質(zhì)上而言屬于作業(yè)車間調(diào)度問題(job shop scheduling problem, JSSP),當(dāng)返航艦載機(jī)數(shù)量為n時(shí),共有n!種方案可供選擇,當(dāng)艦載機(jī)數(shù)量較多時(shí),很難采用枚舉法求得最佳的著艦方案。當(dāng)前,針對(duì)JSSP的求解方法主要有啟發(fā)式算法和元啟發(fā)算法,啟發(fā)式算法通過制定啟發(fā)式優(yōu)先規(guī)則可以快速生成調(diào)度方案,計(jì)算效率高,但是由于在規(guī)則制定過程中存在較大的主觀性,且算法過于貪婪,容易陷入局部最優(yōu)解,導(dǎo)致其最終的優(yōu)化效果無法保證。元啟發(fā)式算法將調(diào)度方案映射為某些特定的對(duì)象(如生物群中的個(gè)體或多維抽象空間中的微粒),并通過模擬自然界的某些過程或生物的群體行為對(duì)最優(yōu)個(gè)體進(jìn)行搜索,具備一定的跳出局部最優(yōu)解的能力,但是在尋優(yōu)過程中,存在大量的隨機(jī)搜索行為,當(dāng)問題規(guī)模增大時(shí),其搜索效率較低。

超啟發(fā)式算法的主要思想是通過某種高層管理策略對(duì)一系列底層的啟發(fā)式算法進(jìn)行處理和操縱。GP算法作為超啟發(fā)式算法的一種,實(shí)際上就是通過上層的遺傳算法操作規(guī)則對(duì)底層的調(diào)度優(yōu)先規(guī)則進(jìn)行重新整合,以生成最優(yōu)的組合優(yōu)先規(guī)則,用于產(chǎn)生調(diào)度方案的算法。與以遺傳算法(genetic algorithm, GA)為代表的元啟發(fā)式算法相比,其給出的結(jié)果是用于求解調(diào)度問題的調(diào)度規(guī)則,而不是針對(duì)特定問題的某一調(diào)度方案。GP算法解決了純啟發(fā)式算法不具備優(yōu)化功能的問題,當(dāng)問題規(guī)模較大時(shí),其在搜索空間和搜索效率方面均具備明顯優(yōu)勢(shì)。

2.1 調(diào)度優(yōu)先規(guī)則的選取

GP算法可以通過底層的啟發(fā)式規(guī)則不斷生成新的組合調(diào)度優(yōu)先級(jí)規(guī)則,并對(duì)組合規(guī)則進(jìn)行迭代優(yōu)化,且調(diào)度優(yōu)先規(guī)則通?？梢杂靡粋€(gè)調(diào)度優(yōu)先級(jí)函數(shù)來表示。因此,對(duì)調(diào)度規(guī)則的優(yōu)化等同于對(duì)優(yōu)先級(jí)函數(shù)的優(yōu)化。在應(yīng)用GP算法之前,首先需要確定底層的啟發(fā)式調(diào)度規(guī)則,針對(duì)艦載機(jī)機(jī)群的回收排序問題,本文選擇以下4種啟發(fā)式調(diào)度規(guī)則:

(1) 油少先著艦規(guī)則,相應(yīng)的優(yōu)先級(jí)函數(shù)為YX1=TO;

(2) 優(yōu)先級(jí)高先著艦規(guī)則,相應(yīng)的優(yōu)先級(jí)函數(shù)為YX2=YXJ;

(3) 完整度低先著艦規(guī)則,相應(yīng)的優(yōu)先級(jí)函數(shù)為YX3=WZD;

(4) 與前序艦載機(jī)尾流間隔要求短的機(jī)型先著艦規(guī)則,相應(yīng)的優(yōu)先級(jí)函數(shù)YX4=WLJ。

由于在后續(xù)的遺傳規(guī)劃操作中需要對(duì)上述啟發(fā)式規(guī)則所對(duì)應(yīng)的優(yōu)先級(jí)函數(shù)進(jìn)行相應(yīng)的加減乘除或極值運(yùn)算,為了避免優(yōu)先級(jí)函數(shù)量級(jí)不同對(duì)計(jì)算結(jié)果的影響,此處對(duì)優(yōu)先級(jí)函數(shù)的數(shù)值進(jìn)行了歸一化處理:

(18)

2.2 編碼設(shè)計(jì)與種群初始化

與GA類似,在利用GP算法進(jìn)行調(diào)度方案求解時(shí),也需要對(duì)種群中的個(gè)體進(jìn)行編碼。但有所不同的是,GP算法中的個(gè)體是一種由底層調(diào)度優(yōu)先規(guī)則所構(gòu)成的組合調(diào)度規(guī)則,其不同的個(gè)體可以用不同的GP樹來表示。如圖2所示,GP樹是一種由計(jì)算符節(jié)點(diǎn)和終端規(guī)則函數(shù)節(jié)點(diǎn)所組成的一種樹狀結(jié)構(gòu)。圖2中,虛線圓節(jié)點(diǎn)表示深度為0的順序判斷編碼[25],rise(升序)表示組合優(yōu)先級(jí)函數(shù)的值越大,優(yōu)先級(jí)越高;fall(降序)表示組合優(yōu)先級(jí)函數(shù)的值越小,優(yōu)先級(jí)越高。圓節(jié)點(diǎn)表示計(jì)算符節(jié)點(diǎn)(也可稱為根節(jié)點(diǎn)),這里選擇+,-,×,÷,max,min這6種計(jì)算符形式。矩形節(jié)點(diǎn)為終端規(guī)則函數(shù)節(jié)點(diǎn)(也可稱為葉節(jié)點(diǎn)),可從第2.1節(jié)中所設(shè)計(jì)的4種歸一化優(yōu)先級(jí)函數(shù)中進(jìn)行選擇。

圖2 GP樹調(diào)度規(guī)則編碼結(jié)構(gòu)Fig.2 GP tree scheduling rule coding structure

圖2中給出的兩個(gè)GP樹的深度均為4,即GP樹中第4層中的節(jié)點(diǎn)均為葉節(jié)點(diǎn)。在進(jìn)行GP樹種群初始化時(shí),為了保證種群的多樣性,通常不希望事先指定GP樹的具體層數(shù)和結(jié)構(gòu)。因此,這里只對(duì)GP樹的深度進(jìn)行限制?？紤]到機(jī)群回收排序問題中終端優(yōu)先級(jí)規(guī)則函數(shù)的可選數(shù)量,這里將GP樹的最大深度限制為L(zhǎng)max=4,同時(shí)為了保證最終的組合調(diào)度規(guī)則中至少含有兩個(gè)終端規(guī)則函數(shù),GP樹的最小深度Lmin=2。GP樹個(gè)體的生成過程可分為以下兩個(gè)步驟。

步驟 1確定2Lmax-1個(gè)節(jié)點(diǎn)的類型,首先,將第Lmax層的所有節(jié)點(diǎn)確定為葉節(jié)點(diǎn);進(jìn)一步,將剩余的節(jié)點(diǎn)隨機(jī)確定為根節(jié)點(diǎn)或葉節(jié)點(diǎn),得到“滿節(jié)點(diǎn)數(shù)”的GP樹個(gè)體;最后,對(duì)葉節(jié)點(diǎn)下層所連接的節(jié)點(diǎn)結(jié)構(gòu)予以刪除,確保葉節(jié)點(diǎn)上層所連接的節(jié)點(diǎn)全部為根節(jié)點(diǎn)。

重復(fù)步驟1和步驟2共Npop次,便可得到種群規(guī)模為Npop的初始GP樹種群。

2.3 調(diào)度方案生成與適應(yīng)度評(píng)價(jià)

在獲得初始的GP樹種群后,需要確定種群中各個(gè)個(gè)體的適應(yīng)度值,以便進(jìn)行后續(xù)的遺傳操作。與傳統(tǒng)的遺傳算法不同,GP樹個(gè)體只對(duì)應(yīng)于某種組合調(diào)度規(guī)則,而并非直接對(duì)應(yīng)于某種特定的調(diào)度方案,因而在對(duì)GP樹的適應(yīng)度進(jìn)行計(jì)算之前應(yīng)先確定GP樹規(guī)則所對(duì)應(yīng)的調(diào)度方案。如圖2所示,GP樹所對(duì)應(yīng)的組合調(diào)度規(guī)則可表示為

(19)

即需要根據(jù)式(19)所給出的組合調(diào)度規(guī)則生成相應(yīng)的著艦回收調(diào)度方案,在介紹調(diào)度方案生成算法之前,需要引入當(dāng)前安全油量著艦(current safe fuel landing, CSFL)和強(qiáng)制提前著艦(mandatory landing ahead, MLA)兩個(gè)判斷性條件。

(1) CSFL條件

CSFL條件是指在著艦方案設(shè)計(jì)過程中,當(dāng)前序著艦序列已確定,而在選擇某架艦載機(jī)作為下一架次著艦機(jī)時(shí),被選中的艦載機(jī)到達(dá)著艦點(diǎn)時(shí)的剩余油量應(yīng)大于安全著艦油量Osafe。轉(zhuǎn)化為剩余油量飛行時(shí)間,可將CSFL條件表示為

DTj+WLJj,i

(20)

式中:i表示被選中的當(dāng)前飛機(jī)編號(hào);Ωzj表示已安排著艦次序的艦載機(jī)集合;Ωust表示尚未確定著艦次序的艦載機(jī)集合。

(2) MLA條件

MLA條件是指在著艦方案設(shè)計(jì)過程中,若按照一定規(guī)則選取某架艦載機(jī)j作為當(dāng)前著艦機(jī),則未安排著艦次序的艦載機(jī)i必然無法實(shí)現(xiàn)安全油量著艦,為避免空中加油情況的出現(xiàn),在條件允許的情況下需要將i的著艦次序提前,即滿足:

DTj+WLJj,i>TOi-TOsafe,i,j∈Ωust

(21)

在滿足式(21)時(shí),需要考慮將i的著艦次序提前。

下面借助CSFL條件和MLA條件,給出基于組合調(diào)度規(guī)則生成著艦回收排序方案的算法步驟如下。

步驟 1首先選擇虛擬機(jī)Jzj0作為著艦方案中的首架機(jī),并設(shè)置其虛擬著艦等待時(shí)間DT0=TML-WLT0(因所有真實(shí)飛機(jī)與虛擬機(jī)之間的尾流安全間隔時(shí)間均為WLT0,所以著艦方案中在虛擬機(jī)之后的首架飛機(jī)的著艦等待時(shí)間為TML)。令待安置集合Ωust=Ωall,其中,Ωall表示全部待回收艦載機(jī)的集合;

步驟 2按照GP樹中的組合調(diào)度規(guī)則,計(jì)算集合Ωust中各架艦載機(jī)的組合優(yōu)先級(jí)函數(shù)值,然后將組合優(yōu)先級(jí)函數(shù)值按照[rise]或[fall]規(guī)則進(jìn)行排序;

步驟 3選擇排序最靠前的艦載機(jī)作為待選著艦機(jī)Jzjud。首先,計(jì)算將Jzjud安排在當(dāng)前架次是否滿足CSFL條件,若不滿足,則判定Jzjud需要進(jìn)行空中加油,并將其從集合Ωust轉(zhuǎn)移到待加油集合Ωjy中,按照排序結(jié)果選擇下一位次的艦載機(jī)作為新的Jzjud。重復(fù)此操作,直至新的Jzjud滿足CSFL條件;

步驟 4將Jzjud暫定為當(dāng)前架次的著艦機(jī),判斷Ωust中的各架飛機(jī)是否滿足MLA條件。若滿足,則將相應(yīng)的飛機(jī)放入到優(yōu)先著艦集合Ωyx中;判斷Ωyx是否為空集,若Ωyx為空集,則將Jzjud正式確定為當(dāng)前架次的著艦機(jī)Jzjc,轉(zhuǎn)至步驟6;若Ωyx不為空集,則轉(zhuǎn)至步驟5;

步驟 5將Ωyx中的艦載機(jī)按組合優(yōu)先級(jí)函數(shù)值進(jìn)行排序,按順序依次判斷其是否滿足CSFL條件,若不滿足則將其放入到集合Ωjy中,若滿足則將其直接確定為當(dāng)前架次著艦機(jī)Jzjc;若集合Ωyx中的艦載機(jī)均不滿足安全油量著艦條件,則將Jzjud正式確定為當(dāng)前架次的著艦機(jī)Jzjc;

步驟 6將當(dāng)前架次的著艦機(jī)放入到著艦集合Ωzj中,并根據(jù)前一架次的著艦等待時(shí)間以及尾流間隔時(shí)間要求確定當(dāng)前架次著艦機(jī)Jzjc的著艦等待時(shí)間DTc,更新Ωyx=?,更新待安置集合Ωust=Ωall-Ωjy-Ωzj;

上述著艦調(diào)度方案生成過程中,在步驟4～步驟5中引入了強(qiáng)制著艦規(guī)則,盡可能避免了艦載機(jī)出現(xiàn)空中加油的情況。為了更清楚地展現(xiàn)算法的邏輯結(jié)構(gòu),帶強(qiáng)制著艦規(guī)則的回收排序調(diào)度方案生成算法如算法1所示。

算法1 帶強(qiáng)制著艦規(guī)則的回收排序調(diào)度方案生成算法輸入 GP樹個(gè)體,Ωall中各架飛機(jī)的狀態(tài)信息輸出 艦載機(jī)機(jī)群回收著艦排序方案1 初始化:確定虛擬機(jī)Jzj0為首架著艦機(jī),DT0=TML-WLT0,Ωust=Ωall。確定Ωust中所有飛機(jī)的YXiu,i=1,2,3,42 While Ωust=? then 3 根據(jù)GP樹編碼計(jì)算Ωust中個(gè)飛機(jī)的組合優(yōu)先級(jí)函數(shù),并按[rise]或[fall]規(guī)則排序,選擇序列中的首架機(jī)為Jzjud 4 While Jzjud不滿足CSFL條件 then 5 將Jzjud從Ωust轉(zhuǎn)移到集合Ωjy 6 選擇序列中下一架飛機(jī)作為Jzjud 7 end 8 for Jzji in Ωust do 9 if Jzji滿足MLA條件 then 10 將Jzji放入集合Ωyx 11 end 12 計(jì)算Ωyx中各架艦載機(jī)的組合優(yōu)先級(jí)函數(shù),并按[rise]或[fall]規(guī)則排序,得到序列XLyx 13 for Jzji in XLyx do 14 if Jzji 滿足CSFL條件 then 15 確定Jzji為當(dāng)前架次著艦機(jī)Jzjc 16 else 17 將Jzji放入集合Ωjy 18 end 19 end 20 if Ωyx中沒有艦載機(jī)滿足CSFL條件 THEN 21 將Jzjud作為當(dāng)前架次的著艦機(jī)Jzjc 22 end 23 end 24 將當(dāng)前架次的著艦機(jī)Jzjc放入集合Ωzj,更新著艦序列XLzj=[XLzj;Jzjc] 25 更新Ωyx=?,Ωust=Ωall-Ωjy-Ωzj26 end27 將Ωjy中的艦載機(jī)的油量更新為maxj=1,2,…,nTOj28 計(jì)算Ωjy中各架艦載機(jī)的組合優(yōu)先級(jí)函數(shù),并按[rise]或[fall]規(guī)則排序,得到序列XLjy29 更新XLzj=[XLzj;XLjy]

2.4 種群的多樣性操作

與普通的GA類似,在GP算法中,為了保證種群的多樣性,對(duì)GP樹種群引入了遺傳、交叉和變異3種形式的遺傳操作,遺傳操作主要是為了選出合適的GP樹個(gè)體作為父代進(jìn)行遺傳操作。此處,為了選擇適應(yīng)度值相對(duì)較優(yōu)的個(gè)體作為父代進(jìn)行遺傳操作,采用二元錦標(biāo)賽模式對(duì)父代個(gè)體進(jìn)行選取,即“兩兩比較,擇優(yōu)選擇”。交叉操作即選擇兩個(gè)不同的父代個(gè)體,隨機(jī)選擇其中的某一節(jié)點(diǎn)連同其全部的子節(jié)點(diǎn)進(jìn)行交換,從而得到新的子代個(gè)體,如圖3所示。

圖3 GP樹交叉操作示意圖Fig.3 Schematic diagram of GP tree crossing operation

本文選取3種變異操作模式,如圖4所示。第1種為刪除子樹操作,選擇GP樹中的某一根節(jié)點(diǎn)及其全部子節(jié)點(diǎn)進(jìn)行刪除,并隨機(jī)生成一個(gè)葉節(jié)點(diǎn)用于代替原根節(jié)點(diǎn)的位置;第2種變異操作為節(jié)點(diǎn)突變,選擇GP樹中的任意節(jié)點(diǎn),對(duì)這一節(jié)點(diǎn)中的取值進(jìn)行修改,而節(jié)點(diǎn)類型不變;第3種操作為隨機(jī)子樹替代,任選一個(gè)節(jié)點(diǎn),用隨機(jī)生成子樹代替該節(jié)點(diǎn),從而得到新的子代個(gè)體。

圖4 GP樹變異操作示意圖Fig.4 GP tree mutation operation schematic diagram

3種不同的變異方式可以通過對(duì)其設(shè)置相應(yīng)的發(fā)生概率予以控制,進(jìn)一步在進(jìn)化的過程中引入精英個(gè)體保留策略,以保證適應(yīng)度最優(yōu)的GP樹個(gè)體可以保留到下一代種群中。圖5給出了本節(jié)所建立的基于MGP的艦載機(jī)機(jī)群回收排序算法的框架圖。

圖5 基于MGP的艦載機(jī)機(jī)群回收排序調(diào)度算法框架Fig.5 Framework for carrier aircraft fleet recovery sequencing scheduling algorithm based on MGP

3 機(jī)群回收仿真分析與對(duì)比

3.1 機(jī)群回收著艦仿真條件設(shè)置

在仿真過程中,設(shè)置MGP算法中的種群數(shù)量為100,最大迭代次數(shù)為80,個(gè)體變異概率為0.2,頂點(diǎn)變異概率為0.5,假設(shè)待回收機(jī)群共有30架飛機(jī),各架飛機(jī)的初始狀態(tài)信息如表2(部分信息參考文獻(xiàn)[8])所示。

表2 待回收機(jī)群的初始狀態(tài)信息Table 2 Initial status information of the carrier aircraft fleet to be recovered

在仿真過程中,假設(shè)S、M、L、N型飛機(jī)的油耗速率分別為0.6 L/s、0.9 L/s、1.2 L/s、0.6 L/s,在仿真過程中有關(guān)的時(shí)間常數(shù)項(xiàng)取值如表3所示,不同機(jī)型間的尾流安全間隔時(shí)間在表1中已經(jīng)給出。

表3 仿真中時(shí)間常數(shù)變量的取值Table 3 Value of time constant variable used in simulation

3.2 仿真結(jié)果分析與對(duì)比

利用本文所設(shè)計(jì)的MGP算法對(duì)表2中需要回收的機(jī)群進(jìn)行著艦排序,所得到的排序結(jié)果如表4所示。從表4可以看出,其著艦安全時(shí)間裕度均大于0 s,即在此著艦方案中需要進(jìn)行空中加油的艦載機(jī)數(shù)量為0架。最終所得到的評(píng)價(jià)指標(biāo)函數(shù)值為19 570 s,著艦回收任務(wù)的完成時(shí)間為3 299 s,算法的計(jì)算求解時(shí)間為16.4 s。

表4 著艦排序方案結(jié)果Table 4 Landing sequencing scheme results

續(xù)表4Continued Table 4

為了展示著艦方案中不同時(shí)刻各艦載機(jī)的飛行位置,圖6給出了表4中艦載機(jī)著艦調(diào)度方案所對(duì)應(yīng)的時(shí)序甘特圖。其中,不同顏色的圖例所對(duì)應(yīng)的字母與圖1中的字母含義相同,用以表示艦載機(jī)在返航航線中所處的位置。

圖6 調(diào)度方案中各艦載機(jī)的飛行狀態(tài)甘特圖Fig.6 Gantt chart of flight status of each carrier aircraft in the scheduling scheme

作為比較,利用普通的GP算法、GA對(duì)上述著艦回收案例進(jìn)行優(yōu)化調(diào)度,所得的迭代收斂曲線如圖7所示。

圖7 不同算法的迭代收斂曲線Fig.7 Iterative convergence curves of different algorithms

從圖7可以分析出,無論是算法的收斂速度還是算法的優(yōu)化效果,本文所設(shè)計(jì)的MGP算法都是3種方法中最優(yōu)的。這主要得益于MGP算法引入了強(qiáng)制優(yōu)先著艦規(guī)則,使得油量不足的艦載機(jī)可以不受組合優(yōu)先級(jí)規(guī)則的限制而實(shí)現(xiàn)提前著艦。引入強(qiáng)制優(yōu)先著艦規(guī)則后,在相同的情況下,可以降低著艦方案中艦載機(jī)出現(xiàn)空中加油的可能性,避免了部分組合規(guī)則因出現(xiàn)空中加油而獲得較大的評(píng)價(jià)指標(biāo)函數(shù),從而被過早淘汰的情況,變相地增加了種群的多樣性,因此其優(yōu)化效果相對(duì)于普通的GP算法有較為明顯的改善。另一方面,在此案例中,機(jī)群的回收數(shù)量較多(30架),在利用GA進(jìn)行方案優(yōu)化時(shí),其搜索空間的規(guī)模為30!,因而搜索效率較低,且極易陷入局部最優(yōu),從而影響了最終的優(yōu)化效果。

圖8中給出了利用GP算法、GA進(jìn)行調(diào)度優(yōu)化時(shí)所得到的著艦方案甘特圖,兩種算法的計(jì)算求解時(shí)間分別為12.6 s和23.2 s。可見在算法的求解速度方面,GP算法的求解耗時(shí)最短,MGP算法的求解時(shí)間較GP算法長(zhǎng)3.8 s,但這一時(shí)間差距相較于著艦回收任務(wù)的總時(shí)長(zhǎng)(55 min)而言,可忽略不計(jì);GA的求解時(shí)間最長(zhǎng),其計(jì)算耗時(shí)約為GP算法的兩倍。

圖8 不同調(diào)度方案中艦載機(jī)的飛行狀態(tài)甘特圖Fig.8 Gantt chart of aircraft flight status in the different scheduling schemes

為了進(jìn)一步驗(yàn)證本文所設(shè)計(jì)的MGA算法的有效性,此處選取GP算法、GA以及油少先著艦(less fuel first served, LFFS)啟發(fā)式算法和優(yōu)先級(jí)高先著艦(higher priority first served, HPFS)啟發(fā)式算法作為對(duì)比。構(gòu)建機(jī)群規(guī)模分別為15架、25架、35架、45架的回收案例,在每種機(jī)群規(guī)模下各進(jìn)行30次仿真實(shí)驗(yàn),將不同機(jī)群規(guī)模條件下的實(shí)驗(yàn)結(jié)果取平均值,獲得的調(diào)度方案指標(biāo)統(tǒng)計(jì)結(jié)果如表5所示,加粗字體的數(shù)值表示各組仿真結(jié)果中的最優(yōu)值。

表5 不同機(jī)群規(guī)模條件下的算法優(yōu)化結(jié)果統(tǒng)計(jì)結(jié)果Table 5 Algoribhm optimization statistic results under different aircraft fleet sizes

從表5可以看出,在4種機(jī)群規(guī)模條件下,本文所設(shè)計(jì)的MGP算法的調(diào)度結(jié)果均為最優(yōu)。利用MGP算法和GP算法求解所得的著艦回收方案,其任務(wù)完成時(shí)間較另外3種算法而言更短。當(dāng)機(jī)群數(shù)量較少時(shí),GA的結(jié)果要優(yōu)于純啟發(fā)式算法,但是隨著機(jī)群規(guī)模的增加,GA的相對(duì)優(yōu)化效果逐漸變差,且當(dāng)艦載機(jī)機(jī)群規(guī)模增加到45架時(shí),利用GA所獲得的著艦方案中出現(xiàn)了空中加油的情況,且從適應(yīng)度函數(shù)值來看,此時(shí)GA的優(yōu)化效果差于LFFS算法。這是由于當(dāng)機(jī)群規(guī)模增加時(shí),GA算法的解空間將按照階乘的方式急劇增大,其尋優(yōu)性能相應(yīng)變差。在全部的5種算法中,HPFS算法所得的著艦方案效果最差,且方案中出現(xiàn)空中加油的架次最多。HPFS算法和LFFS算法均屬于啟發(fā)式算法,其調(diào)度方案的合理性完全依賴于主觀確定的啟發(fā)式規(guī)則,且不具備迭代優(yōu)化能力。但相對(duì)而言,LFFS算法可以保證著艦方案中的空中加油架次盡可能地少,從而使適應(yīng)度函數(shù)中的懲罰項(xiàng)獲得較小的值。除了LFFS算法,采用MGP算法和GP算法在4種不同機(jī)群規(guī)模的情況下所獲得的著艦方案均不需要進(jìn)行空中加油。

表5還給出了各種算法單次迭代的計(jì)算耗時(shí),即算法的求解總耗時(shí)除以算法的迭代次數(shù)所得到的結(jié)果。從表5可以看出,HPFS算法和LFFS算法作為純啟發(fā)式算法,求解速度最快,單次迭代的計(jì)算耗時(shí)較另外3種算法小2個(gè)數(shù)量級(jí),且由于HPFS算法和LFFS算法不需要迭代優(yōu)化,因而其單次迭代的計(jì)算耗時(shí)即為算法求解的總耗時(shí)。在所有的算法當(dāng)中,GA的單次迭代求解耗時(shí)最長(zhǎng),MGP算法的單次迭代求解耗時(shí)略長(zhǎng)于GP算法,但MGP算法與GP算法的單次迭代求解耗時(shí)相差不超過15%。

3.3 逃逸復(fù)飛對(duì)著艦方案的影響分析

本文所設(shè)計(jì)的MGP著艦排序方法可以給出經(jīng)過優(yōu)化后的著艦方案,但在實(shí)際情況中,艦載機(jī)著艦存在一定的失敗概率。艦載機(jī)著艦失敗后需要重新進(jìn)行著艦,因此必須有相應(yīng)的著艦失敗應(yīng)對(duì)策略。本文采用著艦失敗的艦載機(jī)優(yōu)先著艦的策略,即當(dāng)出現(xiàn)逃逸或復(fù)飛的情況時(shí),著艦失敗的艦載機(jī)立即轉(zhuǎn)入復(fù)飛航線,并在當(dāng)前時(shí)刻已經(jīng)經(jīng)過馬歇爾點(diǎn)的飛機(jī)全部完成著艦后再進(jìn)行著艦,而未經(jīng)過馬歇爾點(diǎn)的艦載機(jī)利用其下層等待航線進(jìn)行盤旋等待,待與二次著艦機(jī)的尾流間隔滿足要求后再進(jìn)行著艦。本文將最短復(fù)飛航線的飛行時(shí)間取為417 s。

在表4中的原有著艦方案的基礎(chǔ)上,需考慮艦載機(jī)出現(xiàn)逃逸復(fù)飛時(shí)對(duì)著艦任務(wù)完成時(shí)間以及評(píng)價(jià)指標(biāo)函數(shù)所產(chǎn)生的影響。此處在原方案中隨機(jī)選擇不同的艦載機(jī),假設(shè)其出現(xiàn)了逃逸或復(fù)飛的情況,此時(shí)經(jīng)過應(yīng)急調(diào)整后的著艦方案所對(duì)應(yīng)的任務(wù)完成時(shí)間以及評(píng)價(jià)指標(biāo)函數(shù)如表6所示。由表6可見,與原著艦方案相比,當(dāng)出現(xiàn)一架次艦載機(jī)著艦失敗時(shí),著艦任務(wù)的完成時(shí)間平均增加了139.3 s,指標(biāo)評(píng)價(jià)函數(shù)平均增加了595.6 s,而當(dāng)出現(xiàn)兩架次艦載機(jī)著艦失敗時(shí),著艦任務(wù)的完成時(shí)間平均增加了273.0 s,指標(biāo)評(píng)價(jià)函數(shù)平均增加了1 071.4 s。由此可見,提高艦載機(jī)的著艦成功率對(duì)于縮短回收任務(wù)完成時(shí)間以及增強(qiáng)回收任務(wù)效能而言有著重要意義。

表6 復(fù)飛逃逸對(duì)著艦排序方案的影響Table 6 Influence of wave off and escape on the landing sequencing scheme

4 結(jié) 論

本文首先對(duì)航母甲板環(huán)境以及艦載機(jī)的返航回收進(jìn)場(chǎng)模式進(jìn)行了分析,建立了基于加權(quán)等待時(shí)間的回收排序評(píng)價(jià)指標(biāo)模型,并根據(jù)艦載機(jī)回收著艦問題中的各項(xiàng)約束,建立了考慮空中加油條件下的艦載機(jī)著艦回收排序調(diào)度問題模型。進(jìn)一步,借助于超啟發(fā)式算法思想,設(shè)計(jì)了一種基于MGP算法的艦載機(jī)機(jī)群回收排序調(diào)度方法,最后通過回收仿真算例驗(yàn)證了本文中模型和算法的有效性。本文的研究?jī)?nèi)容以及方法的優(yōu)勢(shì)主要體現(xiàn)在:

(1) 在著艦回收調(diào)度模型中充分考慮了空中加油對(duì)著艦方案的影響,并給出了加油返航機(jī)的著艦回收方案,這使得調(diào)度模型對(duì)于返航艦載機(jī)的油量限制大大減小,提高了文中所建模型的適用范圍。

(2) 通過GP算法進(jìn)行組合調(diào)度規(guī)則優(yōu)化,該方法與傳統(tǒng)的遺傳算法相比,最大的優(yōu)勢(shì)是其在機(jī)群規(guī)模增大的情況下可以保證解空間的搜索范圍不變,因而具有較高的算法搜索效率。

(3) 在傳統(tǒng)的GP算法中引入了強(qiáng)制優(yōu)先著艦規(guī)則,盡可能地避免了著艦方案中出現(xiàn)空中加油的情況,同時(shí)也避免了部分組合規(guī)則因出現(xiàn)空中加油而獲得較大的評(píng)價(jià)指標(biāo)函數(shù),從而被過早淘汰的情況,變相地增加了種群的多樣性,這也使得MGP算法相較于GP算法而言具有更好的優(yōu)化效果。