基于NSGA-II 的多機(jī)場終端區(qū)進(jìn)場航班排序研究

張藝峰

DOI：10.16660/j.cnki.1674-098X.2101-5640-1042

摘? 要：多機(jī)場終端區(qū)內(nèi)由于空域結(jié)構(gòu)復(fù)雜，機(jī)場之間相互影響，空中交通流量大，因而經(jīng)常會(huì)發(fā)生航班延誤、飛行沖突、機(jī)場運(yùn)行效率糟糕等問題。本文研究多機(jī)場終端區(qū)的進(jìn)場航班排序，從航空公司和多機(jī)場的利益需求，建立了多目標(biāo)進(jìn)場航班排序模型，采用帶精英策略的非支配排序遺傳算法NSGA-II 進(jìn)行求解，以成都終端區(qū)為例，進(jìn)行仿真實(shí)例驗(yàn)證。結(jié)果表明，與經(jīng)典的先到先服務(wù)（FCFS）方法相比較，該方法能有效改善進(jìn)場航班的延誤問題并使多機(jī)場能平衡的使用空域資源。

關(guān)鍵詞：空中交通管制 多機(jī)場終端區(qū) 進(jìn)場排序 多目標(biāo)優(yōu)化

中圖分類號：V355 ? ? ? ? ?文獻(xiàn)標(biāo)識碼：A? ? ? ? ? ? ? ? ? 文章編號：1674-098X（2021）03（c）-0144-05

Research on Flight Sequencing in Multi-Airport Terminal Area Based on NSGA-II

ZHANG Yifeng

（School of Air Traffic Management， Civil Aviation Flight University of China，? Guanghan， Sichuan Province， 618307 China）

Abstract： Due to the complex airspace structure， the interaction between airports and the large air traffic flow， flight delays， flight conflicts and poor airport operation efficiency often occur in the multi-airport terminal area. This paper studies the incoming flight ranking in the terminal area of multiple airports. According to the benefit requirements of airlines and multiple airports， a multi-objective incoming flight ranking model is established， and the non-dominated ranking genetic algorithm NSGA-II with elite strategy is adopted to solve the model. Taking Chengdu terminal area as an example， the simulation verification is carried out. The results show that， compared with the classical “first come， first served （FCFS）” method， the proposed method can effectively improve the delay problem of incoming flights and make the multi-airport use of airspace resources in a balanced way.

Key Words： Air traffic control; Multi-airport terminal area; Arrival sequencing; Multi-objective optimization

1? 研究背景

隨著國內(nèi)經(jīng)濟(jì)逐漸增長和航空運(yùn)輸?shù)陌l(fā)展需求，新建和改建的機(jī)場越來越多。根據(jù)2019年民航行業(yè)發(fā)展統(tǒng)計(jì)公報(bào)統(tǒng)計(jì)顯示，全國民航運(yùn)輸機(jī)場完成旅客吞吐量13.52億人次，比上年增長6.9%，其中有39個(gè)機(jī)場達(dá)到了旅客吞吐量1000萬人次以上，比上年增加了2個(gè)[1]。目前國內(nèi)有雙機(jī)場的城市有兩個(gè)，分別是上海、北京。成都天府機(jī)場將于2021年建成并運(yùn)行。珠三角、京津冀以及長三角地區(qū)也存在大型聯(lián)合多機(jī)場終端區(qū)。多機(jī)場終端區(qū)內(nèi)，終端空域耦合關(guān)聯(lián)，各機(jī)場相互影響，進(jìn)離場航班共用多個(gè)進(jìn)離場點(diǎn)、進(jìn)離場航段，造成飛行沖突和資源競爭。不能合理利用時(shí)間和空間資源，導(dǎo)致航班延誤、飛行沖突、機(jī)場運(yùn)行效率低下等問題。

