基于多目標(biāo)帝國(guó)競(jìng)爭(zhēng)算法的進(jìn)場(chǎng)排序與調(diào)度

張軍峰，游錄寶，楊春葦，胡榮

南京航空航天大學(xué) 民航學(xué)院，南京 210016

空中交通需求的持續(xù)增長(zhǎng)與可用空域資源的長(zhǎng)期受限，給空中交通管理(Air Traffic Management，ATM)帶來了新的機(jī)遇與挑戰(zhàn)。以中國(guó)繁忙機(jī)場(chǎng)的終端區(qū)運(yùn)行為例，完全依賴于管制員指令引導(dǎo)的方式，容易導(dǎo)致管制工作負(fù)荷激增、機(jī)場(chǎng)運(yùn)行效率降低、環(huán)境影響問題突出。因此，如何有效地優(yōu)化和調(diào)度時(shí)空資源，成為空中交通管理領(lǐng)域的研究熱點(diǎn)，而進(jìn)場(chǎng)排序與調(diào)度是該領(lǐng)域的典型問題。

進(jìn)場(chǎng)排序與調(diào)度旨在不違反安全間隔的條件下，結(jié)合運(yùn)行約束，合理高效地為進(jìn)場(chǎng)航空器分配著陸跑道，提供最優(yōu)著陸次序與時(shí)間，以期達(dá)到提升跑道容量、減少延誤、緩解管制工作負(fù)荷的目的[1]。歷經(jīng)近30年，進(jìn)場(chǎng)排序與調(diào)度的研究涵蓋了靜態(tài)優(yōu)化[2]與動(dòng)態(tài)優(yōu)化[3]，確定型優(yōu)化[4]與隨機(jī)型優(yōu)化[5]、單階段優(yōu)化[6](直接優(yōu)化著陸時(shí)間)與兩階段優(yōu)化[7-8](先確定著陸次序再優(yōu)化著陸時(shí)間)、是否提供相應(yīng)管制建議[9](即優(yōu)化時(shí)間的可達(dá)性)等方面，其求解工具或算法包括：CPLEX[1,7]、分支定界[5]、動(dòng)態(tài)規(guī)劃[6]、模擬退火[10]、遺傳算法[11]、粒子群算法[12]等。

對(duì)于進(jìn)場(chǎng)排序與調(diào)度問題，各利益相關(guān)方秉持不同的訴求：空管立足運(yùn)行安全，航司著眼效率優(yōu)先，機(jī)場(chǎng)注重容量增強(qiáng)，民眾關(guān)切準(zhǔn)點(diǎn)運(yùn)行與環(huán)境影響。因此，近年來進(jìn)場(chǎng)排序與調(diào)度的研究重點(diǎn)由單目標(biāo)優(yōu)化逐步轉(zhuǎn)向多目標(biāo)優(yōu)化。Sam等[13]研究了具有不同目標(biāo)函數(shù)的進(jìn)場(chǎng)排序與調(diào)度問題，并考察了不同性能指標(biāo)的解決方案之間的差異。Hong等[14]以總飛行時(shí)間和序列變化次數(shù)最小化為目標(biāo)，基于混合整數(shù)線性規(guī)劃對(duì)著陸次序和時(shí)間進(jìn)行優(yōu)化。Zhang等[15]采用基于帕累托支配的多目標(biāo)模擬退火算法(MOSA)，解決了在考慮連續(xù)航班運(yùn)行的條件下，最大化跑道運(yùn)行能力和最小化飛行延誤的進(jìn)場(chǎng)排序問題。帶精英策略的非支配排序遺傳算法(NSGA-II)在多目標(biāo)進(jìn)場(chǎng)排序與調(diào)度研究中應(yīng)用廣泛：Mokhtarimousavi等[16]考慮了跑道容量、地面成本和環(huán)境成本，基于NSGA-II實(shí)現(xiàn)進(jìn)場(chǎng)排序與調(diào)度的多目標(biāo)優(yōu)化；馬園園等[17]面向延誤時(shí)間、延誤架次和運(yùn)行公平性的目標(biāo)，利用NSGA-II求解多目標(biāo)進(jìn)場(chǎng)排序與優(yōu)化；劉繼新等[18]在綜合考慮空管、航空公司和機(jī)場(chǎng)三方的利益需求下，提出一種時(shí)隙交換方法，并基于NSGA-II解決不同交通密度情況下的進(jìn)場(chǎng)排序與調(diào)度問題。

