王莉莉, 張瀟瀟

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

?

多機場協(xié)同決策進(jìn)離場航班排序模型及算法研究

王莉莉, 張瀟瀟

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

摘要:多機場終端區(qū)內(nèi)的航線網(wǎng)絡(luò)錯綜復(fù)雜,來往同一方向的航班會共用一個交接點,航班的起飛降落不僅要考慮各方向航空器的運行間隔和各受限單元容量的限制,還需著重考慮交接點的間隔限制?；诮K端區(qū)多機場多元受限情況,建立了終端區(qū)多機場協(xié)同決策進(jìn)離場航班排序模型,并設(shè)計了遞歸遺傳算法。首先以各機場為單位采用遺傳算法進(jìn)行航班排序,得出各機場延誤時間最小的排隊序列,之后將各機場航班在交接點處進(jìn)行聚類并排序,再將各交接點的排隊序列反推回各機場,運用遞歸算法不斷優(yōu)化各機場的航班序列,在保證安全運行的基礎(chǔ)上,最終得出各機場的航班排隊序列。仿真結(jié)果表明，該算法優(yōu)化效果顯著,各機場的總延誤時間減少了48.2%,可有效緩解多機場航班延誤。

關(guān)鍵詞:多機場終端區(qū); 多元受限; 進(jìn)離場排序; 遺傳算法

0引言

終端區(qū)一般指地理位置較近的幾個機場,其航班運行相互影響,航線網(wǎng)絡(luò)更加復(fù)雜,存在很強的關(guān)聯(lián)性。多機場協(xié)同決策方法逐漸成為提高繁忙終端區(qū)運行效率的有效方法。針對進(jìn)離場排序和多機場協(xié)同決策問題,國內(nèi)學(xué)者已經(jīng)進(jìn)行了研究[1-8],但在流量管理系統(tǒng)運行中發(fā)現(xiàn),對終端區(qū)邊界的進(jìn)離場交接點處的協(xié)同沒有得到足夠重視,目前的研究多是將進(jìn)場航班和離場航班分開考慮,沒有考慮進(jìn)離場航班間的協(xié)同問題。

本文基于終端區(qū)多機場多元受限情況,建立了以最小化延誤時間為目標(biāo)模型,并著重考慮交接點限制的設(shè)計算法,為進(jìn)離場航班分配最優(yōu)的目標(biāo)降落/起飛時間,達(dá)到使總體延誤時間最少的目的。

1問題的提出

如圖1所示,多機場終端區(qū)內(nèi)同一個機場的進(jìn)離場航線會有交叉,進(jìn)離場航班存在沖突,不同機場的航班若進(jìn)出同一個方向會存在共用交接點的現(xiàn)象,使得航班的起飛降落要考慮跑道、進(jìn)離場定位點、進(jìn)離場航線匯合點、扇區(qū)容量的限制,還要著重考慮交接點處的限制問題。

圖1　多機場終端區(qū)示意圖Fig.1　Diagram of multi-airport terminal area

2多機場進(jìn)離場航班排序模型

2.1模型假設(shè)

假設(shè)各機場航班的預(yù)計起飛時間和預(yù)計降落時間都已知;不考慮機型的差異,各定位點、進(jìn)離場航線匯合點和交接點與機場之間的飛行時間可以根據(jù)距離和速度算出;各航班所使用的進(jìn)離場航線在預(yù)優(yōu)化時間段內(nèi)可事先給出;各航班所經(jīng)過的定位點、進(jìn)離場航線匯合點和交接點事先都可通過飛行計劃得知。

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

目標(biāo)函數(shù)為最小化總延誤時間:

(1)

2.3約束條件

2.3.1跑道容量約束

(2)

式中:Cwri(t)為t時段內(nèi)機場r跑道wri的容量;Wr為機場r的跑道的集合,Wr={1,2,…,nrw}。

2.3.2進(jìn)場定位點容量約束

(3)

式中:Cjri(t)為t時段內(nèi)機場r進(jìn)場定位點jri的容量;Jr為機場r的所有進(jìn)場定位點的集合,Jr={1,2,…,nrj}。

2.3.3離場定位點容量約束

(4)

式中:Clri(t)為t時段內(nèi)機場r離場定位點lri的容量;Lr為機場r的所有離場定位點的集合,Lr={1,2,…,nrl}。

2.3.4進(jìn)離場航線匯合點容量約束

(5)

