基于出動效率最大的離場優化排序

唐鑫磊， 沈 堤， 張 哲， 余付平

(空軍工程大學空管領航學院，西安，710051)

在當前軍航機場管制條件下，管制員一般依據飛機執行任務的下達時間并結合個人經驗，給離場飛機安排離場時間和起飛次序，這在飛機較少的日常飛行訓練中，有較好的適用性，但隨著體系化作戰強度的增加或者緊急進入戰備狀態，大批次飛機需要快速從機場起飛到達預定空域執行任務時，繼續應用依靠管制員經驗安排起飛次序這種方法難以解決機場跑道擁擠的問題。鑒于此，如何實現飛機快速高效離場，盡快到達預定空域并形成體系作戰能力，已成為亟需解決的問題。

國內外學者為解決飛機離場優化排序問題應用了許多算法。尹嘉男等建立了基于獨立運行模式的多跑道飛機離場調度模型，并用NSGA-Ⅱ算法求解，均衡了各跑道之間的運行負荷[1]。Ming等將兩階段無等待混合流水車間模型應用于多機場飛機調度問題，并設計了一種CPLEX算法應用于多機場系統的最優起飛序列計算，使總加權延誤成本最小[2]。 Zhong等針對多機場中的低優先級機場的飛機離場優化排序問題，建立了基于機場總延誤時間、單架飛機最大延誤時間的雙目標整數規劃模型，并設計了禁忌搜索算法進行求解，實驗結果證明，可以有效提高低優先級機場的運行效率[3]。Ma等考慮了滑行道的等待隊列容量，并以到達跑道端口等待時間為決策變量，建立了基于時隙分配的多跑道飛機起飛排序模型，利用模擬退火算法求解[4]。 Sandamali等針對離場優化排序問題，建立了基于飛機離場速度和離場時間的不確定性的優化模型，通過使用最佳飛行高度層分配策略來最小化燃料消耗，通過貪心算法求解該問題，有效降低了離場速度和離場時間偏差導致的延誤等問題[5]。馬琳娜等利用了Anylogic建立了基于貨運飛機離場時間最短的智能體仿真模型，對貨運飛機的跑道分配問題進行了優化，降低了飛機在跑道端的等待時間[6]。Wei等針對綜合飛機離場調度和飛行航線分配問題，分析了飛機離場調度、航線的時間窗約束、運輸負載率之間的相互作用，采用基于蟻群算法的兩階段啟發式方法，有效降低了航空公司的運營成本，并最大限度提高了運輸效率[7]。江灝等建立了基于交通狀態的飛機離場優化排序模型，在機場擁擠和非擁擠兩個場景下進行實驗仿真，對比先到先服務方法，NSGA-Ⅱ算法得到的離場飛機總次序調整次數降低80%，且總延誤時間減少一半[8]。

分析前人研究可知，已有飛機離場優化排序研究存在一些不足，主要有：①現有研究大多數只考慮了跑道端的約束讓飛機快速離場，而軍航飛機不僅有快速離場的需求，還有快速到達各自預定空域陣位，建立起“任務包”，形成體系作戰能力，執行軍事行動的需求，這就要求在建立問題模型時，將飛機從機場飛往預定空域的時間對飛機起飛次序的影響納入考慮范圍；②雖有諸如模擬退火算法等傳統經典算法以及遺傳算法、蟻群算法等群智能算法應用于飛機離場優化排序問題，但仍有許多優秀的新算法尚未應用于該領域，如海洋捕食者算法、多元宇宙算法、天牛須搜索算法等。本文在現有研究的基礎上，以飛機在預定空域形成“任務包”時間最短為優化目標，建立飛機離場優化排序模型，并針對海洋捕食者算法的尋優速度較慢、尋優精度不高等問題，引入精英反向學習策略提升初始解的質量，以提高其尋優速度，融入黏菌的覓食行為提高其尋優精度，最后利用案例仿真與其他算法優化結果進行對比，驗證所提算法的性能。

1 問題定義

