魏 云 王莉莉

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

0 引 言

隨著我國民航事業(yè)的快速發(fā)展，航班流量的不斷增加，航班延誤問題正嚴(yán)重阻礙著我國民航事業(yè)又快又好的發(fā)展。根據(jù)美國聯(lián)邦航空局的調(diào)查顯示，美國有近84%的航班延誤發(fā)生在機(jī)場場面，尤其是大型機(jī)場。根據(jù)美國航空運(yùn)輸協(xié)會的數(shù)據(jù)顯示，2009年的美國航空延誤費(fèi)用達(dá)100億美元，其中90%由于地面運(yùn)行造成的。而我國國內(nèi)的幾個繁忙機(jī)場，航班延誤問題也十分突出，尤其是在流量高峰時段。雖然國內(nèi)很多大型機(jī)場都是多跑道，但機(jī)場容量的增加沒能帶來機(jī)場交通流量的較大增加，其中很大一部分原因是由于不合理的場面調(diào)度引起的場面擁擠造成的。因此，在有限的機(jī)場資源下，研究機(jī)場場面的調(diào)度優(yōu)化問題，來提高資源利用率，進(jìn)而提高機(jī)場交通流量顯得十分迫切和必要。近年來，國內(nèi)外學(xué)者對此做了不同層次的研究，從不同角度提出了多種解決方案。Gautam Gupta[1]和 Andrea D’Ariano[2]等對進(jìn)離場航班的排序問題進(jìn)行研究，但求出的解實(shí)時性不好。徐肖豪[3]和李志榮[4]等分別利用不同智能算法求解進(jìn)離場航班排序問題，但這些算法都存在求解效率低且容易陷入局部最優(yōu)解問題。H.Balakrishnan[5]等研究了滑行道優(yōu)化運(yùn)行問題，并以真實(shí)機(jī)場仿真驗(yàn)證了其可有效減少航班滑行時間和排隊(duì)序列。董瑩[6]等都分別對機(jī)場滑行道調(diào)度策略進(jìn)行了研究，建立了滑行路徑優(yōu)化模型。劉期建[7]等研究了多跑道機(jī)場的跑道調(diào)度問題并設(shè)計(jì)了多目標(biāo)和分階段的調(diào)度算法。國內(nèi)目前關(guān)于航班推出時刻的研究較少，王潔寧[8]]等基于有色Petri網(wǎng)對航空器推出建模，對航空器推出策略進(jìn)行了研究。

基于以上研究，本文在研究多跑道離場航班排序的基礎(chǔ)上，考慮不同航班從各自停機(jī)位滑向跑道端的滑行時間不同，建立以總的地面等待時間最小為目標(biāo)的離場航班推出時刻模型，設(shè)計(jì)了相應(yīng)的啟發(fā)式算法并進(jìn)行算例仿真。

1 問題描述

在實(shí)際機(jī)場運(yùn)行過程中，如果僅僅根據(jù)航班時刻表的預(yù)計(jì)起飛時間確定航班推出時刻，那不僅會造成整體航班延誤量增大，使得機(jī)場運(yùn)行效率低下，并且，由于場面擁擠帶來的無謂等待時間所造成的航班燃油的消耗，既不經(jīng)濟(jì)也不環(huán)保，因此，研究航班推出時刻，得出合理的航班推出時間，不僅具有理論意義，也有十分重要的現(xiàn)實(shí)意義。

研究航班推出時刻，必須根據(jù)航班預(yù)計(jì)起飛時刻表，結(jié)合前后不同機(jī)型航班所必須滿足的安全間隔的不同，得到最優(yōu)的航班推出序列。根據(jù)國際民航組織（ICAO）規(guī)定，前后不同航班之間必須滿足一定的安全間隔，將安全間隔轉(zhuǎn)化為時間，得到前后各種機(jī)型航班的最小安全時間間隔，如表1所示。

表1 離場航班不同機(jī)型間的最小安全間隔 ijS(單位：min)Tab.1 The minimum safety separation of departure flights among different plane models (unit: min)

2 推出時刻模型建立與分析

假設(shè)離場航班全部在廊橋口等候推出，航班推出過程是指航班從廊橋口推出一直滑至跑道端等待起 飛的整個過程，見網(wǎng)格圖1。

圖1 離場航班推出過程網(wǎng)格圖Fig.1 Launched process grid figure of the departure flights

地面等待時間是指從關(guān)艙門開始直至實(shí)際起飛這段時間。一般情況下，關(guān)艙門時間與預(yù)計(jì)起飛時間是一樣的，故在此使用預(yù)計(jì)起飛時間代替關(guān)艙門時間，即地面等待時間=實(shí)際起飛時間-預(yù)計(jì)起飛時間。假設(shè)某一繁忙機(jī)場高峰時段離場航班架次為N,irE表示航班i在跑道r的預(yù)計(jì)起飛時間,r=1,2,…,R；irA表示航班i在跑道r的實(shí)際起飛時間,r=1,2,…,R；irx表示航班對跑道的變量；ijy表示航班對航班的變量。

決策變量：

則目標(biāo)函數(shù)為:

約束條件為：

式（2）表示每架航班有且只有一條跑道可以起飛；式（3）表示前后航班必須滿足的安全間隔，前后兩架航班i和j在同一條跑道起飛的間隔要大于等于ijS,而前后兩架航班i和j在同一條跑道起飛的間隔要大于等于ijD；式（4）在跑道端等待起飛的航班數(shù)小于該跑道該時刻的起飛容量。

3 啟發(fā)式算法設(shè)計(jì)

根據(jù)航班推出模型和求解思路，設(shè)計(jì)對應(yīng)的啟發(fā)式算法，步驟如下：