關(guān)于進(jìn)場航班的排序問題，國內(nèi)外學(xué)者做了很多的研究。2006年，A.P. Saraf和G.L. Slater提出一種高效的算法，以尾流間隔和航空公司的偏好對飛機(jī)進(jìn)行優(yōu)先排序[2]。2010年，Andrea DAriano等人研究了繁忙機(jī)場下飛機(jī)起降排序問題。提出一個(gè)分支定界算法在短時(shí)間內(nèi)優(yōu)化飛機(jī)起降序列，使飛機(jī)到達(dá)和出發(fā)時(shí)間相對于計(jì)劃時(shí)間的延誤最小[3]。2013年，Hancerliogullari等人針對多跑道上的飛機(jī)排序問題，采用了貪心啟發(fā)式和元啟發(fā)式算法進(jìn)行求解[4]。2013年，張妍，胡明華，張穎，建立了多機(jī)場進(jìn)場航班排序的0-1整數(shù)規(guī)劃模型[5]。在終端區(qū)進(jìn)場調(diào)度問題中，為提高跑道容量，緩解航班延誤，2016年，張軍峰，王菲，葛騰騰提出了基于分支定界法的多跑道動(dòng)態(tài)排序方法，最小化最后一架航班的著陸時(shí)間[6]。2017年，王璐，張小寧，李英，吳輝等人研究了進(jìn)場交通流在多機(jī)場多跑道系統(tǒng)及定位點(diǎn)的排序優(yōu)化問題，利用Epsilon 約束精確算法對該雙目標(biāo)模型求解[7]。2018年王朋提出了一種混合動(dòng)態(tài)規(guī)劃算法，該算法參考了CPS算法和滑動(dòng)窗算法，對進(jìn)場航班進(jìn)行分階段排序，提高了計(jì)算速度[8]。2019年，張海潮針對多跑道航班進(jìn)場排序，提出啟發(fā)因子和期望啟發(fā)因子自適應(yīng)調(diào)整的機(jī)制[9]。2020年，劉繼新，江灝，董欣放，蘭思潔，王浩哲采用協(xié)同決策（CDM）方法，通過NSGA-II算法解決不同的空中交通密度下的進(jìn)場航班協(xié)同排序[10]。同年，張軍峰，游錄寶，楊春葦，胡榮等人為同時(shí)滿足空管、航空公司、機(jī)場和旅客的不同需求，基于非支配排序設(shè)計(jì)了多目標(biāo)帝國競爭算法[11]，更高效地求得Pareto解[11]。

2? 問題描述

多機(jī)場終端區(qū)內(nèi)，空中交通流快速匯聚和發(fā)散，空域結(jié)構(gòu)復(fù)雜，航線眾多。圖1為多機(jī)場終端區(qū)進(jìn)場航班的空域結(jié)構(gòu)。機(jī)場A1和A2的進(jìn)近航線用藍(lán)色和紅色曲線表示，機(jī)場跑道系統(tǒng)用綠色直線表示。G1～G4為機(jī)場A1和A2的部分進(jìn)場點(diǎn)，其中G2和G4為機(jī)場A1和A2的公共進(jìn)場點(diǎn)。多機(jī)場終端區(qū)進(jìn)場航班排序主要包括進(jìn)場點(diǎn)排序和機(jī)場的跑道著陸排序兩部分。所以本文主要考慮的約束限制條件是進(jìn)場點(diǎn)的管制移交間隔，機(jī)場跑道的尾流間隔、同一儀表著陸系統(tǒng)（ILS）航向道和相鄰儀表著陸系統(tǒng)航向道雷達(dá)間隔等各類間隔約束。

3? 模型建立

假設(shè)模型變量：i：機(jī)場，j：跑道，h：進(jìn)場航班，u：進(jìn)場定位點(diǎn)。F：在某段時(shí)間所有的進(jìn)場航班集合;A：終端區(qū)內(nèi)所有機(jī)場集合;R：終端區(qū)內(nèi)所有機(jī)場的進(jìn)場跑道集合;G：終端區(qū)進(jìn)場定位點(diǎn)集合;

Ri：Ri為機(jī)場i的進(jìn)場跑道集合，i∈A;

Fij：在機(jī)場i的跑道j上降落的進(jìn)場航班集合，i∈A，j∈Ri，F(xiàn)ijF;

αijh：第i個(gè)機(jī)場第j條跑道的第h架航班到達(dá)進(jìn)場定位點(diǎn)的可行時(shí)間窗下限;

βijh：第i個(gè)機(jī)場第j條跑道的第h架航班到達(dá)進(jìn)場定位點(diǎn)的可行時(shí)間窗上限;

eijh：第i個(gè)機(jī)場第j條跑道的第h架航班預(yù)計(jì)到達(dá)跑道時(shí)間;

Sijh：第i個(gè)機(jī)場第j條跑道的第h架航班實(shí)際到達(dá)跑道時(shí)間;

thu：航班h通過進(jìn)場定位點(diǎn)u的時(shí)間;

：進(jìn)場定位點(diǎn)u的管制移交間隔標(biāo)準(zhǔn);

：第i個(gè)機(jī)場第j條跑道的第h1和第h2架航班之間的尾流間隔標(biāo)準(zhǔn)。