式中:Chri(t)為t時段內(nèi)機場r進(jìn)離場航線匯合點hri的容量;Hr為機場r的所有進(jìn)離場航線匯合點集合Hr={1,2,…,nrh}。

2.3.5交接點容量約束

(6)

式中:Cgi(t)為t時段內(nèi)交接點gi的容量;G為多機場終端區(qū)中所有交接點的集合,G={1,2,…,ng};P(t)為t時間段內(nèi)多機場所有航班集合,P(t)={1,2,…,n+m}。

2.3.6扇區(qū)容量約束

(7)

式中:Csi(t)為t時段內(nèi)扇區(qū)si的容量;S為進(jìn)離場航線穿越的扇區(qū),S={1,2,…,ns}。

2.3.7進(jìn)/離場定位點間隔限制

(8)

(9)

2.3.8進(jìn)離場航線匯合點間隔限制

(10)

2.3.9交接點間隔限制

(11)

2.3.10延誤時間限制

(12)

(13)

式中:γa和γd為進(jìn)場和離場航班可接受的最大延誤時間;R為所有機場集合,R={1,2,…,nr}

綜上所述,模型在多機場終端區(qū)多元受限的基礎(chǔ)上,尋求總延誤時間最少的進(jìn)離場排序方案。

3算法設(shè)計

本文根據(jù)多機場運行情況,提出一種遞歸遺傳算法(RG),具體流程如圖2所示。

圖2　RG算法流程圖Fig.2　Flow chart of RG

遺傳算法的具體流程為:以各單機場為單位,根據(jù)進(jìn)離場航班的預(yù)計降落/起飛時間、航班經(jīng)過進(jìn)離場定位點和進(jìn)離場航線匯合點的間隔限制、各受限單元的容量限制,采用遺傳算法分別對各機場航班進(jìn)行第一次排序。

為了能夠表示航班與跑道的對應(yīng)關(guān)系,采用了二重結(jié)構(gòu)編碼。每個染色體由上行碼和下行碼組成,航班的降落/起飛順序用上行碼表示,降落/起飛的跑道號用下行碼表示。如表1所示,0～4表示進(jìn)場航班,5～9表示離場航班,跑道號為0和1,代表兩條跑道(如果某機場是單跑道,那么跑道號都用同樣的數(shù)字表示)。

表1　二重結(jié)構(gòu)編碼方式

在種群的初始化過程中,并不是完全隨機產(chǎn)生所有染色體,而是使用一定比例的FCFS序列,可以使遺傳算法的優(yōu)化結(jié)果不低于FCFS策略。

每個機場的適應(yīng)度函數(shù)為:

(14)

通過選擇操作,個體適應(yīng)度值越大,被選中的概率也越大;交叉采用單點交叉方式[9];變異操作采用隨機選擇染色體上的兩個位置進(jìn)行交換。最終達(dá)到最大進(jìn)化代數(shù),形成各機場初始序列。

4仿真算例

以珠三角終端區(qū)為例進(jìn)行仿真計算,包含深圳、珠海和澳門機場。

4.1首先確定約束條件中的參數(shù)

各點的安全間隔用最小尾流間隔時間來表示,最小尾流間隔與機型組合有關(guān),除前機是重、中型飛機,后機是輕型飛機最小尾流間隔時間3 min外,其余機型最小尾流間隔時間為2 min。

容量限制:深圳機場最大容量為16架/15 min;珠海機場最大容量為8架/15 min;澳門機場最大容量為8架/15 min;機場進(jìn)場定位點和離場定位點處最大容量為10架/15 min,進(jìn)離場航線匯合點和交接點最大容量為7架/15 min。

預(yù)優(yōu)化時間段:08:00～09:00。

4.2仿真計算

以三個機場45架航班(各15架)為例進(jìn)行仿真,種群大小50,最大進(jìn)化代數(shù)50,跑道變異概率0.05,航班交叉概率0.9,最大可接受延誤時間為:γa=20 min,γd=25 min。三個機場的初始交通需求數(shù)據(jù)見表2。表中:狀態(tài)D代表航班狀態(tài)為離場;A代表航班狀態(tài)為進(jìn)場;H代表重型機;M代表中型機;L代表輕型機。

表2　多機場初始交通需求

