王莉莉, 顧秋麗

(中國民航大學(xué) 天津市空管運行規(guī)劃與安全技術(shù)重點實驗室, 天津 300300)

平行跑道到達(dá)航班排序問題研究

王莉莉, 顧秋麗

(中國民航大學(xué) 天津市空管運行規(guī)劃與安全技術(shù)重點實驗室, 天津 300300)

研究了在終端區(qū)空域繁忙的情況下,如何合理地安排到達(dá)航班的降落順序以及同時為到達(dá)航班分配跑道，以增加空中交通流量、減少航班延誤?？紤]航班之間尾流間隔的不同,建立了平行跑道到達(dá)航班的排序模型并設(shè)計了雙重編碼的遺傳算法,即用一對染色體確定到達(dá)航班的跑道分配與降落序號。研究結(jié)果表明,與先到先服務(wù)算法、先優(yōu)化到達(dá)航班順序后優(yōu)化跑道分配算法以及先優(yōu)化跑道分配后優(yōu)化到達(dá)航班順序算法相比,該算法優(yōu)化后的航班排序與跑道分配有效地減少了航班延誤。

空中交通管制; 跑道分配; 到達(dá)航班排序; 遺傳算法

0 引言

隨著我國民航事業(yè)的不斷發(fā)展,空中流量迅速增長,終端區(qū)空域擁擠問題造成航班延誤現(xiàn)象越來越嚴(yán)重,因此終端區(qū)內(nèi)到達(dá)航班的排序與調(diào)度(Arrival Scheduling and Sequencing,ASS)問題是一個急需解決的問題,也是空中交通流量管理研究的主要問題。

國外對ASS問題的研究比較早,文獻(xiàn)[1]用位置交換約束法(CRS)對單跑道著陸航班排序問題進(jìn)行了研究,然而隨著問題規(guī)模的增大,CRS求解模型的實時性不好。文獻(xiàn)[2-3]證明了旅行商問題(Traveling Salesman Problem,TSP)是累計不對稱問題,并將其應(yīng)用在航班的動態(tài)排序中,得到了航班的最佳著陸次序,但這樣可能會使航班的著陸次序變化較大,增加了管制員的負(fù)荷。文獻(xiàn)[4]通過運用排隊論方法,采用離散事件仿真技術(shù)來研究多跑道航班動態(tài)著陸問題,假設(shè)到達(dá)航班流服從泊松分布,得出航班到達(dá)時間服從指數(shù)分布。上述對航班排序的研究主要側(cè)重在為動態(tài)到達(dá)的航班分配降落跑道,但未在分配跑道的研究中考慮尾流間隔的優(yōu)化。國內(nèi)對ASS問題的研究起步較晚,文獻(xiàn)[5]將模糊綜合評判方法應(yīng)用于單跑道到達(dá)航班排序,綜合考慮了航班排序中的各種因素,但模糊綜合評判法隸屬函數(shù)受實際問題影響較大,計算復(fù)雜。文獻(xiàn)[6-7]運用遺傳算法求解了單跑道情況下到達(dá)航班的排序問題。文獻(xiàn)[8]提出了混合人工魚群算法,并將其應(yīng)用在單跑道和多跑道著陸航班的排序中,該算法有效地減少了航班的延誤,但當(dāng)航班數(shù)量較多時其求解效率較差。

本文建立了平行跑道到達(dá)航班的排序模型。由于該問題是典型的TSP組合優(yōu)化問題,同時也是難解的NP完全問題,采用常規(guī)的求解算法很難滿足航班排序?qū)崟r性的要求。因此,本文設(shè)計了基于雙重編碼的遺傳算法對平行跑道到達(dá)航班的排序模型進(jìn)行求解,求解時用一對染色體將航班著陸序號與跑道號對應(yīng)起來同時優(yōu)化跑道的分配與航班的著陸順序,還采用了精英策略以及進(jìn)化逆轉(zhuǎn)操作,大大提高了遺傳算法的求解效率,最后通過仿真驗證了其可行性。

1 問題的提出

具有平行跑道的機場終端區(qū)平面機構(gòu)示意圖如圖1所示。假設(shè)終端區(qū)內(nèi)只考慮到達(dá)的航班流,航班按照儀表進(jìn)場程序從不同的航路進(jìn)入終端區(qū)準(zhǔn)備著陸,在進(jìn)場航線交叉點處按照著陸時間先后順序排成隊列。

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

由圖1可知,終端區(qū)空域按起始調(diào)度界限與終止調(diào)度界限的定義可以分為三個部分。當(dāng)?shù)竭_(dá)航班穿越設(shè)定的起始調(diào)度界限時,用排序算法根據(jù)到達(dá)航班的預(yù)計到達(dá)時間、航班類型等進(jìn)行排序并分配其降落的跑道號;當(dāng)?shù)竭_(dá)航班穿越終止調(diào)度界限后,由算法分配給航班著陸的到達(dá)時間和跑道將確定,不再改變。兩個界限間的時域即為航班動態(tài)排序區(qū)。

