基于多目標(biāo)融合及改進(jìn)遺傳算法的終端區(qū)進(jìn)場(chǎng)協(xié)同排序

向征， 袁博軒， 劉玥琳

(中國(guó)民用航空飛行學(xué)院空中交通管理學(xué)院， 廣漢 618307)

隨著國(guó)民經(jīng)濟(jì)水平的快速提高，民航業(yè)的發(fā)展速度越來越快。然而，空中交通的繁榮，交通流量的增長(zhǎng)，讓本不富足的空域容量更加雪上加霜，空中交通流量過大導(dǎo)致航空器安全性降低、運(yùn)行效率下降、公司效益下降。因此，這不僅使航班運(yùn)行的安全性降低，延誤率增高，也給國(guó)內(nèi)民航業(yè)帶來了嚴(yán)重的經(jīng)濟(jì)損失。

為了緩解矛盾、降低延誤、提高效率，針對(duì)航班的不同飛行階段，業(yè)界在航路建設(shè)與利用、機(jī)場(chǎng)建設(shè)與利用等方面采取了多種手段努力解決問題。這些舉措，對(duì)于提高航班運(yùn)行效率產(chǎn)生了顯著作用。但相比終端管制區(qū)域來說并不簡(jiǎn)單，終端區(qū)是一個(gè)航空器降落的必經(jīng)之地也是流量較大航路較復(fù)雜的區(qū)域，所以為了能夠提升航空器效率和空域使用率，終端區(qū)的規(guī)劃就顯得尤為重要。多機(jī)場(chǎng)終端區(qū)程序繁雜，線路復(fù)雜，運(yùn)行效率低下，很容易造成航班延誤。更為關(guān)鍵的是，終端區(qū)內(nèi)各機(jī)場(chǎng)間有很強(qiáng)的關(guān)聯(lián)性，某一機(jī)場(chǎng)的航班延誤極易影響其他機(jī)場(chǎng)航班，直接降低空中交通運(yùn)行效率并可能導(dǎo)致安全隱患。雖然終端區(qū)運(yùn)行效率的重要性日漸凸顯，但目前針對(duì)這類問題的方法研究還太過于缺乏。

國(guó)外在20世紀(jì)60年代末就對(duì)進(jìn)場(chǎng)航班排序問題開始進(jìn)行研究，到目前為止已經(jīng)取得了豐碩的成果。早期Dear[1]提出先到先服務(wù)是低效的，采用全新的約束位置轉(zhuǎn)換算法消除了以最小延遲為目標(biāo)模型的一些不良特性，并得出該方法是實(shí)用，高效和極為靈活的，為后續(xù)的研究發(fā)展奠定的良好的基礎(chǔ)。1978年，Psaraftis[2]針對(duì)飛機(jī)排序問題的3個(gè)方面提出了動(dòng)態(tài)規(guī)劃算法，考慮到了兩個(gè)目標(biāo)：如何盡快降落所有計(jì)劃到達(dá)飛機(jī)，或者如何最小化乘客的總等待時(shí)間。1995年，Abela等[3]提出了一種在高密度航站區(qū)對(duì)飛機(jī)進(jìn)行排序和調(diào)度的方法，并利用位置約束轉(zhuǎn)移算法進(jìn)行了檢驗(yàn)，并對(duì)其有效性進(jìn)行了測(cè)試，在先到先得的跑道策略中，特別是在高峰時(shí)段，潛在的容量得到提升。2013年，Awasthi等[4]對(duì)美國(guó)國(guó)家航天局所使用的順序排序模型進(jìn)行了全面的優(yōu)化，在先前結(jié)果的基礎(chǔ)上研究出了更為可靠的進(jìn)場(chǎng)排序的模型。2017年，Hong等[5]主要針對(duì)管制員負(fù)荷的問題，通過蒙特卡洛分析法結(jié)合整數(shù)規(guī)劃的思想對(duì)航空器進(jìn)場(chǎng)排序進(jìn)行了優(yōu)化。2018年，Meriem等[6]在對(duì)空域交通線路的建模中提出了一種新的混合整數(shù)規(guī)劃公式，其中將主要問題分解為3個(gè)子問題即航段和跑道上飛機(jī)進(jìn)近和著陸的調(diào)度排序問題，最后利用CPLEX數(shù)學(xué)優(yōu)化技術(shù)進(jìn)行了求解，結(jié)果表明了該方法的有效性。2019年，Zhang等[7]受航空器著陸和單機(jī)調(diào)度問題相似之處的啟發(fā)提出一種準(zhǔn)則選擇法通過最大總飛行時(shí)間和單航班的最大飛行時(shí)間為目標(biāo)函數(shù)構(gòu)建多目標(biāo)模型，利用一組基準(zhǔn)實(shí)例對(duì)所提出的模型和方法的性能進(jìn)行了評(píng)估。2020年，Abdelaziz等[8]提出一種基于迭代局部搜索和模擬退火算法(simulated annealing algorithm，SAA)混合算法的航空器著陸問題的解決方法，主要是在目標(biāo)時(shí)間范圍內(nèi)找到一個(gè)可行的飛機(jī)調(diào)度方案，利用兩種算法的優(yōu)勢(shì)結(jié)合13個(gè)大型實(shí)例來對(duì)解決方案的有效性和廣泛性進(jìn)行了評(píng)估，結(jié)果表明迭代模擬退火算法比其他先進(jìn)的方法表現(xiàn)得更好。

