張勰, 劉宏志, 趙嶷飛

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

多跑道飛機(jī)降落排序快速優(yōu)化方法

張勰, 劉宏志, 趙嶷飛

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

針對多跑道飛機(jī)降落排序這一典型的組合優(yōu)化問題,建立了以延誤代價(jià)最小為目標(biāo)的優(yōu)化模型,并提出了一種基于貪心策略的動態(tài)規(guī)劃算法。在生成子節(jié)點(diǎn)時(shí)引入貪心策略,通過簡化搜索過程的復(fù)雜度,提高算法運(yùn)行效率,以解決問題規(guī)模增大導(dǎo)致計(jì)算效率低下的難題。仿真結(jié)果表明,該方法能夠有效簡化搜索過程,在優(yōu)化效果與動態(tài)規(guī)劃算法相當(dāng)?shù)那闆r下,有效降低了運(yùn)算時(shí)間,證明了方法的有效性。

空中交通管理; 降落排序; 多跑道; 貪心策略

0 引言

飛機(jī)降落排序是終端區(qū)空中交通的一個(gè)重要環(huán)節(jié),順暢、高效的排序方案有助于緩解終端區(qū)空中交通擁堵,減少飛機(jī)空中延誤,進(jìn)而提高整個(gè)空管系統(tǒng)的運(yùn)行效率,對于實(shí)現(xiàn)空中交通管制現(xiàn)代化、自動化具有重要的現(xiàn)實(shí)意義。

飛機(jī)降落排序需要確定飛機(jī)的降落順序、降落跑道和降落時(shí)間,是一個(gè)NP-hard問題[1]?？紤]跑道調(diào)度和著陸時(shí)間的制定,該問題的解空間十分龐大,而且對各種參數(shù)(如時(shí)間、飛機(jī)數(shù)目、跑道數(shù)目等)十分敏感[2-3]。傳統(tǒng)方法在問題規(guī)模不大時(shí)能夠有條件地求得有效解,在問題規(guī)模逐漸增大的情況下,由于計(jì)算代價(jià)過大,難以在理想時(shí)間范圍內(nèi)找到優(yōu)化解[4-6],導(dǎo)致這些算法的應(yīng)用受到極大的限制。本文針對多跑道降落排序問題,提出了基于貪心策略的快速優(yōu)化方法,該方法大大降低了搜索過程的復(fù)雜度,使得優(yōu)化排序方案兼顧了實(shí)時(shí)性與可行性。

1 問題模型

跑道數(shù)量、構(gòu)型與實(shí)際運(yùn)行模式都會影響飛機(jī)排序方案,考慮到目前我國多跑道機(jī)場多為平行雙跑道配置的現(xiàn)實(shí)情況,本文以平行雙跑道為例進(jìn)行討論。

考慮一平行雙跑道機(jī)場,已知待降落飛機(jī)隊(duì)列中各飛機(jī)的初始預(yù)計(jì)降落時(shí)間與時(shí)間窗,在滿足一定約束條件的情況下,對各飛機(jī)的降落順序、降落跑道、降落時(shí)間進(jìn)行優(yōu)化。

1.1 優(yōu)化目標(biāo)

延誤代價(jià)是飛機(jī)排序問題中的首要考量要素,于是有:

(1)

式中:F為飛機(jī)集合;延誤時(shí)間tDTi=tSTAi-tETAi,tDTi>0表示飛機(jī)i發(fā)生了延誤,tDTi=0表示飛機(jī)i正點(diǎn)到達(dá),tDTi<0表示飛機(jī)i提前到達(dá);tSTAi和tETAi分別為飛機(jī)i的優(yōu)化降落時(shí)間和預(yù)計(jì)降落時(shí)間;αi和βi分別為延誤代價(jià)系數(shù)和提前代價(jià)系數(shù);C為單位時(shí)間的延誤成本。

1.2 約束條件

1.2.1 降落順序約束

(2)

式中:λij為飛機(jī)i與j之間的降落順序,λij=1表示飛機(jī)i早于j降落,λij=0表示飛機(jī)i晚于j降落;λij+λji=1,i≠j。

1.2.2 安全間隔約束

tSTAj-tSTAi≥Sij(i≠j)

(3)

本約束表明，若飛機(jī)i早于j降落,則它們之間的間隔必須大于兩者之間的最小安全間隔Sij。

國際民航組織規(guī)定:根據(jù)飛機(jī)的最大起飛重量,飛機(jī)可以分為重型機(jī)H、中型機(jī)M、輕型機(jī)L三種類型。終端區(qū)內(nèi)待排序飛機(jī)隊(duì)列是由不同類型的飛機(jī)組成的,飛機(jī)的前后順序不同所需要的最小尾流間隔也不同。國際民航組織對不同類型飛機(jī)間的最小尾流間隔(單位為m)的規(guī)定如表1所示。

1.2.3 降落順序約束

