特殊情況下的進(jìn)離場航班排序問題研究

王莉莉，顧秋麗

（中國民航大學(xué) 空中交通管理學(xué)院，天津 300300）

1 引言

隨著我國經(jīng)濟(jì)的快速發(fā)展，空中交通流量不斷增加，使得空域資源緊缺，嚴(yán)重影響航班的正點(diǎn)到達(dá).因此優(yōu)化航班的起降順序及跑道分配問題是提高空域利用率的有效途徑，也是空中交通流量管理研究的主要問題.

目前，解決航班排序問題(Aircraft Sequencing Problem,ASP)最常用的方法是采用先到先服務(wù)（First Come First Service，F(xiàn)CFS）方法.國外學(xué)者對航班排序問題（ASP）研究如下.2003年，Kari Andersson[1]根據(jù)NASA提出的改進(jìn)空中交通流量的決策支持工具-協(xié)同進(jìn)場規(guī)劃（CAP）進(jìn)行了優(yōu)化方法分析，并驗(yàn)證了進(jìn)場排序程序能夠改善航空運(yùn)輸系統(tǒng).2006年，Aditya P.Saraf[2]提出了一種對擁擠機(jī)場進(jìn)場航班的組合優(yōu)化方法，但其未考慮多跑道航班的優(yōu)化分配問題，人為地規(guī)定了航班的降落跑道.2009年，Gautam Gupta[3]采用了一種混合整數(shù)線性規(guī)劃模型求解離場航班的排序問題，但由于受限制約束問題的影響，求解模型的實(shí)時性不好.2010年，Andrea D’Ariano[4]將繁忙機(jī)場的進(jìn)離場航班排序問題比作旅行商問題，并采用啟發(fā)式算法進(jìn)行求解，仿真證明算法只可以快速找到可行解.國內(nèi)也有許多學(xué)者對ASP問題進(jìn)行了研究.楊軍利[5]等把飛機(jī)的排序問題等價于帶有準(zhǔn)備好時間的漸增周游店員問題,采用了一種近似算法，但是近似程度較低，很難求出最優(yōu)解.程曉航[6]運(yùn)用遺傳算法求解了單跑道情況下到達(dá)航班的排序問題.王飛[7]提出了混合人工魚群算法并將其應(yīng)用在單跑道和多跑道著陸航班的排序中，該算法有效地減少了航班的延誤，但當(dāng)航班數(shù)量較多時其求解效率較差.

具有平行跑道的機(jī)場終端區(qū)進(jìn)離場平面結(jié)構(gòu)示意圖如圖1所示.進(jìn)離場航班按照儀表進(jìn)場/離場程序從不同的航路進(jìn)入/離開終端區(qū)準(zhǔn)備著陸/起飛，在進(jìn)/離場航線交叉點(diǎn)處按照著陸/起飛時間先后順序排成隊(duì)列.

由圖1可知,進(jìn)離場航班所經(jīng)過的終端區(qū)空域按起始調(diào)度界限與終止調(diào)度界限的定義可以分為三個部分.對于進(jìn)場航班，起始調(diào)度界限是一個空間界限，是航班進(jìn)入進(jìn)近管制區(qū)的界限，終止調(diào)度界限則根據(jù)特定的距離著陸的時間來確定，終止調(diào)度界限也叫動結(jié)區(qū)界限.然而對于離場航班，起始調(diào)度界限則為開始在停機(jī)坪做起飛準(zhǔn)備,終止調(diào)度界限則為航班已進(jìn)入跑道起飛.起始調(diào)度界限與終止調(diào)度界限間的時域即為航班動態(tài)排序區(qū)，在這兩個界限之間用排序算法根據(jù)航班的預(yù)計(jì)起飛時間、預(yù)計(jì)降落時間、航班類型等對航班的起飛與降落順序進(jìn)行排序及分配跑道.

圖1 機(jī)場終端區(qū)平面結(jié)構(gòu)示意圖Fig.1 Diagram of an airport terminal area

空中交通管制的目的是為了保證航班的安全，使航班與航班之間具有一定的安全間隔.但目前的空中交通管制主要是基于距離間隔保證航班飛行的安全.為了保證流量管理的精確性，因此本文引入了時基的概念，把飛機(jī)的距離間隔轉(zhuǎn)化為時間間隔.根據(jù)白云機(jī)場進(jìn)離場距離規(guī)定轉(zhuǎn)化為最小安全時間間隔，如表1所示.