國(guó)內(nèi)對(duì)進(jìn)場(chǎng)航班排序方法的研究開始的比較晚，但也取得了豐碩的科研成果。1999年，荀海波等[9]對(duì)各類常見的基于時(shí)間的排序算法進(jìn)行了分析對(duì)比，針對(duì)機(jī)場(chǎng)終端區(qū)航空器的進(jìn)場(chǎng)次序提出了規(guī)劃算法。2004年，張兆寧等[10]通過對(duì)流量中的戰(zhàn)術(shù)管理進(jìn)行分析后發(fā)現(xiàn)，動(dòng)態(tài)管理航空器的起降是尤為關(guān)鍵的，于是在動(dòng)態(tài)航空器起降管理的基礎(chǔ)上加入了滑動(dòng)窗口機(jī)制，結(jié)果表明該方法可行且有效。2010年，楊晶妹[11]提出滾動(dòng)時(shí)域的策略來解決排序問題，結(jié)合時(shí)間提前量法建立了進(jìn)場(chǎng)航空器排序的問題，利用遺傳算法對(duì)該問題進(jìn)行了優(yōu)化計(jì)算求解。2015年，高偉等[12]利用模糊評(píng)判法和粗糙理論，建立了一套綜合評(píng)定體系，利用該體系中的各項(xiàng)指標(biāo)來對(duì)航空器進(jìn)行相應(yīng)的排序。2017年，張軍峰等[13]為解決終端區(qū)現(xiàn)狀問題，通過歸一化的思想將終端區(qū)看作一個(gè)整體來進(jìn)行思考，優(yōu)先解決局部最優(yōu)問題，最后利用模擬退火算法對(duì)其進(jìn)行了求解，實(shí)驗(yàn)證明這種方式的求解有效地提高了終端區(qū)的運(yùn)行效率。2019年，戴喜妹等[14]為深入研究解決多目標(biāo)模型問題，利用帝國(guó)競(jìng)爭(zhēng)算法對(duì)航空器進(jìn)場(chǎng)排序與調(diào)度進(jìn)行了優(yōu)化。同年，黃吉波[15]針對(duì)管制員指揮過程中的可執(zhí)行性建立了基于延誤分配的多機(jī)場(chǎng)航班排序模型，并利用相應(yīng)的算法進(jìn)行了求解。2020年，張兆寧等[16]針對(duì)機(jī)場(chǎng)跑道實(shí)際情況以及可供起降飛機(jī)的類型進(jìn)行分析，并整理出各項(xiàng)因素對(duì)航空器排序以及延誤航班的影響，為后續(xù)解決約束相關(guān)性打下了良好的基礎(chǔ)。2021年，夏正洪等[17]對(duì)比傳統(tǒng)雷達(dá)管制與程序管制特點(diǎn)與有效性利用雷達(dá)模擬機(jī)對(duì)航空器排序進(jìn)行了研究與分析。