本文采用的多跑道模型為兩條平行跑道的模型,并處于相關(guān)運(yùn)行模式下,這是實(shí)際中較為常見的一種雙跑道配置模式,在我國具有較為普遍的代表性。多跑道調(diào)度除了需要給飛機(jī)分配降落時(shí)刻和順序外,還要指定其降落的跑道,且相鄰飛機(jī)在不同的跑道上降落也需要保證一定的安全時(shí)間間隔。在相關(guān)運(yùn)行模式下,兩條跑道可以一先一后安排飛機(jī)著陸,前后飛機(jī)之間的側(cè)向間距為不小于4 km,此側(cè)向間距可以轉(zhuǎn)化為40 s的著陸時(shí)間間隔,而這一時(shí)間間隔與飛機(jī)類型無關(guān)。也就是說,對于在同一跑道上降落的兩架飛機(jī)之間必須按其機(jī)型配備滿足表1所示的安全間隔要求,而對于在不同跑道降落的兩架飛機(jī)之間只需保證40 s的間隔即可。于是有:

(4)

式中：Zij=1表示飛機(jī)i與飛機(jī)j在同一跑道降落;Zij=0表示在不同跑道降落。

1.2.4 位置交換約束[7]

考慮到管制員的工作負(fù)荷和運(yùn)行安全,降落調(diào)度中過大的位置調(diào)整在管制運(yùn)行中是不實(shí)際的,即調(diào)度前后飛機(jī)位置的變動幅度不能超過一定的范圍。例如最大位置偏移量為2,若某架飛機(jī)在先到先服務(wù)的隊(duì)列中排在第5位,則它在新隊(duì)列中只能占據(jù)第3,4,5,6,7位。這種思想不僅保證了一定的公平性,還極大地縮小了解空間。

設(shè)k為最大位置偏移量,飛機(jī)i在初始隊(duì)列中的位置為Ai,在新隊(duì)列中的位置為A*i,則:

(5)

1.2.5 降落時(shí)間窗

受飛機(jī)性能和進(jìn)場程序等條件的限制,飛機(jī)只能在特定的降落時(shí)間窗內(nèi)降落在跑道上,如式(6)所示:

tSTAi∈[tETAi-tAmax,tETAi+tDmax]

(6)

此外,飛機(jī)在終端區(qū)內(nèi)可以通過一定時(shí)間的盤旋飛行來吸收延誤,因此飛機(jī)的降落時(shí)間窗就擴(kuò)展為若干段離散的時(shí)間段,如式(7)所示:

tSTAi∈[tETAi-tAmax,tETAi+tDmax]+NTh

(7)

式中:N為盤旋圈數(shù);Th為盤旋一圈所需的時(shí)間。

2 基于貪心策略的排序算法

2.1 動態(tài)規(guī)劃算法

文獻(xiàn)[8]提出了一種求解飛機(jī)排序問題的動態(tài)規(guī)劃算法,其基本思想為:按降落飛機(jī)架數(shù)0到n遞推,遞推到m架時(shí),需要計(jì)算、存儲滿足條件的所有情況,即降落的所有m架飛機(jī)及其可能的所有排列方式。受位置交換約束中k值的影響,可以知道當(dāng)前m架飛機(jī)中已確定降落順序的為第1～m-k架,而第m-k+1～m架的k架飛機(jī)則尚未確定降落順序,且這k架只可能為原序列第m-k+1～m+k飛機(jī)中的任意k架[8]。所以可以用這k架飛機(jī)為第m層的飛機(jī)節(jié)點(diǎn)編號:每個(gè)節(jié)點(diǎn)存儲一定的飛機(jī)降落時(shí)間信息,即可按目標(biāo)遞推求解問題。另外,由于在連續(xù)的時(shí)間坐標(biāo)下,動態(tài)規(guī)劃算法無法實(shí)現(xiàn),因此需要根據(jù)實(shí)際的精度要求設(shè)置最小時(shí)間單位,將時(shí)間離散化。一個(gè)最小時(shí)間單位稱為一個(gè)時(shí)隙,一般一個(gè)時(shí)隙表示1～10 s是比較合適的,本文單位時(shí)隙取一個(gè)雷達(dá)掃描周期4 s。

2.2 貪心策略

考慮在子節(jié)點(diǎn)的選取上引入貪心策略,降低子節(jié)點(diǎn)的數(shù)量及對比次數(shù),以提高算法求解速度。舉例來說,對于m層節(jié)點(diǎn)的某個(gè)子節(jié)點(diǎn),假設(shè)某飛機(jī)x在跑道1的降落時(shí)間窗為[t1,t2],若t1

3 仿真算例

隨機(jī)產(chǎn)生100個(gè)先到先服務(wù)飛機(jī)隊(duì)列,對這100個(gè)隊(duì)列進(jìn)行優(yōu)化調(diào)度,并統(tǒng)計(jì)優(yōu)化結(jié)果,取其平均值作為算法的性能指標(biāo)。

參數(shù)設(shè)置:機(jī)型配比(H,M,L)=(0.3,0.6,0.1);單位時(shí)隙4 s;時(shí)間窗跨度為100個(gè)時(shí)隙。

