平行跑道到達航班排序問題研究

王莉莉, 顧秋麗

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

平行跑道到達航班排序問題研究

王莉莉, 顧秋麗

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

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

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

0 引言

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

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

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

1 問題的提出

具有平行跑道的機場終端區平面機構示意圖如圖1所示。假設終端區內只考慮到達的航班流,航班按照儀表進場程序從不同的航路進入終端區準備著陸,在進場航線交叉點處按照著陸時間先后順序排成隊列。

圖1 機場終端區平面結構示意圖Fig.1 Diagram of an airport terminal area

由圖1可知,終端區空域按起始調度界限與終止調度界限的定義可以分為三個部分。當到達航班穿越設定的起始調度界限時,用排序算法根據到達航班的預計到達時間、航班類型等進行排序并分配其降落的跑道號;當到達航班穿越終止調度界限后,由算法分配給航班著陸的到達時間和跑道將確定,不再改變。兩個界限間的時域即為航班動態排序區。

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

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

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

2 到達航班排序模型的建立

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

目標函數以使總的延遲時間最小為原則。目標函數為:

(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)考慮飛機性能、管制員的負荷以及航班先到先服務的公平性原則,引入了最大移動位置數(Maximum Position Shifting,MPS),即以FCFS航班順序為基準,航班向前或向后移動的最大位置數為MPS。由以上可知yij=yji(i,j=1,2,…,N;i≠j)。

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

3 遺傳算法的設計

(1)編碼

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

表2 二重結構編碼方式Table 2 Dual coding mode

(2)種群的初始化

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

(3)適應度函數

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

(4)選擇操作

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

(5)交叉操作

以部分映射雜交的方式確定交叉操作的上行碼,子個體的下行碼值根據其父代個體中下行碼與上行碼的對應關系來確定。

(6)變異操作

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

(7)進化逆轉操作

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

進化逆轉操作采取在父代染色中隨機選取兩個位置,進行逆轉。如選取位置四和位置七進行逆轉操作。

4 算法仿真

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

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

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

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

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

5 結束語

本文討論了終端區到達航班的排序問題,建立了平行跑道終端區到達航班的排序模型,并設計了遺傳算法進行求解。采用了精英策略以及進化逆轉操作,使其搜索最優解的能力更強,能快速尋找到所需的最優解。本文所設計的遺傳算法與先到先服務

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

[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] 徐肖豪,黃寶軍.終端區飛機排序的模糊綜合評判方法研究[J].航空學報, 2001,22(3):259-261.

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

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

[8] 王飛,徐肖豪.終端區飛機排序的混合人工魚群算法[J].交通運輸工程學報,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">網絡出版時間

時間:2013-10-22 14:16

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

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

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

(編輯：姚妙慧)