隨著空中交通流量以及需求的不斷增長(zhǎng)，對(duì)空域容量以及流量的研究重點(diǎn)要從單一跑道逐漸向多跑道、單一機(jī)場(chǎng)逐漸向多機(jī)場(chǎng)這樣大型的交通流量區(qū)域過渡。求解算法上也要不斷地創(chuàng)新，目前包括利用滑動(dòng)窗口算法增加局部搜索最優(yōu)、解決多目標(biāo)的非支配排序遺傳算法Ⅱ(non-dominated sorting genetic algorithm Ⅱ，NSGA-Ⅱ)和帶有精英改進(jìn)遺傳算法等[18]。較之前相比效率大幅度提高，但還有如下許多不足之處。

(1)大部分的研究都是對(duì)單一機(jī)場(chǎng)、單一跑道進(jìn)行考慮，沒有充分考慮到多方面的耦合關(guān)系，比如機(jī)場(chǎng)與機(jī)場(chǎng)之間，機(jī)場(chǎng)與航空公司之間，多跑道與單跑道之間的關(guān)系[19]。

(2)優(yōu)化目標(biāo)過于單一，大多數(shù)是以最小延誤時(shí)間為目標(biāo)進(jìn)行優(yōu)化，忽略了多目標(biāo)的情況，比如跑道容量最大，顧客滿意度最高，公共資源公平使用率最高[20]。

(3)進(jìn)場(chǎng)排序考慮的方面太少，針對(duì)天氣因素、地形因素、跑道因素以及相關(guān)機(jī)場(chǎng)之間的構(gòu)型問題分配問題、管制員的指揮方式問題考慮地欠缺。

現(xiàn)針對(duì)當(dāng)今航空事業(yè)的發(fā)展現(xiàn)狀，大型機(jī)場(chǎng)以及大型機(jī)場(chǎng)群的現(xiàn)實(shí)需求，以終端區(qū)內(nèi)部范圍為界限，航空器在終端區(qū)內(nèi)運(yùn)行情況為對(duì)象，研究多機(jī)場(chǎng)終端區(qū)進(jìn)場(chǎng)航空器協(xié)同排序的問題。通過分析終端區(qū)的空域結(jié)構(gòu)和運(yùn)行特征，綜合考慮多方的公平以及利益需求，為航空器分配最優(yōu)的進(jìn)場(chǎng)順序，以適應(yīng)和緩解日益劇增的空域流量。

1 多機(jī)場(chǎng)系統(tǒng)定義及運(yùn)行主要問題與空域結(jié)構(gòu)的分析

1.1 多機(jī)場(chǎng)系統(tǒng)定義及運(yùn)行主要問題

研究對(duì)象為多機(jī)場(chǎng)終端區(qū)，首先要對(duì)終端區(qū)給予明確定義。根據(jù)《中華人民共和國(guó)飛行基本規(guī)則》中《民用航空使用空域辦法》有關(guān)規(guī)定，終端區(qū)即終端管制區(qū)，指的是在單個(gè)機(jī)場(chǎng)下或機(jī)場(chǎng)較多航路航線較多的范圍附近建立的管制匯合區(qū)稱作終端進(jìn)近管制區(qū)，需要區(qū)分的是在單個(gè)機(jī)場(chǎng)的條件下稱為進(jìn)近管制區(qū)，多個(gè)機(jī)場(chǎng)的條件下稱為終端管制區(qū)，且這些機(jī)場(chǎng)的進(jìn)離場(chǎng)航班運(yùn)行具有極強(qiáng)相關(guān)性的系統(tǒng)，如表1所示。

表1 多機(jī)場(chǎng)系統(tǒng)運(yùn)行相關(guān)因素

根據(jù)多機(jī)場(chǎng)系統(tǒng)定義及對(duì)多機(jī)場(chǎng)系統(tǒng)運(yùn)行相關(guān)因素的分析表明：多機(jī)場(chǎng)系統(tǒng)運(yùn)行中最突出的問題是多個(gè)機(jī)場(chǎng)共同競(jìng)爭(zhēng)使用同一受限的資源。通過對(duì)國(guó)內(nèi)相關(guān)研究文獻(xiàn)分析總結(jié)，提煉出多機(jī)場(chǎng)系統(tǒng)中運(yùn)行相關(guān)性問題，通過對(duì)運(yùn)行主要問題的分析不難看出，多機(jī)場(chǎng)運(yùn)行矛盾主要集中在空域資源的使用上，多機(jī)場(chǎng)系統(tǒng)運(yùn)行相關(guān)性在空域交互方面表現(xiàn)為如下5種形式，如表2所示。