上述多目標(biāo)優(yōu)化兼顧了諸多利益相關(guān)方的訴求，也豐富了進(jìn)場(chǎng)排序與調(diào)度研究的內(nèi)涵。然而，仍存在兩方面問題亟待解決：① 諸多優(yōu)化目標(biāo)之間是否存在冗余，優(yōu)化目標(biāo)選擇能否找到依據(jù)；② 如 何評(píng)價(jià)多目標(biāo)優(yōu)化的解集，能否在常用的NSGA-II之外尋求更為精準(zhǔn)和高效的多目標(biāo)優(yōu)化求解算法。本文擬通過將進(jìn)場(chǎng)排序與調(diào)度問題等效于機(jī)器調(diào)度問題，借鑒機(jī)器調(diào)度領(lǐng)域的研究成果，為多目標(biāo)進(jìn)場(chǎng)排序與調(diào)度的目標(biāo)選擇提供依據(jù)；進(jìn)一步，引入非支配排序，基于近年來廣泛應(yīng)用的帝國(guó)競(jìng)爭(zhēng)算法[19]，設(shè)計(jì)多目標(biāo)帝國(guó)競(jìng)爭(zhēng)算法(Multi-Objective Imperialist Competitive Algorithm，MOICA)，解決進(jìn)場(chǎng)排序與調(diào)度問題；最后，基于通用數(shù)據(jù)集與實(shí)際運(yùn)行數(shù)據(jù)構(gòu)建仿真驗(yàn)證的場(chǎng)景，一方面考慮帕累托最優(yōu)解集的評(píng)價(jià)指標(biāo)，對(duì)比分析本文提出的MOICA與進(jìn)場(chǎng)排序與調(diào)度領(lǐng)域廣泛使用的NSGA-II及MOSA，另一方面考察了MOICA在實(shí)際管制運(yùn)行中的優(yōu)化效能。

1 多目標(biāo)進(jìn)場(chǎng)調(diào)度模型構(gòu)建

1.1 問題等效

進(jìn)場(chǎng)航空器的排序與調(diào)度問題可視為機(jī)器調(diào)度問題[20-21]：跑道為機(jī)器，進(jìn)場(chǎng)航空器為工件，其進(jìn)入終端空域的時(shí)間等效于工件的出現(xiàn)時(shí)間，航空器的最早、最晚以及計(jì)劃到達(dá)時(shí)刻，分別與工件提交時(shí)間、最后期限以及交付時(shí)間一一對(duì)應(yīng)，而尾流間隔約束則與順序決定的準(zhǔn)備時(shí)間相當(dāng)。為后續(xù)闡述方便，相關(guān)變量如表1所示。

表1 變量定義

1.2 目標(biāo)選擇

最小化最大完成時(shí)間min(maxCi)，表明最后優(yōu)化一架航空器盡早著陸，意味著跑道運(yùn)行容量的最大化，該目標(biāo)是機(jī)場(chǎng)的關(guān)注點(diǎn)。

最小化最大流動(dòng)時(shí)間min(maxFi)，表明最小化進(jìn)場(chǎng)航空器在終端空域飛行的最長(zhǎng)時(shí)間，意味著對(duì)各個(gè)航空公司的航空器實(shí)施公平的調(diào)度。

最小化最大延誤時(shí)間min(maxTi)，表明最小化進(jìn)場(chǎng)航空器的最大延誤，體現(xiàn)對(duì)航空器實(shí)施公平調(diào)度。

Cmax(S*{max})=max(C(S*{Σ}))

證明如下：

首先，設(shè)Cmax(S*{max})>max(C(S*{Σ}))。因?yàn)镃max(S*{max})=max(C(S))，定義S為任意一個(gè)調(diào)度，而S*{Σ}為S的其中一種情況，所以假設(shè)Cmax(S*{max})>max(C(S*{Σ}))不成立。

最后，證得推論成立。

1.3 模型構(gòu)建

基于上述分析，多目標(biāo)進(jìn)場(chǎng)優(yōu)化排序與調(diào)度問題可以描述為：對(duì)于給定n架進(jìn)場(chǎng)航空器，當(dāng)滿足著陸時(shí)間窗約束、尾流間隔約束、著陸次序的最大位置轉(zhuǎn)換約束等，以最小化進(jìn)場(chǎng)航空器終端區(qū)內(nèi)的總飛行時(shí)間、最小化最大飛行時(shí)間、最小化進(jìn)場(chǎng)航空器的總延誤時(shí)間為目標(biāo)，優(yōu)化進(jìn)場(chǎng)航空器的著陸序列及時(shí)間。構(gòu)建數(shù)學(xué)模型如下：

(1a)

(1b)

min maxFi

(1c)

(1d)

(1e)

(1f)

(1g)

(1h)

(1i)

kCPS≤K

(1j)