空中力量前出執行作戰任務，通常以“任務包”形式組織實施。以空中突擊作戰為例，一個典型的任務包通常由掃蕩編隊、壓制編隊、對地突擊編隊構成。“任務包”中的戰機首先從機場起飛，前往預定空域集結編組隊形，形成完整的突擊“任務包”，然后從前推線向前推進。預定空域集結隊形通常如圖1所示，掃蕩編隊、壓制編隊、對地突擊編隊三者隊形之間保持一定距離(圖1)。

圖1 預定空域集結隊形

離場優化排序作為本文研究內容，是飛機執行作戰任務的關鍵一環，其出動效率高低將直接影響后續前往預定陣位形成突擊任務包的速度。這里，出動效率主要由飛機到達預定空域陣位的時間來體現，因此求解離場優化排序問題是核心。解決離場優化排序問題的關鍵是，如何在跑道離場端安排多個離場隊列中的不同飛機進入不同的跑道，以使離場飛機前往預定空域形成完整“任務包”的時間最短。顯然，這個問題能通過建立一個數學模型并應用一個優化算法來解決，這正是本文的研究重點。而多隊列飛機離場優化排序問題是單隊列離場的一種拓展情況，其流程如下圖2所示。其中，藍色虛線方框部分為本文的重點研究部分。

圖2 多隊列飛機離場過程

2 模型構建

與民航單跑道離場優化問題不同的是，軍航多跑道離場優化問題的難點在于，它不但需要確定作戰飛機在起飛跑道上的最終起飛次序，還需要將這些作戰飛機合理分配到預定的空域陣位上，以便使得執行作戰任務的飛機到達預定空域形成完整“任務包”的總時間最短。本文假定每條滑行道可以進入任意一條跑道上，因此形成完整“任務包”總時間等于最后一架飛機到達預定空域陣位的時間，而飛機到達預定陣位的時間等于飛機的起飛時間加上跑道占用時間和從機場起飛到預定陣位的時間。

基于上述分析，建立多隊列飛機離場優化排序問題的模型。

2.1 目標函數

成批次的作戰飛機從跑道起飛到達預定空域陣位形成完整“任務包”執行作戰任務這個過程，主要受飛機的起飛時間、跑道占用時間、從機場起飛后前往預定空域陣位的到達時間影響，表達式如式(1)所示：

min(maxDi)=min{max(Qi+Pi+Fi)}，i=1,2,…,N

(1)

式(1)表示模型的最小化目標函數，目的是將飛機到達預定空域陣位的最大時間極小化，從而使得“任務包”的形成時間最短。Di為飛機i到達預定空域陣位的時間，Qi為飛機i的起飛時間，Pi為飛機i的跑道占用時間，Fi為飛機i從機場起飛到達預定空域陣位時間，N為飛機數量。

2.2 安全間隔約束

作戰飛機作為高價值資產，保障其運行安全尤為重要，為避免發生前后飛機發生碰撞等事故，規定同一跑道上每次只允許一架飛機單獨使用，與此同時，在一條跑道上連續起飛的飛機須滿足一定的安全間隔。本文的安全間隔分為前機的發動機噴流等產生推力引起的縱向間隔和前機獲得升力形成尾渦引起的尾流間隔[9]。同一跑道上的前后飛機起飛時間間隔應大于前后飛機的縱向間隔、尾流間隔(距離間隔均轉換為時間間隔)以及前機的跑道占用時間三者中的最大值，以此確保作戰飛機的起飛安全，如式(2)、(3)所示：

Qi,j-Qi-1,j≥δ(i,i-1),j，i=1,2,…,Nj,j=1,2,…,M

(2)

δ(i,i-1),j=max(φ(i,i-1),j,φ(i,i-1),j,Pi-1,j)，i=1,2,…,Nj,j=1,2,…,M

(3)

式中：Qi,j為飛機在跑道上的起飛時間；δ(i,i-1),j為在跑道上前后飛機的最大安全間隔；Nj為跑道j的飛機數量；與N定義不同；M為跑道的數量；j為跑道的編號；φ(i,i-1),j,φ(i,i-1),j分別為跑道j上前后飛機的縱向間隔和尾流間隔；Pi-1,j為跑道j上前機的跑道占用時間。

2.3 滑行道約束

依據先到先服務原則，作戰飛機進入滑行道形成隊列后，假設該飛機隊列后續從某一跑道起飛，那么起飛的前后順序應保持相對不變。從該跑道起飛的飛機應滿足如下約束：