本文考慮了機(jī)場實(shí)際運(yùn)行中貨機(jī)只能在某條固定跑道起降的情況，建立了進(jìn)離場航班的排序模型.由于該問題是典型的TSP組合優(yōu)化問題，同時也是難解的NP完全問題，采用常規(guī)的求解算法很難滿足航班排序?qū)崟r性的要求.本文設(shè)計(jì)了基于雙重編碼的遺傳算法對平行跑道進(jìn)離場航班的排序模型進(jìn)行求解.求解時用一對染色體將航班進(jìn)離場序號與跑道號對應(yīng)起來同時優(yōu)化跑道的分配與進(jìn)離場航班的起降順序，并采用了排列編碼法區(qū)分了載客與載貨航班的不同，同時也采用了精英策略及進(jìn)化逆轉(zhuǎn)操作，大大提高了遺傳算法的求解效率.最后通過仿真驗(yàn)證其可行性.

表1 不同機(jī)型間的尾流最小間隔（Si j）Table 1 Minimum wake turbulence separation between different aircraft

本文考慮了機(jī)場實(shí)際運(yùn)行中貨機(jī)只能在某條固定跑道起降的情況，建立了進(jìn)離場航班的排序模型.由于該問題是典型的TSP組合優(yōu)化問題，同時也是難解的NP完全問題，采用常規(guī)的求解算法很難滿足航班排序?qū)崟r性的要求.本文設(shè)計(jì)了基于雙重編碼的遺傳算法對平行跑道進(jìn)離場航班的排序模型進(jìn)行求解.求解時用一對染色體將航班進(jìn)離場序號與跑道號對應(yīng)起來同時優(yōu)化跑道的分配與進(jìn)離場航班的起降順序，并采用了排列編碼法區(qū)分了載客與載貨航班的不同，同時也采用了精英策略及進(jìn)化逆轉(zhuǎn)操作，大大提高了遺傳算法的求解效率.最后通過仿真驗(yàn)證其可行性.

2 模型算法

2.1 特殊情況下進(jìn)離場航班排序模型的建立

假設(shè)某一具有多跑道繁忙機(jī)場的終端區(qū)航班架數(shù)為N，包括載客航班數(shù)Nk，載貨航班數(shù)Nh，并且 Nk∪Nh=N,Nk∩Nh=Φ ，表示為 f=(1,2,...,Nk,...,N)；設(shè)航班i在跑道r的預(yù)計(jì)降落時間為ETi,實(shí)際降落時間為ATi；r=(1,2,...,R)為機(jī)場跑道數(shù)目；g(i)表示到達(dá)航班隊(duì)列優(yōu)化后第i個位置的航班；xir為航班對跑道的變量，yij為航班對航班的變量.

定義決策變量：

目標(biāo)函數(shù)以總的延遲時間最小為原則.目標(biāo)函數(shù)為

考慮到排序過程中的各種限制，給出模型的約束條件如下：

式(2)說明每架載客航班都被分配一條跑道降落（起飛）且每架載客航班只能在一條跑道上降落（起飛）；式(3)說明每架載貨航班都被分配在某一條確定的跑道起降且每架載貨航班只能在一條跑道上起降；考慮航班之間的尾流間隔要求，式(4)說明前后兩架航班i和 j在同一跑道上降落（起飛）時之間的間隔要大于等于Sij，前后兩架航班i和 j在不同跑道上降落(起飛)時之間的間隔要大于等于Dij；式(5)考慮飛機(jī)性能、管制員的負(fù)荷及航班先到先服務(wù)的公平性原則，引入了最大移動位置數(shù)（Maximum Position Shifting,MPS），即以FCFS航班順序?yàn)榛鶞?zhǔn)，航班向前或向后移動的最大位置數(shù)為MPS.由以上可知yij=yji,i,j=1,2,...,N;i≠j.

令 Tdelay=ATi-ETi，當(dāng)航班 i的 ATi≤ETi時，令 Tdelay=0，既無延遲.當(dāng)航班 i的 ATi＞ETi時，Tdelay=ATi-ETi.若前后兩架航班使用同一條跑道時（i-1為i的前一架航班），則航班的實(shí)際到達(dá)（起飛）時間為ATi=max(ATi-1+Si,i-1,ETi)；若前后兩架航班使用不同跑道時，則航班的實(shí)際到達(dá)（起飛）時間為ATi=max(ATi-1+Di,i-1,ETi).

2.2 遺傳算法的設(shè)計(jì)

(1)編碼.