表2 多機(jī)場(chǎng)系統(tǒng)空域交互分類

1.2 空域結(jié)構(gòu)的分析

終端區(qū)是多機(jī)場(chǎng)管制區(qū)一個(gè)最為關(guān)鍵的部分，航空器的起飛和降落、飛行姿態(tài)的轉(zhuǎn)變、速度的提升和降低等都是在終端管制區(qū)內(nèi)完成的。因此終端管制區(qū)的劃設(shè)合理性至關(guān)重要。

終端區(qū)內(nèi)的結(jié)構(gòu)比較復(fù)雜，分析其結(jié)構(gòu)就要從以下幾個(gè)元素著手：終端區(qū)進(jìn)場(chǎng)離場(chǎng)走廊口點(diǎn)、進(jìn)場(chǎng)離場(chǎng)航線、起始進(jìn)近點(diǎn)和航線、中間進(jìn)近進(jìn)近點(diǎn)和航線、最后進(jìn)近進(jìn)近點(diǎn)和航線、復(fù)飛點(diǎn)和航線、復(fù)飛區(qū)和等待區(qū)。典型終端區(qū)空域結(jié)構(gòu)如圖1所示。

IAF(initial approach fix)為起始進(jìn)近定位點(diǎn)；IF(intermediate fix)為中間定位點(diǎn)；FAF(final approach fix)為最后進(jìn)近定位點(diǎn)；紅色曲線分別表示A、B兩機(jī)場(chǎng)航空器的進(jìn)場(chǎng)航線，藍(lán)色曲線分別表示A、B兩機(jī)場(chǎng)航空器的離場(chǎng)航線

多機(jī)場(chǎng)終端區(qū)空域結(jié)構(gòu)圖如圖2所示，整個(gè)圓柱體表示機(jī)場(chǎng)周圍的管制空域，交叉點(diǎn)表示進(jìn)場(chǎng)航路與離場(chǎng)航路的交叉點(diǎn)。

圖2 多機(jī)場(chǎng)終端區(qū)空域結(jié)構(gòu)圖

協(xié)同排序的主要因素是“協(xié)同”兩字，主要涉及多目標(biāo)之間的協(xié)同，主要包含機(jī)場(chǎng)與機(jī)場(chǎng)之間的相關(guān)性，各個(gè)機(jī)場(chǎng)之間多跑道的相關(guān)性，降落在各個(gè)機(jī)場(chǎng)各個(gè)跑道航空器之間的相關(guān)性。當(dāng)前中國(guó)的空域結(jié)構(gòu)較為復(fù)雜，多機(jī)場(chǎng)終端區(qū)協(xié)同主要有以下特點(diǎn)。

(1)航路航線復(fù)雜管制效率低。航空器從航線進(jìn)入終端區(qū)前就要進(jìn)行管制移交，在這一系列的過程中航空器要經(jīng)過平飛、下降、降速等過程，都要通過管制員的指令來完成，航空器根據(jù)這些指令進(jìn)行飛機(jī)的安全飛行，在繁忙的終端區(qū)中進(jìn)離場(chǎng)航線交錯(cuò)，進(jìn)離場(chǎng)航班較多這就會(huì)造成管制員指揮不過來的現(xiàn)象，管制的效率會(huì)大大降低，稍有不慎會(huì)造成嚴(yán)重的后果。

(2)多機(jī)場(chǎng)以及空域構(gòu)型復(fù)雜。多機(jī)場(chǎng)終端區(qū)中航空器進(jìn)入終端區(qū)后會(huì)飛往各自不同的機(jī)場(chǎng)，機(jī)場(chǎng)的程序、跑道、運(yùn)行方式各有不同，各航空器需要滿足各機(jī)場(chǎng)不同的條件，加上空域結(jié)構(gòu)復(fù)雜航線也時(shí)常交錯(cuò)，進(jìn)入終端區(qū)后限制區(qū)和危險(xiǎn)區(qū)時(shí)常存在使得空域環(huán)境更為復(fù)雜，更加不利于對(duì)航空器進(jìn)行管理。

