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

王莉莉, 顧秋麗

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

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

王莉莉, 顧秋麗

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

研究了在終端區(qū)空域繁忙的情況下,如何合理地安排到達(dá)航班的降落順序以及同時(shí)為到達(dá)航班分配跑道，以增加空中交通流量、減少航班延誤。考慮航班之間尾流間隔的不同,建立了平行跑道到達(dá)航班的排序模型并設(shè)計(jì)了雙重編碼的遺傳算法,即用一對(duì)染色體確定到達(dá)航班的跑道分配與降落序號(hào)。研究結(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)問題是一個(gè)急需解決的問題,也是空中交通流量管理研究的主要問題。

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

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

1 問題的提出

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

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

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

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

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

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

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

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

目標(biāo)函數(shù)以使總的延遲時(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在同一跑道上降落時(shí)之間的間隔要大于等于Sij,式(4)說明前后兩架航班i和j在不同跑道上降落時(shí)之間的間隔要大于等于Dij; 式(5)考慮飛機(jī)性能、管制員的負(fù)荷以及航班先到先服務(wù)的公平性原則,引入了最大移動(dòng)位置數(shù)(Maximum Position Shifting,MPS),即以FCFS航班順序?yàn)榛鶞?zhǔn),航班向前或向后移動(dòng)的最大位置數(shù)為MPS。由以上可知yij=yji(i,j=1,2,…,N;i≠j)。

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

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

(1)編碼

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

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

(2)種群的初始化

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

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

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

(4)選擇操作

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

(5)交叉操作

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

(6)變異操作

變異操作采取在父代染色體中隨機(jī)選取兩個(gè)位置并將其對(duì)換。

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

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

進(jìn)化逆轉(zhuǎn)操作采取在父代染色中隨機(jī)選取兩個(gè)位置,進(jìn)行逆轉(zhuǎn)。如選取位置四和位置七進(jìn)行逆轉(zhuǎn)操作。

4 算法仿真

根據(jù)《中國民用航空總局令(第123號(hào))平行跑道同時(shí)儀表運(yùn)行管理規(guī)定》第七條所述,平行雙跑道同時(shí)儀表運(yùn)行按照跑道用于進(jìn)近使用方式分為獨(dú)立平行儀表進(jìn)近、相關(guān)平行儀表進(jìn)近兩種模式。本文設(shè)定機(jī)場的跑道數(shù)r=2,當(dāng)平行雙跑道使用相關(guān)平行儀表進(jìn)近時(shí),不同跑道上航班之間尾流間隔與單跑道類似,因此將兩條平行跑道設(shè)置為獨(dú)立的運(yùn)行狀態(tài),即航班在不同跑道上降落的時(shí)間間隔Dij=0,以40架航班為例對(duì)算法進(jìn)行了驗(yà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)化后的航班總延誤時(shí)間為8 681 s,先到先服務(wù)(FCFS)算法、先優(yōu)化到達(dá)航班順序后優(yōu)化跑道分配算法以及先優(yōu)化跑道分配后優(yōu)化航班排序算法的總延誤時(shí)間分別為9 987 s,10 534 s,8 709 s,比較結(jié)果如圖3所示。由仿真結(jié)果可知,同時(shí)優(yōu)化到達(dá)航班的排序和跑道的分配可以有效減少航班延誤時(shí)間,提高空中交通管制效率。

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

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

5 結(jié)束語

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

(FCFS)算法、先優(yōu)化到達(dá)航班順序后優(yōu)化跑道分配算法以及先優(yōu)化跑道分配后優(yōu)化航班排序算法相比,不僅有效地減少了航班延誤時(shí)間,并且實(shí)時(shí)性更好,提高了空中交通管制效率,能夠在一定程度上緩解繁忙機(jī)場終端區(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ī)排序的模糊綜合評(píng)判方法研究[J].航空學(xué)報(bào), 2001,22(3):259-261.

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

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

[8] 王飛,徐肖豪.終端區(qū)飛機(jī)排序的混合人工魚群算法[J].交通運(yùn)輸工程學(xué)報(bào),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ò)出版時(shí)間

時(shí)間:2013-10-22 14:16

國家自然科學(xué)基金委員會(huì)與中國民用航空局聯(lián)合資助(61179042);中央高校基本科研業(yè)務(wù)費(fèi)資助(ZXH 2012L005)

王莉莉(1973-),女,陜西興平人,副教授,博士,研究方向?yàn)榭罩薪煌ü芾怼⑷藶橐蛩氐?

顧秋麗(1988-),女,遼寧錦州人,碩士研究生,研究方向?yàn)榭罩薪煌ü芾碇械呐判騿栴}。

(編輯：姚妙慧)