為了與平行多跑道運(yùn)行方案相匹配，本文采用的編碼方式為二重結(jié)構(gòu)編碼.每個染色體由上行碼和下行碼組成.上行碼表示進(jìn)離場航班的起降次序,下行碼表示進(jìn)離場航班起降的跑道號.上行碼采用排列編碼方式進(jìn)行編碼，排列編碼也叫序列編碼，是針對一些特殊問題的特定編碼方式.如航班序列中有兩種航班類型，分別為載客航班和載貨航班，則將某個終端區(qū)內(nèi)的進(jìn)離場航班按初始進(jìn)離場時刻表的時間順序進(jìn)行編碼，并在同一編碼中同時包含兩種類型的進(jìn)離場航班.如載客航班的個數(shù)為30，載貨航班的個數(shù)為6，則編碼為1，2，3，31，4，33，5，...,30，36.編碼中小于等于30的個體代表載客的進(jìn)離場航班，大于30的個體代表載貨的進(jìn)離場航班，以兩條跑道、36架航班為例，構(gòu)成如表2所示的染色體.

表2 二重結(jié)構(gòu)編碼方式Table 2 The way of dual coding

(2)種群的初始化.

在完成染色體編碼以后，必須產(chǎn)生一個初始種群作為起始解,本算法使用了一定比例的FCFS序列，這樣保證了在最壞情況下，優(yōu)化結(jié)果好于FCFS序列.

(3)適應(yīng)度函數(shù).

適應(yīng)度函數(shù)表示為