(3)各場(chǎng)場(chǎng)面容量存在差異導(dǎo)致空域資源分配不均。航空器進(jìn)入終端區(qū)后會(huì)按照順序飛往不同的目的地機(jī)場(chǎng)，大流量機(jī)場(chǎng)和小流量機(jī)場(chǎng)航空器的起降次數(shù)肯定會(huì)存在明顯的差異。按照實(shí)際情況來說，會(huì)安排大流量機(jī)場(chǎng)的飛機(jī)優(yōu)先排序，導(dǎo)致小流量機(jī)場(chǎng)的飛機(jī)處于等待狀態(tài)。這種方式存在很強(qiáng)的不合理性，也會(huì)導(dǎo)致空域資源的不公平分配，提高航班延誤率。

(4)地面保障系統(tǒng)復(fù)雜。由上述可知，在多機(jī)場(chǎng)終端區(qū)中會(huì)存在著不同等級(jí)的機(jī)場(chǎng)，各機(jī)場(chǎng)的地面保障系統(tǒng)也會(huì)存在差異。如航空器飛行中在相同條件下雷達(dá)管制間隔一定比目視飛行間隔要小，這樣也更能提高航空器的效率，如果某機(jī)場(chǎng)的雷達(dá)服務(wù)設(shè)備故障，航空器就會(huì)從雷達(dá)間隔轉(zhuǎn)為目視飛行間隔，增加了航空器之間的間隔，因此也會(huì)降低航空器的運(yùn)行效率。

2 多機(jī)場(chǎng)終端區(qū)進(jìn)場(chǎng)航空器協(xié)同排序模型建立

2.1 進(jìn)場(chǎng)航空器協(xié)同排序模型參數(shù)介紹

建立多機(jī)場(chǎng)終端區(qū)進(jìn)場(chǎng)航空器協(xié)同排序模型，需給出一些符號(hào)定義和參數(shù)變量，如表3所示。

表3 參數(shù)變量和符號(hào)定義

為建立模型還需定義3個(gè)決策變量，變量表達(dá)式如下。

(1)

式(1)中：Xi,j為航空器進(jìn)入走廊口定位點(diǎn)，并且按預(yù)定進(jìn)近航路飛行，當(dāng)該變量為1時(shí)表明航空器i進(jìn)入進(jìn)近航道j，反之為0。

(2)

式(2)中：Yi,j為航空器進(jìn)入入場(chǎng)定位點(diǎn)，并且按預(yù)定航線進(jìn)入所對(duì)應(yīng)的入場(chǎng)定位點(diǎn)，當(dāng)該變量為1時(shí)表明航空器i進(jìn)入入場(chǎng)定位點(diǎn)j，反之為0。

(3)

式(3)中：Zi,j為航空器按計(jì)劃航路飛行到跑到口后，按飛機(jī)預(yù)計(jì)跑道降落，當(dāng)該變量為1時(shí)表明航空器i進(jìn)入跑道入口點(diǎn)j，反之為0。

2.2 進(jìn)場(chǎng)航空器協(xié)同排序模型目標(biāo)函數(shù)

在求解多目標(biāo)的基礎(chǔ)上對(duì)模型進(jìn)行建立，根據(jù)對(duì)多機(jī)場(chǎng)系統(tǒng)運(yùn)行主要問題和空域結(jié)構(gòu)的分析，將從3個(gè)方面來建立目標(biāo)函數(shù)。

從機(jī)場(chǎng)方面，應(yīng)盡量減小所有航班延誤時(shí)間損失，表達(dá)式為

(4)

從管制員負(fù)荷方面，應(yīng)盡量減小管制員負(fù)荷，預(yù)計(jì)到達(dá)時(shí)間最大差值在20%，表達(dá)式為

(5)

從資源平衡方面，應(yīng)盡量減小各機(jī)場(chǎng)之間的平均延誤時(shí)間，表達(dá)式為

(6)

2.3 進(jìn)場(chǎng)航空器協(xié)同排序模型約束條件

航空器只能降落在飛行計(jì)劃中對(duì)應(yīng)的一個(gè)機(jī)場(chǎng)，即

(7)

式(7)為1時(shí)，航空器i的目的機(jī)場(chǎng)為j，反之為0，可以確保式(7)的變量針對(duì)的是多機(jī)場(chǎng)。