其中：式(1d)為進(jìn)場(chǎng)航空器著陸時(shí)間的時(shí)間窗限制；式(1e)表示著陸次序；式(1f)確保了進(jìn)場(chǎng)航空器前后機(jī)之間的尾流間隔約束；式(1g)與式(1h)表示進(jìn)場(chǎng)航空器的延誤時(shí)間定義及約束；式(1i)表示進(jìn)場(chǎng)航空器在終端空域的飛行時(shí)間；式(1j)表示著陸次序調(diào)配需要滿足的最大位置轉(zhuǎn)換約束。

2 多目標(biāo)進(jìn)場(chǎng)調(diào)度算法設(shè)計(jì)

2.1 帝國(guó)競(jìng)爭(zhēng)算法

帝國(guó)競(jìng)爭(zhēng)算法(Imperialist Competitive Algorithm, ICA)[19]是一種社會(huì)政治進(jìn)化算法，該算法將初始解集視為若干個(gè)帝國(guó)(Emp.)，每個(gè)帝國(guó)由一個(gè)殖民國(guó)家(Imp.)與若干個(gè)殖民地(Col.)組成，其中殖民國(guó)家代表該帝國(guó)內(nèi)最優(yōu)解，通過成本值(Costi=f(Countryi))確定。對(duì)于最小化問題，其算法簡(jiǎn)要流程如下所示：

步驟1初始化。隨機(jī)產(chǎn)生初始國(guó)家集合N，根據(jù)成本值選取殖民國(guó)家，分配殖民地，組建帝國(guó)。

步驟2同化。帝國(guó)中的殖民地在一定概率下向殖民國(guó)家靠攏。

步驟3革命。帝國(guó)中的殖民國(guó)家及殖民地在一定概率下發(fā)生突變。

步驟4帝國(guó)內(nèi)競(jìng)爭(zhēng)。更新帝國(guó)內(nèi)殖民國(guó)家與殖民地的成本值，成本值最小的成為新的殖民國(guó)家。

步驟5帝國(guó)間競(jìng)爭(zhēng)。更新各帝國(guó)勢(shì)力值，將最弱帝國(guó)的最弱殖民地轉(zhuǎn)移到最強(qiáng)帝國(guó)中。

步驟6帝國(guó)消亡。若某帝國(guó)中所有殖民地都被掠奪，則此殖民國(guó)家淪為殖民地，該帝國(guó)消亡。

步驟7驗(yàn)證終止條件。若滿足，輸出最優(yōu)殖民國(guó)家，否則重復(fù)步驟2～步驟6，直到滿足終止條件。

帝國(guó)競(jìng)爭(zhēng)算法的優(yōu)點(diǎn)在于：通過帝國(guó)內(nèi)競(jìng)爭(zhēng)和帝國(guó)間競(jìng)爭(zhēng)，加強(qiáng)深度搜索和廣度搜索，從而提升了鄰域搜索和全局優(yōu)化的能力。

2.2 多目標(biāo)帝國(guó)競(jìng)爭(zhēng)算法

將帝國(guó)競(jìng)爭(zhēng)算法引入進(jìn)場(chǎng)排序與調(diào)度的多目標(biāo)優(yōu)化，相較于傳統(tǒng)帝國(guó)競(jìng)爭(zhēng)算法，其特點(diǎn)在于：① 解集的初始化與更新策略；② 面向多目標(biāo)優(yōu)化的成本函數(shù)的構(gòu)建；③ 面向多目標(biāo)優(yōu)化的帝國(guó)勢(shì)力的衡量。假設(shè)多目標(biāo)帝國(guó)競(jìng)爭(zhēng)算法(MOICA)的最大迭代次數(shù)imax，種群數(shù)量為npop，殖民國(guó)家數(shù)量nimp，MOICA的算法流程圖如圖1所示。

圖1 多目標(biāo)帝國(guó)競(jìng)爭(zhēng)算法流程示意圖

1) 初始化帝國(guó)

對(duì)于進(jìn)場(chǎng)航空器排序與調(diào)度問題，各航空器的優(yōu)化著陸時(shí)間構(gòu)成一個(gè)初始解，即一個(gè)國(guó)家。生成初始解集時(shí)，需要滿足時(shí)間窗約束(ri,di)，本文擬采用線性插值實(shí)現(xiàn)解集初始化，如式(2)所示。

Ci=ξdi+(1-ξ)rii∈I

(2)

式中：ξ∈[0,1]。

由于面向多目標(biāo)優(yōu)化，常規(guī)的基于目標(biāo)函數(shù)構(gòu)建成本函數(shù)的方式并不可行。鑒于此，本文采用非支配排序與擁擠距離實(shí)現(xiàn)成本函數(shù)的構(gòu)建，具體包括：