(4)

2.4 空域資源約束

在一個完整的“任務包”體系內，各種類型飛機各司其職，例如：電子戰飛機執行壓制干擾任務，殲擊機執行掃蕩任務等，故作戰飛機與空域陣位必須相吻合，這就要求執行某種任務的一架飛機有且只能占用一個與之相對應的空域陣位，同樣的，某種類型的每個空域陣位必須且只能分配給執行與之相對應任務的作戰飛機使用，即：

(5)

(6)

式中：Ng為g類型作戰飛機數量；Fg為發揮g類型作戰飛機作用相對應的空域陣位數量；γi,τ為0～1離散變量，若飛機i占用的空域陣位為τ，則γi,τ=1，否則為0；G為作戰飛機的種類數。

2.5 變量約束

為用N表示所有的作戰飛機數量以及與之相同的空域陣位數量，有下式成立：

(7)

飛機的起飛時間、跑道占用時間、從機場起飛到達預定空域陣位時間、以及2種安全間隔等均為非負數，有下式成立：

Qi,Pi,Fi,φ(i,i-1),j,φ(i,i-1),j,δ(i,i-1),j≥0

(8)

3 基于精英反向學習策略和黏菌覓食行為的改進海洋捕食者算法

2020年，Faramarzi等[10]通過解析海洋捕食者的捕食行為，提出了海洋捕食者算法(marine predators algorithm, MPA)。ESMPA繼承了MPA的所有捕食過程，并對其進行了改進。主要改進如下。

1) MPA算法的初始種群個體基于隨機規則產生的，這將導致初始解具有隨機性和不確定性，而算法的計算時間與初始解的優劣直接相關，初始解與最優解的距離越短，MPA算法計算時間則越短，反之則越長，故隨機產生的初始解可能導致MPA算法性能不佳。根據Tizhoosh教授研究[11]發現，初始解的反向解比初始解更接近最優解的概率多50%，并通過實驗證明，與隨機產生的初始種群的原算法相比，加入反向學習策略的改進算法具有更快的收斂速度；而ESMPA引入了精英反向學習策略[12]，則是考慮到精英個體比其他個體具備更多接近最優解的可能性，通過對種群中的精英個體構建出反向精英種群，增加種群的多樣性同時減少了構建普通個體的反向種群的運算時間，進一步提升ESMPA算法的收斂速度。

2)在MPA算法尋優的第3階段中，捕食者通過萊維飛行方式進行捕食，而應用萊維飛行方式會在隨機行走過程中出現較大概率的大跨步，使得MPA算法存在錯過最優解的可能。黏菌算法(slime mould algorithm，SMA)的覓食行為則有較好的局部尋優能力[13]，任麗莉等將黏菌算法的覓食行為引入多元宇宙算法中[14]，與原多元宇宙算法在測試函數上的測試結果相比，具有更好的求解能力。本文將黏菌算法的覓食行為融入算法的MPA算法第三階段，與應用萊維飛行方式的捕食行為相結合，以提升ESMPA算法的尋優能力。

ESMPA算法詳細過程如下所示，算法流程見圖3。

圖3 改進的海洋捕食者算法流程圖

3.1 ESMPA的種群初始化

ESMPA先通過隨機規則初始化“任務包”的離場起飛序列，其表達式如式(9)所示：

Xi,j=Xmin,j+r1(Xmax,j-Xmin,j)，i=1,2,…,n,j=1,2,…,D

(9)

式中：Xi,j為第i種起飛序列中在第j架飛機的進入預定空域陣位時間；n為種群數量(即為生成的起飛方案數量)；D為搜索維度(即為飛機數量)；r1∈(0,1)內的隨機數；Xmax,j、Xmin,j分別為飛機到達空域陣位時間的上下限。

(10)

(11)

通過精英式反向學習后，計算個體的適應度函數，本文所求為最小值問題，故認為適應度函數值低的個體更優，將原種群與反向種群的適應度值進行對比，將適應度值好的個體選為初始種群個體，采用式(12)進行更新：

(12)

精英矩陣E和獵物矩陣P定義如下：

(13)

(14)