航空器在進(jìn)入終端區(qū)走廊口點(diǎn)后，進(jìn)近航路是固定的，航路的終點(diǎn)只對(duì)應(yīng)一個(gè)，最后進(jìn)近定位點(diǎn)也只能對(duì)應(yīng)一個(gè)機(jī)場(chǎng)，即

(8)

式(8)為1時(shí)，航空器i通過進(jìn)近航路的目的機(jī)場(chǎng)為j，反之為0。

航空器在進(jìn)入終端區(qū)走廊口點(diǎn)后，進(jìn)近航路是固定的，進(jìn)近航路只能對(duì)應(yīng)一個(gè)入場(chǎng)定位點(diǎn)與一個(gè)跑道入口點(diǎn)，即

(9)

式(9)為1時(shí)，進(jìn)近航路i服務(wù)入場(chǎng)定位點(diǎn)j與跑道入口點(diǎn)z，反之為0。

民航對(duì)尾流間隔有明確的定義，不同的尾流間隔會(huì)產(chǎn)生不同的進(jìn)場(chǎng)次序與時(shí)間，為確保時(shí)間利用率最高，航空器的類型只屬于一種，即

(10)

航空器在進(jìn)入終端區(qū)走廊口點(diǎn)后，進(jìn)近航路是固定的，航空器只能選擇符合要求的航路，不同型號(hào)降落器跑道限制約束，即

(11)

航空器i的延誤時(shí)間可以用航空器i結(jié)束滑跑的時(shí)間減去航空器i預(yù)計(jì)著陸的時(shí)間來計(jì)算，即

?i∈F, Tfi=|Tdi-TCi|

(12)

絕對(duì)值的意義在于行業(yè)的特殊性，航空器提前到不一定會(huì)提高效率以及降低管制負(fù)荷，也有可能會(huì)增加管制負(fù)荷。

航空器i實(shí)際到達(dá)的時(shí)間，相當(dāng)于結(jié)束滑跑的時(shí)間可以使用航空器進(jìn)入終端區(qū)走廊口點(diǎn)之后的計(jì)劃飛行路線時(shí)間加上航空器通過最后進(jìn)近定位點(diǎn)到跑道頭的時(shí)間加上滑跑時(shí)間來計(jì)算，即

?i∈F, Tdi=Tni+TRi+TMi

(13)

航空器是否延誤，延誤的嚴(yán)重性是通過針對(duì)實(shí)際到達(dá)時(shí)間以及預(yù)計(jì)到達(dá)時(shí)間之差來做比較得到的，即

?i∈F,Ki=|Tsi-THi|>To

(14)

為確保使得終端區(qū)內(nèi)所有管制機(jī)場(chǎng)的平均延誤時(shí)間最低，換句話說總體延誤時(shí)間最低，空間利用率最大，用飛機(jī)場(chǎng)航空器平均延誤時(shí)間來表示，即

(15)

為確保每個(gè)連續(xù)降落的航空器在同一航路有足夠的尾流間隔，通過轉(zhuǎn)換前后兩架航空器進(jìn)入進(jìn)近航道的時(shí)間之差來表示，即

?i∈F,j∈F,i≠j,

(16)

進(jìn)場(chǎng)定位點(diǎn)尾隨間隔以及管制移交間隔為

?i∈F,j∈F,i≠j,

(17)

相同跑道入口點(diǎn)行駛間隔為

?i∈F,j∈F,i≠j,

(18)

降落器進(jìn)場(chǎng)時(shí)間約束為

?i∈F, TAi≤Tni≤TBi

(19)

為了搜索能力更佳，更好地對(duì)該位置進(jìn)行局部搜索，所以添加了滑動(dòng)窗口的概念以及位置互換約束，即

(20)

3 算例仿真

3.1 算法過程

以成都終端區(qū)為例，將收集到的成都雙流國(guó)際機(jī)場(chǎng)與天成都天府國(guó)際機(jī)場(chǎng)某時(shí)間段的航班時(shí)刻表代入多排序模型中，采用結(jié)合模擬退火的NSGA-Ⅱ算法對(duì)數(shù)據(jù)進(jìn)行仿真，對(duì)得出的結(jié)果進(jìn)行分析和對(duì)比。