① 基于初始化的解集計(jì)算目標(biāo)函數(shù)值，并針對(duì)所得的目標(biāo)值進(jìn)行快速非支配排序。

(3)

③ 初始化殖民國(guó)家，優(yōu)先從帕累托前沿(Pareto Front，PF)中選取殖民國(guó)家，若PF中解的個(gè)數(shù)小于設(shè)定的帝國(guó)個(gè)數(shù)，則從下一層級(jí)中依次選擇成本值小的解作為補(bǔ)充。

④ 初始化殖民地，采用輪盤賭的方式，利用式(4)將殖民地分配給殖民國(guó)家。

(4)

式中：α為選擇系數(shù)。

如此完成了初始化帝國(guó)的工作，每個(gè)帝國(guó)，即進(jìn)場(chǎng)排序與調(diào)度的初始解集的子集，包含一個(gè)PF解和若干個(gè)初始解。

2) 同 化

同化過程是帝國(guó)內(nèi)殖民地向殖民國(guó)家靠攏的過程，也即進(jìn)場(chǎng)排序與調(diào)度的可行解向帕累托最優(yōu)解學(xué)習(xí)的過程。本文采用差分進(jìn)化的方式，如式(5)所示，實(shí)現(xiàn)帝國(guó)內(nèi)的同化。

Col.←Col.+β·rand·(Imp.-Col.)

(5)

式中:β表示差分進(jìn)化系數(shù)；rand為隨機(jī)數(shù)。

3) 革 命

為防止迭代過程中陷入局部最優(yōu)解，對(duì)殖民地進(jìn)行革命操作，文中主要采用單點(diǎn)變異、兩點(diǎn)交換和子段逆序3種算子進(jìn)行革命。

單點(diǎn)變異算子中，隨機(jī)選擇一個(gè)進(jìn)場(chǎng)航空器，按式(2)分配新的優(yōu)化著陸時(shí)間；兩點(diǎn)交換算子中，隨機(jī)交換兩個(gè)航空器的優(yōu)化著陸時(shí)間；子段逆序算子中，隨機(jī)選擇一部分航空器的優(yōu)化降落序列，并逆序。值得注意的是，在實(shí)施上述操作需要考慮位置轉(zhuǎn)換約束(Constrained Position Shift, CPS)以及相應(yīng)的尾流間隔，以確保革命后的解仍是可行解。

4) 帝國(guó)內(nèi)競(jìng)爭(zhēng)

基于同化和革命的解集更新，計(jì)算目標(biāo)函數(shù)值，再次進(jìn)行快速非支配排序操作，利用式(3)更新國(guó)家的成本值。進(jìn)一步，比較帝國(guó)內(nèi)殖民國(guó)家與殖民地的成本，若殖民地的成本優(yōu)于對(duì)應(yīng)的殖民國(guó)家時(shí)，那么優(yōu)秀殖民地成為新的殖民國(guó)家，原來殖民國(guó)家淪為殖民地。

5) 帝國(guó)間競(jìng)爭(zhēng)

帝國(guó)間競(jìng)爭(zhēng)是各個(gè)帝國(guó)間殖民地再分配的過程，勢(shì)力弱小的帝國(guó)將被勢(shì)力強(qiáng)大的帝國(guó)逐步吞并，直至消亡。帝國(guó)勢(shì)力值計(jì)算過程如下所述：

(6)

Empj.Cost

(7)

(8)

在此過程中，式(6)綜合帝國(guó)內(nèi)殖民國(guó)家與殖民地的成本計(jì)算帝國(guó)總成本，其中:μ表示勢(shì)力值系數(shù); |Empj|表示帝國(guó)中殖民地的數(shù)目；隨后，按照式(7)和式(8)實(shí)現(xiàn)勢(shì)力值的量綱統(tǒng)一，其中式(7)的作用在于防止勢(shì)力為零的情況，本文λ取值為1.2。

2.3 多目標(biāo)優(yōu)化解的評(píng)價(jià)

如何評(píng)價(jià)多目標(biāo)進(jìn)場(chǎng)排序與調(diào)度優(yōu)化解集的優(yōu)劣，選擇兼顧各利益相關(guān)方訴求的優(yōu)化方案，也是值得深入研究的問題。本文擬從帕累托最優(yōu)解的收斂性和多樣性兩個(gè)角度出發(fā)，通過如下4個(gè)指標(biāo)[23]評(píng)估本文提出的多目標(biāo)帝國(guó)競(jìng)爭(zhēng)算法。

1) 覆蓋率 (C-Metric, CM)

覆蓋率是衡量帕累托解集收斂性的指標(biāo)，即

CCM(PFA,PFB)=

(9)