式中：n為種群數量；D為搜索維度。初始種群的所有個體的位置信息構成了獵物矩陣，將初始種群中的最優解命名為頂級捕食者，將其位置向量作為E矩陣的第1行，將其復制n次，構成了初始精英矩陣。在尋優過程中，捕食者和獵物均為搜索者，因為每個個體都有捕食者與被捕食者兩種屬性。在每輪迭代中，如果捕食者被適應度值更優的捕食者取代，精英矩陣E的信息則需要進行更新。

3.2 ESMPA的尋優過程

ESMPA的尋優過程主要模擬了海洋捕食者追逐獵物的過程，依據兩者之間的速度比變化，將整個尋優過程劃分為3個階段。

1)高速比階段(迭代前期)：該階段發生在t

Si=RB×(Ei-RB×Pi)，i=1,2,…,n

(15)

Pi=Pi+p·R×Si

(16)

式中：Si為移動步長；RB為布朗運動[15]向量；R為[0,1]的隨機均勻分布的向量；p為一個常數，一般取0.5。

2)均速比階段(迭代中期)：該階段發生在T/3≤t<2T/3時，假設在此階段獵物的移動速度比捕食者相當，此時算法的尋優過程由全局搜索向局部搜索轉化，種群的前一半個體采用萊維飛行方式進行局部搜索，而后一半個體則繼續采用布朗運動進行全局搜索，主要表現為獵物負責局部搜索，捕食者負責全局搜索，前一半種群個體的位置變化如式(17)、(18)所示：

Si=RL×(Ei-RL×Pi)，i=1,2,…,n/2

(17)

Pi=Pi+p·R×Si

(18)

后一半個體的位置變化如式(19)、(20)、(21)所示：

Si=RB×(RB×Ei-Pi),i=n/2,…,n

(19)

Pi=Ei+p·C·Si

(20)

C=(1-t/T)(2t/T)

(21)

式中：RL為萊維飛行[16]向量；C為自適應參數，用以控制捕食者的移動步長；其他參數同上。

(22)

rfi=min(hi)+rand(max(hi)-min(hi))

(23)

(24)

(25)

式中：Pb為當前最優個體位置，PA、PB為兩個隨機個體的位置；υb、υc均為控制參數，υb∈[-a,a]的一個隨機值，υc從1線性遞減到0；a、υc的數學表達式分別如式(26)、(27)所示；r2∈(0,1)內的隨機數；g為一個控制變量，其表達式如式(28)所示；W為種群個體的適應度值權重，表達式如(29)所示：

(26)

(27)

g=tanh|f(Xi)-F|

(28)

(29)

k(i)=sort(f(Xi))

(30)

式中：f(Xi)為當前個體的適應度值；F表示已迭代輪次中的個體最優適應度值；r3∈(0,1)的隨機數；fb、fw分別表示本輪迭代的個體最優適應度值和最劣適應度值，i=m表示該個體的適應度值處于種群的前一半，i=n則表示其適應度值位于種群的后一半；k(i)為適應度值排序，本文所求為最小值問題，則使用升序排序法對種群個體進行排序。

3.3 ESMPA的位置更新

此外，ESMPA此外還考慮了2種效應對算法的影響，具體如下所示：

1)渦流(eddy formation,EF)和魚群聚集(fish aggregation devices,FAD)效應。Filmalter等研究發現渦流的形成以及魚群聚集效應會導致算法陷入局部最優[17]，因此ESMPA采用式(31)所示的跳躍方式來避免局部最優。

(31)

式中：r4∈(0,1)的隨機數；VFAD為渦流效應或魚群聚集效應對算法尋優的影響概率，一般取0.2；Pr1、Pr2為2個隨機獵物的位置；U為只包含0和1的二進制數組向量。

2)海洋記憶效應[18]。海洋捕食者存在對其曾經捕食成功的位置有一定記憶，這在MPA中可以表示對最優解的儲存，即將上一代的最優解與新解進行比較，如果新解適應度更好，則用當前的新解替代原最優解，這個過程會在迭代過程持續進行，以提高最優解的質量。

4 仿真驗證

4.1 仿真準備