：第i個(gè)機(jī)場第j條跑道的第h1架航班和第h2架航班之間的同一儀表著陸系統(tǒng)航向道安全間隔標(biāo)準(zhǔn);

：第i個(gè)機(jī)場第j1條跑道的第h1架航班和第j2條跑道的第h2架航班之間的相鄰儀表著陸系統(tǒng)航向道安全間隔標(biāo)準(zhǔn)，當(dāng)兩條跑道采用獨(dú)立進(jìn)近模式時(shí)，=0;

3.1 目標(biāo)函數(shù)

（1）航班延誤總時(shí)間最小。

多機(jī)場終端區(qū)進(jìn)場航班在跑道上的降落次序?yàn)樽罱K輸出隊(duì)列，因此將以航班實(shí)際到達(dá)跑道的時(shí)間與預(yù)計(jì)到達(dá)時(shí)間差值絕對值作為多機(jī)場進(jìn)場航班延誤值進(jìn)行優(yōu)化，即

（2）各機(jī)場平均航班延誤偏差最小。

因?yàn)槎鄼C(jī)場終端區(qū)內(nèi)的每個(gè)機(jī)場有空域資源競爭的關(guān)系，所以該模型的優(yōu)化目標(biāo)應(yīng)該使得各機(jī)場均衡的使用終端區(qū)的空域資源。因此，以各機(jī)場平均航班延誤最小為優(yōu)化目標(biāo)，即

其中，。即δi表示機(jī)場i的平均航班延誤時(shí)間，其中表示機(jī)場i的進(jìn)場航班數(shù)量。

3.2 約束條件

（1）管制移交間隔約束。

每架航空器進(jìn)入終端區(qū)進(jìn)場定位點(diǎn)時(shí)，需要必須滿足管制移交間隔。

其中，為0-1變量，若航班h1和h2能通過定位點(diǎn)u，且航班h1是航班h2的前機(jī)，則為1，否則為0。th1u和th2u是航班h1和h2通過定位點(diǎn)u的時(shí)間，若不能通過，則值為0。

（2）尾流間隔約束。

連續(xù)降落的前后航空器，后機(jī)會(huì)受到前機(jī)的尾流影響。進(jìn)場航班必須滿足尾流間隔約束。

其中，為0-1變量，若同一機(jī)場的同一跑道航班h1先于h2著陸，則為1，否則為0。

（3）多跑道運(yùn)行間隔。

在多跑道系統(tǒng)下，進(jìn)場航班應(yīng)保持同一儀表著陸系統(tǒng)（ILS）航向道和相鄰儀表著陸系統(tǒng)（ILS）航向道雷達(dá)間隔。

其中，為0-1變量，若同一機(jī)場的同一跑道航班h1先于h2著陸，則為1，否則為0。為0-1變量，若第i個(gè)機(jī)場第j1條跑道的第h1架航班先于第j2條跑道的第h2架航班著陸，則為1，反之為0。

（4）著陸時(shí)間窗約束。

為方便對航班進(jìn)場時(shí)間進(jìn)行編碼，我們設(shè)置進(jìn)場航班在機(jī)場著陸時(shí)應(yīng)該滿足在著陸時(shí)間窗內(nèi)。時(shí)間窗下限是根據(jù)目前航班的位置和最短距離航線，計(jì)算得到的最早著陸時(shí)間;時(shí)間窗上限是根據(jù)航班的載油量和飛行性能等數(shù)據(jù)，計(jì)算得到的最晚著陸時(shí)間。

4? 算法設(shè)計(jì)

本文有兩個(gè)優(yōu)化目標(biāo)，即航班延誤總時(shí)間最小和各機(jī)場平均航班延誤偏差最小，因此屬于NP-Hard組合優(yōu)化問題。本文采用帶精英策略的非支配排序遺傳算法NSGA-II 對所建多目標(biāo)優(yōu)化模型進(jìn)行求解。NSGA-II算法可通過快速非支配排序、擁擠距離排序等方法，能使種群具有最優(yōu)性和多樣性，求出使多個(gè)目標(biāo)優(yōu)化的Pareto解。

4.1 算法流程

獲取多機(jī)場終端區(qū)進(jìn)場定位點(diǎn)信息，以及每個(gè)機(jī)場的跑道數(shù)量、運(yùn)行模式、航班計(jì)劃數(shù)據(jù)等信息。根據(jù)這些數(shù)據(jù)獲得航班的計(jì)劃到達(dá)跑道時(shí)間和著陸時(shí)間窗。編碼設(shè)計(jì)所有的進(jìn)場航班著陸時(shí)間窗，隨機(jī)產(chǎn)生初始父代種群。至此，初始化解完成，下面進(jìn)行NSGA-II算法，如圖2所示。