式中：PFA、PFB分別為兩組Pareto最優(yōu)解集。分子表示解集B受解集A支配的解的個(gè)數(shù)，分母表示解集B中所有解個(gè)數(shù)。若CCM(PFA,PFB)=1，說明解集B完全受解集A所支配，即解集B收斂性比A差。

2) 空間分布 (SPacing, SP)

空間分布是評(píng)估帕累托解集廣泛程度的指標(biāo)，即

(10)

3) 超體積 (Hyper Volume, HV)

超體積是評(píng)估帕累托解集收斂性和多樣性的綜合指標(biāo)，即

(11)

式中：δ(·)表示勒貝格測(cè)度，用來測(cè)量體積；Vk表示第k個(gè)點(diǎn)與參考點(diǎn)圍成的區(qū)域超體積。超體積值越大，表明解集越好。

4) 平均理想距離(Mean Ideal Distance, MID)

平均理想距離衡量帕累托解集和理想點(diǎn)之間距離的指標(biāo)，即

CMID(PF)=

(12)

3 仿真驗(yàn)證

仿真驗(yàn)證從2個(gè)角度展開，一方面利用進(jìn)場(chǎng)排序與調(diào)度研究領(lǐng)域常用的基準(zhǔn)案例——OR數(shù)據(jù)集(http:∥people.brunel.ac.uk/～mastjjb/jeb/orlib/ airlandinfo.html)，考察MOICA的效果，并與多目標(biāo)進(jìn)場(chǎng)排序與調(diào)度常用的NSGA-II及MOSA進(jìn)行對(duì)比；另一方面采用實(shí)際運(yùn)行數(shù)據(jù)，驗(yàn)證MOICA的適用性。

MOICA通過MATLAB2014b編程實(shí)現(xiàn)，運(yùn)行環(huán)境為：Windows10操作系統(tǒng)，Corei7-7700處理器、3.6 GHz主頻和8 GB內(nèi)存的微機(jī)。

3.1 OR數(shù)據(jù)驗(yàn)證

3.1.1 運(yùn)行場(chǎng)景

OR數(shù)據(jù)集中關(guān)于進(jìn)場(chǎng)排序與調(diào)度共有13組案例，航空器架次從10～500架不等。由于第1～8組案例不滿足進(jìn)場(chǎng)排序與調(diào)度的尾流間隔三角不等式，故采用第9～13組數(shù)據(jù)，分別有100/150/200/250/500架次航空器，第9～12組數(shù)據(jù)，構(gòu)成大規(guī)模數(shù)據(jù)集；拆分第13組數(shù)據(jù)，構(gòu)成小規(guī)模數(shù)據(jù)集，拆分的依據(jù)在于——進(jìn)場(chǎng)航空器進(jìn)入終端空域的時(shí)間具有波次效應(yīng)。進(jìn)一步，為了反映進(jìn)場(chǎng)航空器的交通需求特性，引入壓縮因子Kd，即

(13)

具體的數(shù)據(jù)集信息如表2所示，數(shù)據(jù)集中airland #13.1參數(shù)信息詳情如圖2所示，其中藍(lán)色方框表示航空器進(jìn)入終端空域時(shí)間，黑色星號(hào)表示著陸時(shí)間窗，紅色圓圈表示預(yù)計(jì)著陸時(shí)間。

圖2 仿真場(chǎng)景示意圖

表2 仿真數(shù)據(jù)集信息

實(shí)驗(yàn)中：MOICA應(yīng)用于大規(guī)模數(shù)據(jù)集時(shí)，imax=250、npop=100、nimp=7；應(yīng)用小規(guī)模數(shù)據(jù)集時(shí)，imax=150、npop=75、nimp=5；革命概率選為0.35，選擇系數(shù)為0.9，同化系數(shù)為2，勢(shì)力值系數(shù)μ=0.2。NSGA-II中交叉概率為0.7，變異概率為0.02。MOSA中初始溫度值為1 000，冷卻系數(shù)0.98。

3.1.2 結(jié)果分析

首先，針對(duì)所有數(shù)據(jù)集進(jìn)行MOICA、NSGA-II和MOSA的仿真驗(yàn)證，同時(shí)利用多目標(biāo)優(yōu)化解的評(píng)價(jià)指標(biāo)進(jìn)行對(duì)比，具體如表3所示。由于元啟發(fā)式算法(如模擬退火、遺傳算法、帝國(guó)競(jìng)爭(zhēng)算法)的優(yōu)化結(jié)果與參數(shù)以及初始化息息相關(guān)，表3的結(jié)果基于20次獨(dú)立仿真的均值進(jìn)行對(duì)比。