本文以某實施獨立離場運行模式的軍用遠距雙跑道機場為例，對某次執行空中突擊任務的飛機編隊進行離場優化排序，其在3條滑行道上排隊等待進入跑道端的數據如表1所示，其中，A、B、C分別為3條滑行道的編號，H為實施對地打擊的轟炸機，M為實施電子壓制的電子戰飛機，S為實施空中掃蕩的殲擊機。

表1 滑行道飛機序列初始數據

轟炸機、電子戰飛機、殲擊機依據其最大起飛質量分別屬于重型(H)、中型(M)、輕型(S)作戰飛機。不同類型飛機對跑道的占用時間不同，本文采用的時間如表2所示。

表2 跑道占用時間

由于飛機的發動機噴流等產生推力引起的尾跡壽命較短，對后機的影響小，而飛機獲得升力形成尾渦形成的時間長，對后機的影響大，故本文計算時只考慮尾流間隔，飛機離場的尾流間隔標準[19]如表3所示(表中軍航間隔標準參考民航標準進行計算)。

表3 尾流間隔標準 單位：s

飛機從機場起飛后，前往不同的空域陣位點消耗的時間也不同，例如，一架殲擊機離開機場后可以選擇前往F1、F2、F3、F4空域陣位點進行盤旋等待，待到形成完整突擊“任務包”之后整體前推執行空中突擊任務，空域陣位到達時間如表4所示，空域陣位點如圖4所示。

表4 空域陣位點到達時間 單位：min

圖4 預定空域陣位點

4.2 結果分析

為了驗證ESMPA算法應用在進場優化排序領域的性能，選擇“任務包”形成最小時間min(maxDi)為驗證指標，與蟻群算法(ant colony optimization,ACO)[20]、遺傳算法(genetic algorithm,GA)[21]、粒子群算法(particle swarm optimization,PSO)[22]、海洋捕食者算法進行對比驗證，算法的參數設置如表5所示，所有算法的最大迭代次數設為200次，種群數量設為100，運行環境為MATLAB R2019a。

表5 算法參數取值

各算法獲得的仿真結果如表6～10所示，其中，符號(M)C1,X1,E4表示位于滑行道C的等待隊列中的第1架飛機為電子戰飛機，安排其以第1順位從跑道X起飛，前往壓制編隊所在的空域陣位點E4(由于空域陣位點呈軸對稱分布，默認先到達的飛機飛往左翼陣位點)，其余符號以此類推；tX、tY分別表示進入跑道X、Y的時間，tO表示到達空域陣位點的時間。尋優結果對比總時間如表11所示，基于ACO、GA、PSO、MPA、ESMPA算法求得的“任務包”形成最小時間分別為1 700 s、1 700 s、1 720 s、1 690 s、1 670 s, ESMPA算法較其他4種算法減少了30 s、30 s、50 s、20 s，對于分秒必爭的軍事打擊行動來說， ESMPA算法有效提高了“任務包”的出動效率。

表6 ACO的仿真結果 單位：s

表7 GA的仿真結果 單位：s

表8 PSO的仿真結果 單位：s

表9 MPA的仿真結果 單位：s

表10 ESMPA的仿真結果 單位：s

表11 尋優結果對比 單位：s

算法對比見圖5。

圖5 算法迭代曲線對比圖

對圖5的算法迭代曲線對比圖進行分析可知，GA、ACO算法尋優速度較快，分別在第13代、第6代獲得其最優值，但陷入了局部最優值，過早收斂；PSO、MPA則搜索速度與精度均較差，分別在第174代、第132代獲得其最優值；ESMPA算法搜索速度適中，在第89代獲得了最優值，尋優能力最強，這也證明了本文所提出的改進措施有效且實用。

5 結語

本文通過引入精英反向學習策略和融入黏菌算法的覓食行為對MPA算法進行改進，并將其應用到解決“任務包”的離場優化排序問題，得出了“任務包”的最短形成時間與最優起飛序列。與ACO、GA、PSO、MPA 算法求得的優化結果相比，應用ESMPA算法能更好地處理成批次飛機離場優化排序問題，有效提升作戰飛機的出動效率，為提升軍航機場的保障能力提供理論基礎。下一步研究將以其他軍事行動為背景，進一步提高ESMPA算法的實用性。