4.2 算法實(shí)現(xiàn)

成都多機(jī)場終端區(qū)，目前有成都雙流機(jī)場和成都天府機(jī)場。因?yàn)槌啥继旄畽C(jī)場暫無航班數(shù)據(jù)，所以隨機(jī)選擇雙流機(jī)場的進(jìn)場航班序列插入到天府機(jī)場航班序列中。表1和表2分別是成都雙流機(jī)場和成都天府機(jī)場的進(jìn)場航班在NSGA-II算法優(yōu)化和FCFS方法對比的結(jié)果。進(jìn)場航班時(shí)刻節(jié)選自成都雙流國際機(jī)場某日的流量高峰期。從表1和表2中可以看出，用FCFS方法得出兩機(jī)場的進(jìn)場航班總延誤是7696s，NSGA-II算法優(yōu)化下總延誤為5231s，延誤時(shí)間減少了32%。兩種算法在兩種方法下各個(gè)機(jī)場的進(jìn)場航班平均延誤差值為60s和41s。因此，該算法對最小化兩個(gè)目標(biāo)，即航班延誤總時(shí)間和各機(jī)場平均航班延誤偏差，優(yōu)化效果顯著。

5? 結(jié)語

通過表1和表2的排序結(jié)果對比，表明本文提出的基于NSGA-II 的多機(jī)場終端區(qū)進(jìn)場航班排序策略是可行的，并且優(yōu)于經(jīng)典的先到先服務(wù)（FCFS）方法，能明顯減少多機(jī)場終端區(qū)的進(jìn)場航班延誤時(shí)間，且基于空域資源的公平性考慮，能減少各個(gè)機(jī)場的平均延誤。

參考文獻(xiàn)

[1] 閔梓.民航局公布2019年民航行業(yè)發(fā)展統(tǒng)計(jì)公報(bào)[N]. 中國航空報(bào)，2020-06-09（007）.

[2] SARAF A P ， SLATER G L . An efficient combinatorial optimization algorithm for optimal scheduling of aircraft arrivals at congested airports[C]// IEEE Aerospace Conference. IEEE， 2006.

[3] D'ARIANO A ， D'URGOLO P ， PACCIARELLI D ， et al. Optimal sequencing of aircrafts take-off and landing at a busy airport[C]// International IEEE Conference on Intelligent Transportation Systems. IEEE， 2010.

[4] HANCERLIOGULLARI， GULSAH， RABADI， GHAITH， AL-SALEM， AMEER H. Greedy algorithms and metaheuristics for a multiple runway combined arrival-departure aircraft sequencing problem[J]. Journal of Air Transport Management， 2013， 32（Complete）：39-48.

[5] 張妍，胡明華，張穎.多機(jī)場終端區(qū)進(jìn)場航班排序模型研究[J].航空計(jì)算技術(shù)，2013，43（3）：20-24.

[6] 張軍峰，王菲，葛騰騰.基于分支定界法的進(jìn)場航空器動(dòng)態(tài)排序與調(diào)度[J].系統(tǒng)仿真學(xué)報(bào)， 2016，28（8）：1909-1914.

[7] 王璐，張小寧，李英，等.多機(jī)場終端區(qū)進(jìn)場交通流優(yōu)化排序方法研究[J].航空計(jì)算技術(shù)，2017，47（1）：31-34.

[8] 王朋.基于混合動(dòng)態(tài)規(guī)劃算法的進(jìn)場航空器優(yōu)化排序[J].航空計(jì)算技術(shù)，2018，48（4）：37-40，45.

[9] 張海潮.西安終端區(qū)進(jìn)場航空器排序模型研究[D].德陽：中國民用航空飛行學(xué)院，2019.

[10] 劉繼新，江灝，董欣放，等.基于空中交通密度的進(jìn)場航班動(dòng)態(tài)協(xié)同排序方法[J].航空學(xué)報(bào)， 2020，41（7）：285-300.

[11] 張軍峰，游錄寶，楊春葦，等.基于多目標(biāo)帝國競爭算法的進(jìn)場排序與調(diào)度[J/OL].航空學(xué)報(bào)：1-13[2020-08-23].http：//kns.cnki.net/kcms/detail/11.1929.V.20200817.1011.002.html.