使用MATLAB進(jìn)行仿真,三個機場的進(jìn)離場序列進(jìn)化至23代左右時趨于收斂。FCFS算法計算得出的航班序列與本文RG算法優(yōu)化后的航班序列對比如表3所示?？梢钥闯?本文提出的RG算法和FCFS算法相比,深圳機場的延誤時間由198 min減少為92 min,珠海機場的延誤時間由254 min減少為145 min,澳門機場的延誤時間由306 min減少為156 min,三個機場總延誤時間由758 min減少為393 min,航班平均延誤時間由16.8 min減少為8.7 min,減少了48.2%。

表3　兩種算法優(yōu)化序列對比

5結(jié)束語

本文分析了終端區(qū)多機場存在的沖突問題,綜合考慮機型、安全間隔和容量等因素,以最小化總延誤時間為目標(biāo),建立了終端區(qū)多機場協(xié)同決策排序模型,并設(shè)計了遞歸遺傳算法,充分考慮了多機場航班共用交接點這一因素,既避免了各機場航班在交接點處的沖突,也優(yōu)化了各機場的航班序列。借鑒協(xié)同決策這一理念,提高了多機場的空管運行效率。如果將模型擴展到航路和航路交叉點構(gòu)成的網(wǎng)絡(luò)中,能更大范圍地改進(jìn)空中交通網(wǎng)絡(luò)的運行效率。

參考文獻(xiàn)：

[1]胡明華,蘇蘭根.多機場地面等待問題模型研究[J].南京航空航天大學(xué)學(xué)報,2000,32(5):586-590.

[2]張兆寧,王莉莉.基于蟻群算法的多跑道著陸飛機隊列排序研究[C]//Proceedings of the 7th World Congress on Intelligent Control and Automation.Chongqing,China,2008:1935-1939.

[3]張洪海,胡明華.多機場終端區(qū)容流利用和分配建模與仿真[J].系統(tǒng)仿真學(xué)報, 2009,21(18):5639-5644.

[4]趙彩霞,李海峰.多機場終端區(qū)聯(lián)合放行策略優(yōu)化[J].交通信息與安全,2012,30(3):83-86.

[5]張穎,胡明華,謝華.航路流量間隔限制及排序策略一體化決策模型及算法[J].系統(tǒng)工程理論與實踐,2013,33(9):2430-2436.

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

[7]王莉莉,顧秋麗.平行跑道到達(dá)航班排序問題研究[J].飛行力學(xué),2013,31(6):566-569.

[8]王莉莉,顧秋麗.特殊情況下的進(jìn)離場航班排序問題研究[J].交通運輸系統(tǒng)工程與信息,2014,14(2):102-107.

[9]史峰,王輝,郁磊.MATLAB 智能算法30個案例分析[M].北京:北京航空航天大學(xué)出版社,2011:321-367.

(編輯：崔立峰)

Modeling and algorithm of arrival and departing aircraft sequencing in multi-airport terminal area collaborative decision

WANG Li-li, ZHANG Xiao-xiao

(College of Air Traffic Management, CAUC, Tianjin 300300, China)

Abstract:Airline network of multi-airport terminal area is so complicated that the arrival and departing of aircraft are restricted by operational separation and capacity of each unit,the aircraft go to or come from the same direction will pass the same joint point. Based on multi-restrict constraints of multi-airport terminal area, a sequencing model was set up. A recursive genetic algorithm was set up for sequencing. Firstly sequencing the aircraft of each airport, then aircraft which go through the same cross point was classified and sequenced according to the wake turbulence separation. Finally the queue of each cross point was inserted in to each airport, using the recursive genetic algorithm to optimize the sequences, created a new queue of each airport so as to ensure safety. It is proved that this model and algorithm will optimize the delay time and can decrease delay time 48.2% than FCFS, which can reduce the delay efficiently.

Key words:multi-airport terminal area; multi-restrict constraints; arrival and departing sequencing; genetic algorithm

中圖分類號：V355

文獻(xiàn)標(biāo)識碼：A

文章編號：1002-0853(2016)01-0090-05

作者簡介:王莉莉(1973-)，女，陜西興平人，教授，博士，主要研究方向為空域規(guī)劃和空中交通優(yōu)化理論。

基金項目:國家自然科學(xué)基金委員會與中國民用航空局聯(lián)合資助(61179042)；中央高?；究蒲薪?jīng)費資助(ZXp012L005)

收稿日期:2015-05-12;

修訂日期:2015-08-04; 網(wǎng)絡(luò)出版時間:2015-09-10 09:55