空中交通管制的目的是為了保證航班的安全,使航班與航班之間具有一定的安全間隔。但目前的空中交通管制主要是基于距離間隔保證航班飛行的安全。為了保證流量管理的精確性,本文引入了時基的概念,把飛機的距離間隔轉(zhuǎn)化為時間間隔。根據(jù)國際民航組織(ICAO)對無風(fēng)條件下不同機型的最小尾流間隔作出的規(guī)定,通過計算可以得到不同機型間的最小安全間隔時間[9](單位:s),如表1所示。

表1 不同機型間的尾流最小間隔(Sij) Table 1 Minimum wake flow separation between different types of aircraft

從表1可以看出,不同機型間的尾流最小間隔是不同的并且是非對稱的,本文基于位置調(diào)換法(Position Shifting,PS)利用著陸時不同機型間不同的尾流間隔來調(diào)換到達(dá)航班的位置順序以及優(yōu)化航班的跑道分配。

2 到達(dá)航班排序模型的建立

假設(shè)某一具有多跑道繁忙機場的終端區(qū)航班架數(shù)為N,表示為f=(1,2,…,N);設(shè)航班i在跑道r的預(yù)計降落時間為ETi,實際降落時間為ATir;r=(1,2,…,R)為機場跑道數(shù)目;g(i)表示到達(dá)航班隊列優(yōu)化后第i個位置的航班;xir為航班對跑道的變量,yij為航班對航班的變量。令:

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

(1)

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

(i=1,2,…,N;r=1,2,…,R)

(2)

ATjr-ATir≥Sij

(i,j=1,2,…,N(j>i);r=1,2,…,R)

(3)

ATjr-ATi,r+1≥Dij

(i,j=1,2,…,N(j>i);r=1,2,…,R)

(4)

|i-z|≤MPS,g(i)=z

(i,z=1,2,…,N)

(5)

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

令Tdel=ATir-ETi,當(dāng)航班i的ATir≤ETi時,Tdel=0,即無延遲。當(dāng)航班i的ATir>ETi時,Tdel=ATir-ETi。若前后兩架航班使用同一條跑道時(i-1為i的前一架航班),則航班的實際到達(dá)時間為ATir=max(ATi-1,r+Si,i-1,ETi);若前后兩架航班使用不同跑道時,則航班的實際到達(dá)時間為ATir=max(ATi-1,r+Di,i-1,ETi)。

3 遺傳算法的設(shè)計

(1)編碼

為了與平行多跑道運行方案相匹配,本文采用的編碼方式為二重結(jié)構(gòu)編碼。每個染色體由上行碼和下行碼組成。上行碼表示到達(dá)航班的降落次序,下行碼表示航班降落的跑道號,上下行碼都以整數(shù)形式進(jìn)行編碼。以兩條跑道、7架航班為例,編碼方式如表2所示。

表2 二重結(jié)構(gòu)編碼方式Table 2 Dual coding mode

(2)種群的初始化

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

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

(i,j=1,2，…,N(j>i);r=1,2,…,R)

(4)選擇操作

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

(5)交叉操作

以部分映射雜交的方式確定交叉操作的上行碼,子個體的下行碼值根據(jù)其父代個體中下行碼與上行碼的對應(yīng)關(guān)系來確定。

(6)變異操作

變異操作采取在父代染色體中隨機選取兩個位置并將其對換。

(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ìn)行逆轉(zhuǎn)。如選取位置四和位置七進(jìn)行逆轉(zhuǎn)操作。

4 算法仿真

根據(jù)《中國民用航空總局令(第123號)平行跑道同時儀表運行管理規(guī)定》第七條所述,平行雙跑道同時儀表運行按照跑道用于進(jìn)近使用方式分為獨立平行儀表進(jìn)近、相關(guān)平行儀表進(jìn)近兩種模式。本文設(shè)定機場的跑道數(shù)r=2,當(dāng)平行雙跑道使用相關(guān)平行儀表進(jìn)近時,不同跑道上航班之間尾流間隔與單跑道類似,因此將兩條平行跑道設(shè)置為獨立的運行狀態(tài),即航班在不同跑道上降落的時間間隔Dij=0,以40架航班為例對算法進(jìn)行了驗證。遺傳算法的種群大小為100,最大進(jìn)化代數(shù)為50,航班交叉概率pcf=0.9,跑道交叉概率pcr=0.9,航班變異概率pcf=0.05,跑道變異概率pcr=0.05,MPS=3。

