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

王莉莉, 張瀟瀟

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

?

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

王莉莉, 張瀟瀟

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

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

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

0引言

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

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

1問題的提出

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

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

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

2.1模型假設(shè)

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

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

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

(1)

2.3約束條件

2.3.1跑道容量約束

(2)

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

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

(3)

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

2.3.3離場定位點(diǎn)容量約束

(4)

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

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

(5)

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

2.3.5交接點(diǎn)容量約束

(6)

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

2.3.6扇區(qū)容量約束

(7)

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

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

(8)

(9)

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

(10)

2.3.9交接點(diǎn)間隔限制

(11)

2.3.10延誤時(shí)間限制

(12)

(13)

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

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

3算法設(shè)計(jì)

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

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

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

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

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

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

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

(14)

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

4仿真算例

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

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

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

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

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

4.2仿真計(jì)算

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

表2　多機(jī)場初始交通需求

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

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

5結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

[9]史峰,王輝,郁磊.MATLAB 智能算法30個(gè)案例分析[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

中圖分類號(hào)：V355

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

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

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

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

收稿日期:2015-05-12;

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