由表3可知：對(duì)于14組仿真數(shù)據(jù)集，覆蓋率指標(biāo)(CCM)，MOICA全面優(yōu)于NSGA-II與MOSA；空間分布指標(biāo)(CSP)，MOICA最優(yōu)，MOSA較劣；超體積指標(biāo)(CHV)，MOICA在12組數(shù)據(jù)集中占優(yōu)；平均理想距離(CMID)，MOICA在13組數(shù)據(jù)集中占優(yōu)。通過計(jì)算各組數(shù)據(jù)在各類指標(biāo)下的均值可見，MOICA的帕累托最優(yōu)解相對(duì)于NSGA-II與MOSA而言，解集更占支配地位(CCM)、解集的分布更均勻(CSP)、解集的收斂性更好(CHV)、解集的質(zhì)量更高(CMID)。進(jìn)一步分析MOICA解集非占優(yōu)的情況發(fā)生在小規(guī)模數(shù)據(jù)集OR#13.1/OR#13.4/OR#13.7，原因在于上述數(shù)據(jù)集的壓縮因子Kd較大，對(duì)應(yīng)進(jìn)場(chǎng)需求低，排序與調(diào)度難度較小。此時(shí)，NSGA-II與MOSA也能獲得較優(yōu)解。對(duì)于最復(fù)雜數(shù)據(jù)集OR#13.6，本文提出的MOICA表現(xiàn)更好。

表3 OR數(shù)據(jù)集仿真結(jié)果對(duì)比

其次，選取數(shù)據(jù)組OR #9，應(yīng)用MOICA、NSGA-II與MOSA分別進(jìn)行500次獨(dú)立實(shí)驗(yàn)。針對(duì)仿真結(jié)果計(jì)算指標(biāo)：空間分布、超體積、平均理想距離，并將500組評(píng)價(jià)指標(biāo)以四分位圖的方式顯示仿真結(jié)果，如圖3所示。

圖3 多目標(biāo)優(yōu)化解評(píng)價(jià)指標(biāo)的四分位圖

由圖3可知：OR #9數(shù)據(jù)的500次獨(dú)立實(shí)驗(yàn)結(jié)果進(jìn)一步驗(yàn)證了相對(duì)于NSGA-II與MOSA而言，MOICA的優(yōu)越性。覆蓋率指標(biāo)未列入，原因在于MOICA帕累托解集均占支配地位。

最后，為了考察多目標(biāo)優(yōu)化算法的運(yùn)算效率，圖4提供了不同數(shù)據(jù)集的CPU時(shí)間示意圖，無論是本文提出的MOICA，還是對(duì)比的NSGA-II，小規(guī)模數(shù)據(jù)集的迭代次數(shù)設(shè)為150次，大規(guī)模數(shù)據(jù)集的迭代次數(shù)設(shè)為250次。

圖4 多目標(biāo)優(yōu)化運(yùn)行時(shí)間對(duì)比

由圖4可知：一方面，本文提出的MOICA其算法效率均優(yōu)于NSGA-II與MOSA；另一方面，多目標(biāo)優(yōu)化算法的運(yùn)行效率主要依賴于迭代次數(shù)和航空器架次，當(dāng)?shù)螖?shù)一致時(shí)(如大規(guī)模數(shù)據(jù)集，imax=250)，數(shù)據(jù)集規(guī)模越大其優(yōu)化時(shí)間越長(zhǎng)。

3.2 實(shí)際數(shù)據(jù)優(yōu)化分析

3.2.1 仿真場(chǎng)景構(gòu)建

以長(zhǎng)沙黃花機(jī)場(chǎng)(四字碼ZGHA))進(jìn)場(chǎng)運(yùn)行為例，圖5顯示了2019年12月26日8:00—2019年12月27日8:00共計(jì)233條進(jìn)場(chǎng)航空器的綜合航跡，長(zhǎng)沙機(jī)場(chǎng)共有5個(gè)進(jìn)港點(diǎn)(BEMTA, LLC, LIG, OVTAN, DAPRO)。

圖5 長(zhǎng)沙黃花機(jī)場(chǎng)進(jìn)場(chǎng)運(yùn)行航跡示意圖

圖6 進(jìn)場(chǎng)航空器飛行時(shí)間四分位圖

表4 尾流間隔標(biāo)準(zhǔn)[22]

3.2.2 仿真結(jié)果分析

利用本文提出的MOICA實(shí)現(xiàn)長(zhǎng)沙機(jī)場(chǎng)的進(jìn)場(chǎng)排序與調(diào)度優(yōu)化，選取23:00—00:30內(nèi)的21架進(jìn)場(chǎng)航空器作為優(yōu)化對(duì)象，相關(guān)參數(shù)的設(shè)定同3.1節(jié)的大規(guī)模數(shù)據(jù)集。