(4）選擇操作.

選擇操作即從種群中以一定概率選擇個體添加到新群體中，個體被選中的概率與其適應(yīng)度值有關(guān)，個體適應(yīng)度值越大，被選中的概率也越大.

(5）交叉操作.

以部分映射雜交的方式確定交叉操作的上行碼,子個體的下行碼采用隨機(jī)方式進(jìn)行交叉.但對于載貨航班,如果起降的跑道號與實(shí)際要求相符，則該個體不進(jìn)行交叉操作.

(6）變異操作.

變異操作采取在父代染色體中隨機(jī)選取兩個位置并將其對換進(jìn)行變異.但對于載貨航班，如果起降的跑道號與實(shí)際要求相符，則該個體不進(jìn)行變異.

(7）進(jìn)化逆轉(zhuǎn)操作.

為提高遺傳算法局部的搜索能力，在選擇、交叉、變異之后采用了連續(xù)多次的進(jìn)化逆轉(zhuǎn)操作.這里的“進(jìn)化”是指逆轉(zhuǎn)算子的單方向性，即只有經(jīng)過逆轉(zhuǎn)后，適應(yīng)度值有提高的個體才被留下來，否則逆轉(zhuǎn)無效.并且逆轉(zhuǎn)操作只在航班允許MPS范圍內(nèi)進(jìn)行.

進(jìn)化逆轉(zhuǎn)操作采取在父代染色中隨機(jī)選取兩個位置，進(jìn)行逆轉(zhuǎn).如選取位置四和位置七進(jìn)行逆轉(zhuǎn)操作，但對于載貨航班并且其起降的跑道號與實(shí)際要求相符的個體不進(jìn)行逆轉(zhuǎn).

進(jìn)化逆轉(zhuǎn)后：

3 算法仿真

根據(jù)《中國民用航空總局令（第123號）平行跑道同時儀表運(yùn)行管理規(guī)定》第十二條所述，平行跑道同時儀表運(yùn)行按照第七條所述的四種運(yùn)行模式（獨(dú)立平行儀表進(jìn)近、相關(guān)平行儀表進(jìn)近、獨(dú)立平行離場、隔離平行運(yùn)行等四種模式）的不同組合，也可以分為半混合運(yùn)行和混合運(yùn)行.本文根據(jù)廣州白云機(jī)場的運(yùn)行情況，令跑道數(shù)r=2,平行跑道使用的方式為混合運(yùn)行的模式.以某時段36架連續(xù)航班流為例對算法進(jìn)行了驗(yàn)證，其中航班序號為1-30的航班為正常的載客航班，對起飛和降落的跑道沒有要求；航班序號31-36號航班為載貨航班，由于實(shí)際運(yùn)行的需要，他們只能在規(guī)定的跑道上進(jìn)行起降，本文令載貨航班只能在02號跑道上起飛與降落.本文遺傳算法的種群大小為100，最大進(jìn)化代數(shù)為50，航班交叉概率 pcf=0.9,跑道交叉概率 pcr=0.9，航班變異概率 pcf=0.05，跑道變異概率 pcr=0.05，MPS=3.

考慮機(jī)場實(shí)際運(yùn)行中對載貨航班起降跑道有特殊要求的進(jìn)離場航班的遺傳算法的收斂過程如圖2所示.本文的遺傳算法采用了進(jìn)化逆轉(zhuǎn)操作，改善了遺傳算法的局部搜索能力，加快了收斂速度.經(jīng)本文算法優(yōu)化后，對跑道有規(guī)定的31-36號載貨進(jìn)離場航班都在規(guī)定的02號跑道上進(jìn)行了起降，優(yōu)化后的排序結(jié)果與FCFS算法的結(jié)果對比如圖3所示.優(yōu)化后的航班總延誤時間為1912秒，F(xiàn)CFS算法總延誤時間為2468秒，比較結(jié)果如圖4所示.由仿真結(jié)果可知，本文所建立的模型和算法能夠有效解決實(shí)際運(yùn)行中對載貨航班的跑道限制要求，31-36號進(jìn)離場航班中不符合跑道要求的航班在優(yōu)化后都在規(guī)定的跑道上進(jìn)行了起降，并且以總的延遲時間為目標(biāo)對1-36號航班的起降順序進(jìn)行了合理地優(yōu)化，大大減少航班延誤的總時間，提高了空中交通管制效率.

圖2 遺傳算法收斂過程Fig.2 The convergence process of GA

圖3 GA與FCFS排序結(jié)果比較Fig.3 Comparison of FCFS and GA algorithm’s sequencing

圖4 FCFS與GA延誤時間對比Fig.4 Comparison of FCFS and GA algorithm’s delay time

4 研究結(jié)論

本文討論了終端區(qū)進(jìn)離場航班的排序問題，并同時考慮了機(jī)場實(shí)際運(yùn)行中對載貨航班起降跑道的特殊限制，建立了載貨航班只能在規(guī)定跑道上進(jìn)行起降的進(jìn)離場航班的排序模型，并設(shè)計(jì)了雙重編碼的遺傳算法進(jìn)行求解，合理地安排了進(jìn)離場航班的起降順序，以及同時為進(jìn)離場航班分配跑道.遺傳算法中采用了精英策略及進(jìn)化逆轉(zhuǎn)操作，使其搜索最優(yōu)解的能力更強(qiáng),能夠快速尋找到所需的最優(yōu)解.仿真結(jié)果證明了模型和算法的有效性，以36架連續(xù)航班流為例，本文所設(shè)計(jì)的遺傳算法與先到先服務(wù)算法相比，能有效地減少航班延誤總時間556 s，并且實(shí)現(xiàn)了特殊航班只能在規(guī)定跑道起降的要求，具有實(shí)際意義，提高了空中交通管制效率，能夠在一定程度上緩解繁忙機(jī)場終端區(qū)的擁擠問題.

[1]Kari Andersson,William Hall,Stephen Atkins,et al.Opti?mization-based analysis of collaborative airport arrival planning[J].Transportation Science,2003,37(4):422-433.

[2]Aditya P Saraf,Gary L Slater.An efficient combinatorial optimization algorithm for optimal scheduling of aircraft arrivals at congested airports[C]//Aerospace Conference,IEEE,2006.

[3]Gautam Gupta,Waqar Malik,Yoon C Jung.A Mixed in?teger linear program for airport departure scheduling[C]//Hilton Head,South Carolina:9th AIAA Aviation Technol?ogy,Integration,and Operations Conference(ATIO),2009.

[4]Andrea D’Ariano,Paolo D’Urgolo,Dario Pacciarelli,et al.Optimal sequencing of aircrafts take-off and landing at a busy airport[C]//Madeira Island,Portugal:201013th International IEEE,Annual Conference on Intelligent Transportation Systems,2010.

[5]楊軍利,方群,向小軍.終端區(qū)飛機(jī)排序的規(guī)劃模型和算法研究[J].飛行力學(xué)，2005,23（2）：77-80.[YANG J L,FANG Q,XIANG X J.Research on the scheduling model and algorithm for aircraft sequencing problem in TMA[J].Flight Dynamics,2005,23（2）：77-80.]

[6]程曉航，薛惠鋒，洪鼎松，等.進(jìn)港飛機(jī)調(diào)度的精華自適應(yīng)遺傳算法設(shè)計(jì)[J].交通與計(jì)算機(jī),2006,24(6):91-94.[CHENG XH,XUE HF,HONG DS,et al.Design of elit?ist adaptive genetic algorithm in arrival aircrafts sched?uling[J].Transport and Computer,2006,24(6):91-94.]

[7]王飛,徐肖豪.終端區(qū)飛機(jī)排序的混合人工魚群算法[J].交通運(yùn)輸工程學(xué)報,2008,8(3):68-72.[WANG F,X U XH.Mixed artificial fish school algorithm of aircraft se?quencing in terminal area[J].Journal of Traffic and Transportation Engineering,2008,8(3):68-72.]