表2為算法運(yùn)算性能比較(k=2)。由表2可知,未加貪心策略前雙跑道動態(tài)規(guī)劃算法的運(yùn)算時(shí)間較長,效率不高。加入貪心策略后,由于算法的子節(jié)點(diǎn)數(shù)目以及比較次數(shù)大幅降低,算法運(yùn)算速度在雙跑道環(huán)境下提高了近100倍,計(jì)算時(shí)間大大縮短。另一方面,算法的優(yōu)化效果也基本達(dá)到原動態(tài)規(guī)劃算法的優(yōu)化效果。這是由于保證了初始遞推所需的信息后,隨著遞推一步一步地進(jìn)行,貪心策略所丟失的信息量逐步得到彌補(bǔ),使得效果可以接近原算法的效果。

表2 算法運(yùn)算性能比較Table 2 Performance comparison of two algorithms

圖1給出了平行雙跑道總延誤最小的優(yōu)化結(jié)果?？梢钥闯觯核惴▋?yōu)化效果隨飛機(jī)數(shù)量增加逐步提升,這是由于當(dāng)飛機(jī)數(shù)量較少時(shí),其相對于大量飛機(jī)的可優(yōu)化空間亦相對較小;不同的飛機(jī)數(shù)量和k值均會影響運(yùn)算時(shí)間,但即使是70架飛機(jī)、k=3時(shí)用時(shí)也僅為2.53 s,完全能夠滿足實(shí)時(shí)調(diào)度的需求。

圖1 平行雙跑道優(yōu)化結(jié)果Fig.1 Optimum results of parallel runways

4 結(jié)束語

本文針對飛機(jī)排序問題提出一種快速優(yōu)化方法,在生成子節(jié)點(diǎn)時(shí)引入貪心策略,通過簡化搜索過程的復(fù)雜度,提高算法運(yùn)行效率。仿真結(jié)果表明,在保持優(yōu)化效果相當(dāng)?shù)那闆r下,加入貪心策略后算法運(yùn)算速度提高了近100倍,滿足實(shí)際運(yùn)行需求。

此外,本文的研究對象為平行雙跑道相關(guān)運(yùn)行模式下的飛機(jī)降落排序優(yōu)化問題,但不失一般性,本文算法稍加修改即可應(yīng)用于其他構(gòu)型(多條跑道數(shù)大于3、交叉跑道等)和運(yùn)行模式(獨(dú)立運(yùn)行、相關(guān)運(yùn)行)下的飛機(jī)降落排序優(yōu)化。

[1] Beasley J E,Krishnamoorthy M,Sharaiha Y M.Scheduling aircraft landings—the static case[J].Transportation Science,2000,34(2):180-197.

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

[3] 王世東,張?jiān)?張智海,等.繁忙機(jī)場航班降落排序的多目標(biāo)優(yōu)化[J].交通運(yùn)輸系統(tǒng)工程與信息,2012,12(4):135-142.

[4] Zhan Z H,Zhang J,Li Y.An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem[J].IEEE Transactions on Intelligent Transportation Systems,2010,11(2):399-412.

[5] 孟祥偉,張平,李春錦.到場飛機(jī)排序及調(diào)度問題的Memetic算法[J].西南交通大學(xué)學(xué)報(bào),2011,46(3):488-493.

[6] 張勰,趙嶷飛,劉宏志.基于協(xié)同進(jìn)化遺傳算法的航班進(jìn)港優(yōu)化調(diào)度[J].交通運(yùn)輸系統(tǒng)工程與信息,2014,14(2):94-101.

[7] Dear R G.The dynamic scheduling of aircraft in the near terminal area[R].Cambridge, Mass.: MIT,Flight Transportation Laboratory,1976.

[8] Lee H,Hamsa B.Fuel cost,delay and throughput tradeoffs in runway scheduling [C]//Proceedings of the American Control Conference.Seattle:IEEE Press,2008:2449-2454.

(編輯:方春玲)

A fast optimization method for multi-runway aircraft landing sequencing

ZHANG Xie, LIU Hong-zhi, ZHAO Yi-fei

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

Focusing on this typical combinatorial problem of sequencing the arrival aircraft for multi-runway, optimization model with minimum delay is established, and a dynamic programming algorithm based on greedy strategy is proposed. The greedy strategy is introduced while generating the nodes, and then reduces the searching complexity to improve the algorithm efficiency, so that the problem is solved that the computation efficiency decreases as the scale of the problem increases. Through the simulation, it is shown that the algorithm proposed here can simplify the searching process effectively, and the time is reduced effectively as the optimization effect is equivalent to the dynamic programming algorithm. The effectiveness of the algorithm is proved.

air traffic flow management; landing sequencing; multi-runway; greedy strategy

2014-11-08；

2015-03-16；

時(shí)間：2015-05-13 17:14

國家自然科學(xué)基金資助(U1333108)；國家科技支撐計(jì)劃資助(2011BAH24B10)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資助(3122014C020)

張勰(1981-)，男，陜西咸陽人，助理研究員，博士，研究方向?yàn)榭罩薪煌ü芾硐到y(tǒng)優(yōu)化理論與方法。

V355.2

A

1002-0853(2015)05-0467-04