NSGA-Ⅱ算法能夠高效地遍歷整個(gè)空間內(nèi)的種群，有很強(qiáng)的全局搜索能力，但是針對(duì)航空器排序運(yùn)用了時(shí)間窗口約束，該算法在局部搜索的能力較弱。模擬退火算法相比于遺傳算法有很強(qiáng)的局部搜索能力，但是要求解一個(gè)需要全局搜索的最優(yōu)解，該算法的效率較低，過程較為復(fù)雜，因此在NSGA-Ⅱ算法的框架下引入模擬退火算法，利用兩種算法的優(yōu)勢(shì)相結(jié)合來對(duì)進(jìn)場(chǎng)航空器排序模型進(jìn)行求解。算法過程如下。

步驟1根據(jù)航空器及航空器選擇的航道以及跑道隨機(jī)產(chǎn)生染色體，并生成父代的染色體群nC。

步驟2按照所建立的約束條件和父代篩選情況，過濾掉不符合各項(xiàng)約束條件的個(gè)體，將剩下的個(gè)體重新組成新的種群nC1。

步驟3將新生成種群nC1中的值代入多機(jī)場(chǎng)終端區(qū)排序模型中，計(jì)算出所對(duì)應(yīng)的延誤時(shí)間、管制員負(fù)荷以及資源公平度，對(duì)其進(jìn)行快速非支配排序后形成新種群nC2。

步驟4利用錦標(biāo)賽法對(duì)新生成種群nC2該種群進(jìn)行選擇、交叉、變異等操作，將生成的新種群與初始種群nC1進(jìn)行合并，再次進(jìn)行快速非支配排序生成新種群nC3，然后通過精英策略對(duì)該種群繼續(xù)進(jìn)行篩選得到新種群nC4。

步驟5如果迭代次數(shù)到達(dá)上限，則將得到的解取出作為模擬退火算法的初始解；如果迭代次數(shù)沒有達(dá)到上限，則繼續(xù)按步驟3繼續(xù)迭代。

步驟6將NSGA-Ⅱ算法中最終的解取出作為初始值代入模擬退火算法的步驟1中進(jìn)行計(jì)算。

步驟7在初始溫度下利用蒙特卡洛過程對(duì)初始值進(jìn)行擾動(dòng)選擇抽樣，形成新的解集。

步驟8模擬退火算法隨著迭代次數(shù)的增加溫度逐漸降低，當(dāng)溫度或迭代次數(shù)降到最低時(shí)，將模擬退火算法產(chǎn)生的解集與NSGA-Ⅱ算法產(chǎn)生的種群進(jìn)行合并，如果沒有繼續(xù)迭代循環(huán)。

步驟9將模擬退火算法產(chǎn)生的解集與NSGA-Ⅱ算法產(chǎn)生后的種群進(jìn)行合并，形成新的種群nC5返回步驟3繼續(xù)搜索計(jì)算。

步驟10重復(fù)以上循環(huán)，將NSGA-Ⅱ算法的解集與模擬退火算法產(chǎn)生的解集一次次的合并對(duì)比，直到整個(gè)大循環(huán)結(jié)束。

改進(jìn)的NSGA-Ⅱ算法流程圖如圖3所示。

圖3 改進(jìn)NSGA-Ⅱ算法流程圖

3.2 基于成都終端區(qū)排序算例

成都終端管制區(qū)主要由成都雙流國(guó)際機(jī)場(chǎng)和成都天府國(guó)際國(guó)際機(jī)場(chǎng)構(gòu)成，該終端區(qū)內(nèi)一共有5個(gè)進(jìn)離場(chǎng)走廊口點(diǎn)，由圖4可知，順時(shí)針順序分別為AKDIK、EKOKA、IGNAK、CZH和CDX。在該終端區(qū)內(nèi)有多條進(jìn)離場(chǎng)航線交錯(cuò)，空域結(jié)構(gòu)極其復(fù)雜。

圖4 成都終端區(qū)結(jié)構(gòu)圖

通過對(duì)該終端區(qū)航班時(shí)刻表的收集，在14：00—16：00區(qū)間內(nèi)，共有30架次航班進(jìn)入該終端區(qū)，航班信息如表4所示。

表4 航班信息