到達(dá)航班遺傳算法的收斂過程如圖2所示。由圖可知,本文的遺傳算法采用了進(jìn)化逆轉(zhuǎn)操作,改善了遺傳算法的局部搜索能力,加快了收斂速度。

經(jīng)本文算法優(yōu)化后的航班總延誤時間為8 681 s,先到先服務(wù)(FCFS)算法、先優(yōu)化到達(dá)航班順序后優(yōu)化跑道分配算法以及先優(yōu)化跑道分配后優(yōu)化航班排序算法的總延誤時間分別為9 987 s,10 534 s,8 709 s,比較結(jié)果如圖3所示。由仿真結(jié)果可知,同時優(yōu)化到達(dá)航班的排序和跑道的分配可以有效減少航班延誤時間,提高空中交通管制效率。

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

圖3 四種算法延誤時間的比較Fig.3 Comparison of delay times for four algorithms

5 結(jié)束語

本文討論了終端區(qū)到達(dá)航班的排序問題,建立了平行跑道終端區(qū)到達(dá)航班的排序模型,并設(shè)計了遺傳算法進(jìn)行求解。采用了精英策略以及進(jìn)化逆轉(zhuǎn)操作,使其搜索最優(yōu)解的能力更強,能快速尋找到所需的最優(yōu)解。本文所設(shè)計的遺傳算法與先到先服務(wù)

(FCFS)算法、先優(yōu)化到達(dá)航班順序后優(yōu)化跑道分配算法以及先優(yōu)化跑道分配后優(yōu)化航班排序算法相比,不僅有效地減少了航班延誤時間,并且實時性更好,提高了空中交通管制效率,能夠在一定程度上緩解繁忙機場終端區(qū)的擁擠問題。

[1] Dear R G.The dynamic scheduling of aircraft in the near terminal area[R].FTL R76-9,1976.

[2] Psaraftis H N.A dynamic programming approach to the aircraft sequencing problem[R].FTL R78-4,1978.

[3] Bianco L,Rinadi G,Ricciardelli S,et al.Scheduling tasks with sequence-dependent processing times[J].Naval Research Logistics,1988,35(2):177-184.

[4] Bolender M A,Slater G L.Cost analysis of the departure-en route merge problem[J].Journal of Aircraft,2000,37(1):23-29.

[5] 徐肖豪,黃寶軍.終端區(qū)飛機排序的模糊綜合評判方法研究[J].航空學(xué)報, 2001,22(3):259-261.

[6] 陶冶,白存儒.基于遺傳算法的航班動態(tài)排序模型研究[J].中國民航飛行學(xué)院學(xué)報,2005,5(16):3-7.

[7] 程曉航,薛惠鋒,洪鼎松,等.進(jìn)港飛機調(diào)度的精華自適應(yīng)遺傳算法設(shè)計[J].交通與計算機,2006,24(6):91-94.

[8] 王飛,徐肖豪.終端區(qū)飛機排序的混合人工魚群算法[J].交通運輸工程學(xué)報,2008,8(3):68-72.

[9] Dear R G,Sherif Y S.The dynamic scheduling of air-craft in high density terminal areas[J].Microelectron Reliab,1989,29(5):743-749.

Parallelrunwayarrivalaircraft-sequencingoptimization

WANG Li-li, GU Qiu-li

(Tianjin Key Lab of Operation Programming and Safety Technology of Air Traffic Management, CAUC, Tianjin 300300, China)

This paper studies on how to properly sequence the arrival aircraft and assign a runway for them in the case of air traffic congestion in the terminal area so as to increase the air traffic flow and reduce the flights’ delay. A model to solve the problem of parallel runway arrival aircraft-sequencing was set up and the genetic algorithm (GA) of dual code was designed according to the aircraft wake turbulence separation requirements. GA of dual code was that an arrival flight’s sequencing and landing runway was determined by a pair of chromosomes. Compared with the algorithms of first come first service(FCFS), first optimize arrival flights’ sequencing and then the assignment of runways for flights, first optimize the assignment of runways for flights and then the arrival flights sequencing, it is proved the provided model can effectively reduce the flights’ delay by actual data computation.

air traffic control; runway assignment; arrival aircraft-sequencing; genetic algorithm

V355

A

1002-0853(2013)06-0566-04

2013-03-18;

2013-06-04; < class="emphasis_bold">網(wǎng)絡(luò)出版時間

時間:2013-10-22 14:16

國家自然科學(xué)基金委員會與中國民用航空局聯(lián)合資助(61179042);中央高?；究蒲袠I(yè)務(wù)費資助(ZXH 2012L005)

王莉莉(1973-),女,陜西興平人,副教授,博士,研究方向為空中交通管理、人為因素等;

顧秋麗(1988-),女,遼寧錦州人,碩士研究生,研究方向為空中交通管理中的排序問題。

(編輯：姚妙慧)