在本次的實(shí)例仿真中，尾流間隔分別選取表4 對(duì)應(yīng)標(biāo)準(zhǔn)的1.2倍、1.5倍和1.8倍實(shí)施驗(yàn)證，其總延誤時(shí)間，總飛行時(shí)間和最大飛行時(shí)間的優(yōu)化結(jié)果如表5所示。

由表5可知，利用MOICA實(shí)現(xiàn)進(jìn)場(chǎng)的排序與調(diào)度可以有效地提升運(yùn)行效率與效益，兼顧空管、航司、機(jī)場(chǎng)、民眾的不同訴求。即便是將尾流間隔限制擴(kuò)大到現(xiàn)行標(biāo)準(zhǔn)的1.8倍，相對(duì)于管制實(shí)際運(yùn)行結(jié)果，總延誤時(shí)間可以降低41.2%、總飛行時(shí)間可以減少11.4%、最大飛行時(shí)間可以縮短8.6%。

表5 實(shí)際案例仿真驗(yàn)證結(jié)果

進(jìn)一步，為考察實(shí)際著陸序列與優(yōu)化著陸序列的變化情況，圖7以時(shí)序圖的形式，展示了1.5倍標(biāo)準(zhǔn)間隔設(shè)置下，各進(jìn)場(chǎng)航空器在不同進(jìn)港點(diǎn)(Entry-FIX)的出現(xiàn)時(shí)間(黑色圓圈所示)與序列、各進(jìn)場(chǎng)航空器的預(yù)計(jì)著陸時(shí)間(Estimate Time of Arrival, ETA)(綠色三角所示)與序列、各進(jìn)場(chǎng)航空器的優(yōu)化著陸時(shí)間(Schedule Time of Arrival, STA)(藍(lán)色菱形所示)與序列、各進(jìn)場(chǎng)航空器的實(shí)際著陸時(shí)間(Actual Time of Arrival, ATA)(紅色方框所示)與序列。

由圖7可知，1.5倍的間隔標(biāo)準(zhǔn)與實(shí)際管制運(yùn)行時(shí)的安全間隔相仿，引入MOICA的優(yōu)勢(shì)在于通過調(diào)整著陸次序，最大可能地逼近設(shè)置的尾流安全間隔，從而實(shí)現(xiàn)總延誤時(shí)間、總飛行時(shí)間以及最大飛行時(shí)間地減少。至于管制員在實(shí)際運(yùn)行中未能應(yīng)用最佳著陸序列的原因，可以通過不同時(shí)間點(diǎn)進(jìn)場(chǎng)航空器態(tài)勢(shì)加以解釋，如圖8所示。

圖8展示了從23:30—23:55這段時(shí)間內(nèi)，10架進(jìn)場(chǎng)航空器的運(yùn)行態(tài)勢(shì)。航空器的選擇是基于圖7的分析。

圖8 進(jìn)場(chǎng)航空器不同時(shí)刻的態(tài)勢(shì)示意圖

由圖7可知，進(jìn)場(chǎng)航空器可以粗略分為3個(gè)“波次”，第1波共有12架；第2波共有4架；第3波也是4架。前12架中，可以忽略第一架與最后一架著陸的航空器(均由DAPRO進(jìn)港)，因此余下10架的構(gòu)成為：2架次DAPRO進(jìn)港，1架次BEMTA進(jìn)港，2架次LLC進(jìn)港，3架次LIG進(jìn)港，以及2架次OVT進(jìn)港。管制員對(duì)于西向進(jìn)港(LLC/BEMTA)航空器的調(diào)配策略是等待；對(duì)于北向(DAPRO)和南向(LIG)進(jìn)港航空器使用向東側(cè)偏離策略；至于東向進(jìn)港(OVTAN)航空器則向北側(cè)調(diào)配。23:35和23:40時(shí)，管制員發(fā)現(xiàn)著陸需求較為旺盛，于是分別按既定策略引導(dǎo)進(jìn)場(chǎng)航空器作機(jī)動(dòng)飛行。此時(shí)，管制員引導(dǎo)主要依賴經(jīng)驗(yàn)，兼之飛行員具體操控航空器時(shí)對(duì)管制員指令的依從度無法預(yù)知，最終導(dǎo)致無法充分利用終端空域以及跑道的容量。因此，MOICA可以為管制員提供著陸序列與時(shí)間的決策支持，至于如何給定確切的管制指令，本文擬借助于點(diǎn)融合系統(tǒng) (Point Merge System, PMS) 實(shí)現(xiàn)。

圖7 進(jìn)場(chǎng)航空器著陸時(shí)序?qū)Ρ仁疽鈭D