經(jīng)過對(duì)成都終端區(qū)14:00—16:00時(shí)間段30架航空器數(shù)據(jù)的分析，再利用NSGA-Ⅱ和NSGA-Ⅱ加模擬退火算法代入所建立的模型中得出優(yōu)化后的延誤時(shí)間目標(biāo)圖、管制員負(fù)荷目標(biāo)圖以及不同機(jī)場(chǎng)延誤平滑指數(shù)圖，可以明顯地看出，對(duì)于NSGA-Ⅱ和NSGA-Ⅱ加模擬退火算法，隨著迭代次數(shù)不斷地增加，三組目標(biāo)函數(shù)得到的解集有明顯的提高。如圖5～圖7所示。

圖5 延誤時(shí)間優(yōu)化圖

圖6 管制員負(fù)荷優(yōu)化圖

圖7 不同機(jī)場(chǎng)延誤平滑指數(shù)優(yōu)化圖

根據(jù)熵權(quán)法，綜合3個(gè)目標(biāo)函數(shù)的影響，將3個(gè)目標(biāo)函數(shù)最優(yōu)解按照優(yōu)先比例進(jìn)行權(quán)重分配，得到最終的三維最優(yōu)解集，根據(jù)pareto所有解集中最前沿的解集得到一檔最優(yōu)權(quán)重解集作為綜合最優(yōu)解集，如圖8所示。

圖8 三目標(biāo)綜合影響分析優(yōu)化圖

針對(duì)30架航空器利用結(jié)合模擬退火的NSGA-Ⅱ算法進(jìn)行求解，由表5可知，利用結(jié)合模擬退火的NSGA-Ⅱ算法后航空器總延誤時(shí)間為5 690 s，較利用先到先服務(wù)調(diào)度算法求解出來的時(shí)間提高了55.2%，較利用NSGA-Ⅱ算法求解出來的時(shí)間提高了28.1%。

表5 結(jié)合模擬退火的NSGA-Ⅱ算法下進(jìn)場(chǎng)航班數(shù)據(jù)

可以看到利用了結(jié)合模擬退火的NSGA-Ⅱ算法后整個(gè)系統(tǒng)又在原先的基礎(chǔ)上更加優(yōu)化了一些，因?yàn)榧尤肓四M退火算法的機(jī)制結(jié)合滑動(dòng)窗口后，更容易進(jìn)行局部搜索使得數(shù)據(jù)更加的精準(zhǔn)。顯然利用全局搜索能力較強(qiáng)的NSGA-Ⅱ算法和局部搜索能力較強(qiáng)的模擬退火算法能夠使航空器排序效率更有效的提升。

4 結(jié)論與展望

(1)結(jié)合實(shí)際機(jī)場(chǎng)終端區(qū)需求，從終端區(qū)定義范圍、空域結(jié)構(gòu)、運(yùn)行特征以及終端區(qū)運(yùn)行的影響因素等多維度綜合分析了多機(jī)場(chǎng)終端區(qū)流量會(huì)趨于飽和的原因，提出能夠提高終端區(qū)運(yùn)行效率的措施，可為空中交通管理人員提供科學(xué)的管制方法。

(2)根據(jù)對(duì)終端區(qū)的分析建立了時(shí)間資源模型和空間資源模型，分析了終端區(qū)內(nèi)主要的幾個(gè)關(guān)鍵流量點(diǎn)以及關(guān)鍵時(shí)間點(diǎn)。依據(jù)航空器進(jìn)近方式以及跑道的運(yùn)行方式建立了全新的以延誤時(shí)間最小、管制員負(fù)荷最小以及平衡空域資源為目標(biāo)的多目標(biāo)進(jìn)場(chǎng)排序模型。但由于目前天府機(jī)場(chǎng)流量較小，因此未來需要在大流量終端區(qū)進(jìn)行實(shí)驗(yàn)驗(yàn)證方法的有效性。

(3)分析了具有較強(qiáng)全局搜索能力的NSGA-Ⅱ算法和具有較強(qiáng)局部搜索能力的模擬退火算法。將模擬退火算法應(yīng)用于NSGA-Ⅱ算法的框架下提出結(jié)合模擬退火的NSGA-Ⅱ算法。該算法不僅具有遺傳算法較強(qiáng)全局搜索的能力，還利用模擬退火算法增加了種群的搜索寬度。但求解多目標(biāo)問題的算法需要在此研究的基礎(chǔ)上進(jìn)一步探索，找到收斂更快、解更為精確的優(yōu)化算法，提升了整體解決的效率以及精確性。