Step 1 選擇推出時刻參考值。根據(jù)航班時刻表以及先到先服務(wù)原則，以航班的預(yù)計(jì)起飛時間作為航班的推出時刻參考值，得出航班總的地面等待時間t1；

Step 2 根據(jù)飛機(jī)不同機(jī)型的安全間隔，構(gòu)造前后離場航班的安全間隔矩陣；

Step 3 根據(jù)前后不同機(jī)型航班的組合排列，得到各航班的離場次序，算出不同離場次序的總航班延誤時間，確出航班總延誤時間最少的離場次序r1；

Step 4由于不同停機(jī)位距跑道端的距離不同，導(dǎo)致?？坎煌C(jī)位的各個航班滑至跑道端的滑行時間不同,即各航班的滑行時間數(shù)組，得到最終的航班離場次序r2；

Step 5 若出現(xiàn)推出時刻相同的情況，由于跑道起飛容量的限制，根據(jù)優(yōu)先級原則，將優(yōu)先等級低的航班往后延遲一個推出時刻，得到各航班最終的推出時刻。

4 算例仿真與分析

為了驗(yàn)證模型的準(zhǔn)確性，下面采用成都雙流機(jī)場運(yùn)控部門提供的進(jìn)離場航班數(shù)據(jù)進(jìn)行仿真。成都雙流機(jī)場為多跑道設(shè)置，設(shè)跑道數(shù)R=2,由于還有進(jìn)場航班，故起飛容量取M=2。由于在實(shí)際運(yùn)行過程中，前后兩架在不同跑道起飛的航班，往往使用同一安全間隔ijS。因此，本文算例仿真采用的安全間隔都是ijS，即ijD=ijS。選取某15分鐘內(nèi)的10架起飛航班，根據(jù)國際民航組織（ICAO）的規(guī)定,將飛機(jī)按機(jī)型分為重型（H）,中型(L)，輕型（S）三類,且相鄰兩架不同機(jī)型航班的最小尾流安全間隔標(biāo)準(zhǔn)，可用3×3矩陣表示：

矩陣中的單位為min；行為前機(jī)i，列為后機(jī)j。

每架班延誤如公式（1）所示。美國聯(lián)邦航空管理局（FAA）對無障礙滑行時間是這樣定義的：在最理想運(yùn)行條件下，航空器在沒有受到擁擠、氣象和其他造成延誤等因素影響時從停機(jī)位推出到起飛這一過程的滑行時間。故假設(shè)10架航班的起飛跑道,預(yù)計(jì)起飛時間以及各航班滑至跑道端的無障礙滑行時間已知，如表2所示：

表2 航班預(yù)計(jì)起飛時間與跑道以及滑行時間（單位：min）Tab.2 Flight departure time and the runway and sliding time (unit: min)

仿真的具體結(jié)果，見表3，表4。

表3 利用FAFS算法計(jì)算的仿真結(jié)果（單位：min）Tab.3 Simulation results calculated with FAFS algorithm (unit: min)

表4 利用啟發(fā)式算法計(jì)算的仿真結(jié)果Tab.4 Simulation results calculated with heuristic algorithm

本文用 FAFS算法求得的航班總的地面等待時間為19.5 min,而采用啟發(fā)式算法求得的航班總的地面等待時間為11.5 min，相比先到先服務(wù)原則（FAFS算法），采用該算法對離場航班的推出時刻進(jìn)行優(yōu)化，使得航班地面總的等待時間減少了近41%，可以明顯的減少航班地面等待時間，同時跑道利用率提高了30%。

5 結(jié)束語

本文研究了繁忙多跑道機(jī)場的離場航班推出時刻問題，在滿足安全間隔和不同滑行時間的約束條件下，設(shè)計(jì)推出時刻啟發(fā)式算法，求解出離場航班的最優(yōu)推出時刻，通過matlab仿真，對該算法進(jìn)行驗(yàn)證，結(jié)果表明，針對機(jī)場短時間小流量的離場航班，本文建立的模型符合機(jī)場實(shí)際，算法可行，為以后對航班推出時刻的進(jìn)一步研究作了一定的理論探討。

[1] Gautam Gupta, Waqar Malik, Yoon C. Jung. A mixed integer linear program for airport departure scheduling[C]//Hilton Head, South Carolina: Proc. of 9th American Institute of Aeronautics and Astronautics，Aviation Technology Integration and Operations Conference (ATIO), 2009.

[2] Andrea D’Ariano. Paolo D’Urgolo, Dario Pacciarellietal.Optimal sequencing of aircrafts take-off and landing at a busy airport[C]//Madeira Island, Portugal: Proc.of 2010 13thInternational IEEE, Annual Conference on Intelligent Transportation Systems, 2010.

[3] 徐肖豪，姚 源. 遺傳算法在終端區(qū)排序中的應(yīng)用[J]. 交通運(yùn)輸工程學(xué)報, 2004,4(3): 121-126.

[4] 李志榮，張兆寧. 基于蟻群算法的航班著陸排序[J].交通運(yùn)輸工程與信息學(xué)報，2006,4(2): 66-19.

[5] Simaiakis I.，Balakrishnan H． Queuing models of airport departure processes for emissions reduction[C].Proc. of American Institute of Aeronautics and Astronautics Guidance，Navigation and Control Conference，2009.

[6] 董 瑩，安 然. 機(jī)場航空器地面滑行時間優(yōu)化研究[J]．交通運(yùn)輸系統(tǒng)工程與信息，2011, 11(5):141-146.

[7] 劉期建．多目標(biāo)分階段的跑道調(diào)度計(jì)劃算法研究[D].成都: 電子科技大學(xué)，2009．

[8] 王潔寧, 薛 鵬, 徐肖豪. 基于 CPN 的 Agent建模及其用于航空器推出的分析[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2012, 22(1): 187-190.