基于統(tǒng)計(jì)分析獲取飛行時(shí)間或者采用四維航跡預(yù)測(cè)[24]，能夠?qū)崿F(xiàn)進(jìn)場(chǎng)運(yùn)行“可見”目標(biāo)；采用本文提出的MOICA兼顧各利益相關(guān)方的訴求開展排序與調(diào)度，可以實(shí)現(xiàn)進(jìn)場(chǎng)運(yùn)行“可優(yōu)”目標(biāo)；如何基于優(yōu)化的著陸序列與時(shí)間向管制員提供決策支持，方能實(shí)現(xiàn)進(jìn)場(chǎng)運(yùn)行“可達(dá)”目標(biāo)。為此，本文擬通過PMS解決優(yōu)化結(jié)果“可達(dá)”的問題。圖9提供了引入PMS后的進(jìn)場(chǎng)程序，以及基于該程序和1.2倍間隔標(biāo)準(zhǔn)優(yōu)化結(jié)果的進(jìn)場(chǎng)航空器運(yùn)行示意圖(注：1.5倍間隔標(biāo)準(zhǔn)的配備需要通過引入標(biāo)準(zhǔn)等待實(shí)現(xiàn))。

由圖9可見，PMS的引入具備如下優(yōu)勢(shì)：①進(jìn) 場(chǎng)排序與調(diào)度優(yōu)化結(jié)果的可達(dá)，根據(jù)優(yōu)化著陸序列與時(shí)間反推PMS程序結(jié)構(gòu)下的航空器四維軌跡，為管制員提供決策建議；② 管制決策建議簡(jiǎn)單有效，將傳統(tǒng)的管制指令簡(jiǎn)化為排序支路上的轉(zhuǎn)彎，降低了管制工作負(fù)荷；③ 由于管制引導(dǎo)僅發(fā)生在排序支路上，提升了飛行員的態(tài)勢(shì)感知與情境意識(shí)；④ 飛行軌跡更為規(guī)整有序，有效降低了終端空域進(jìn)場(chǎng)運(yùn)行的復(fù)雜性。值得注意的是，由于引入PMS導(dǎo)致預(yù)計(jì)到達(dá)時(shí)間與著陸時(shí)間窗變化，因此表5的相關(guān)結(jié)論需要另行計(jì)算。

圖9 引入PMS的進(jìn)場(chǎng)排序與調(diào)度運(yùn)行示意圖

4 結(jié) 論

1) 借鑒機(jī)器調(diào)度領(lǐng)域的研究成果，梳理和刪減進(jìn)場(chǎng)排序與調(diào)度問題所對(duì)應(yīng)的目標(biāo)函數(shù)，最終確定3個(gè)指標(biāo)：最小化總延誤時(shí)間、最小化總飛行時(shí)間、最小化最大飛行時(shí)間。從理論角度分析和證明，上述目標(biāo)能夠同時(shí)滿足空管、航司、機(jī)場(chǎng)以及民眾的不同訴求。

2) 面向3個(gè)目標(biāo)，考慮著陸時(shí)間窗約束、尾流間隔約束、航空器著陸次序的最大位置轉(zhuǎn)換約束等，構(gòu)建進(jìn)場(chǎng)排序與調(diào)度多目標(biāo)優(yōu)化模型，以實(shí)現(xiàn)管制工作負(fù)荷降低、跑道運(yùn)行容量增強(qiáng)、航空器正點(diǎn)率提升、各航司調(diào)度公平的目的。

3) 基于非支配排序，設(shè)計(jì)了多目標(biāo)帝國(guó)競(jìng)爭(zhēng)算法，求解多目標(biāo)進(jìn)場(chǎng)排序與調(diào)度模型的帕累托解。同時(shí)，引入覆蓋率指標(biāo)、空間分布指標(biāo)、超體積指標(biāo)和平均理想距離等指標(biāo)，衡量帕累托解集優(yōu)劣。

4) 從兩個(gè)角度實(shí)施仿真驗(yàn)證：一方面，利用基準(zhǔn)案例(OR數(shù)據(jù)集)對(duì)比多目標(biāo)帝國(guó)競(jìng)爭(zhēng)算法(MOICA)與多目標(biāo)遺傳算法(NSGA-II)及多目標(biāo)模擬退火算法(MOSA)的解集質(zhì)量與求解效率；另一方面，利用實(shí)際運(yùn)行案例考察本文提出方法的有效性，并引入點(diǎn)融合系統(tǒng)保障優(yōu)化結(jié)果的可行性。

5) 本文主要解決了單跑道進(jìn)場(chǎng)排序與調(diào)度問題，未來的研究會(huì)擴(kuò)展到多跑道、進(jìn)離場(chǎng)、以及多機(jī)場(chǎng)終端空域的運(yùn)行場(chǎng)景。