多跑道飛機降落排序快速優化方法

張勰, 劉宏志, 趙嶷飛

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

多跑道飛機降落排序快速優化方法

張勰, 劉宏志, 趙嶷飛

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

針對多跑道飛機降落排序這一典型的組合優化問題,建立了以延誤代價最小為目標的優化模型,并提出了一種基于貪心策略的動態規劃算法。在生成子節點時引入貪心策略,通過簡化搜索過程的復雜度,提高算法運行效率,以解決問題規模增大導致計算效率低下的難題。仿真結果表明,該方法能夠有效簡化搜索過程,在優化效果與動態規劃算法相當的情況下,有效降低了運算時間,證明了方法的有效性。

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

0 引言

飛機降落排序是終端區空中交通的一個重要環節,順暢、高效的排序方案有助于緩解終端區空中交通擁堵,減少飛機空中延誤,進而提高整個空管系統的運行效率,對于實現空中交通管制現代化、自動化具有重要的現實意義。

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

1 問題模型

跑道數量、構型與實際運行模式都會影響飛機排序方案,考慮到目前我國多跑道機場多為平行雙跑道配置的現實情況,本文以平行雙跑道為例進行討論。

考慮一平行雙跑道機場,已知待降落飛機隊列中各飛機的初始預計降落時間與時間窗,在滿足一定約束條件的情況下,對各飛機的降落順序、降落跑道、降落時間進行優化。

1.1 優化目標

延誤代價是飛機排序問題中的首要考量要素,于是有:

(1)

式中:F為飛機集合;延誤時間tDTi=tSTAi-tETAi,tDTi>0表示飛機i發生了延誤,tDTi=0表示飛機i正點到達,tDTi<0表示飛機i提前到達;tSTAi和tETAi分別為飛機i的優化降落時間和預計降落時間;αi和βi分別為延誤代價系數和提前代價系數;C為單位時間的延誤成本。

1.2 約束條件

1.2.1 降落順序約束

(2)

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

1.2.2 安全間隔約束

tSTAj-tSTAi≥Sij(i≠j)

(3)

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

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

1.2.3 降落順序約束

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

(4)

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

1.2.4 位置交換約束[7]

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

設k為最大位置偏移量,飛機i在初始隊列中的位置為Ai,在新隊列中的位置為A*i,則:

(5)

1.2.5 降落時間窗

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

tSTAi∈[tETAi-tAmax,tETAi+tDmax]

(6)

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

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

(7)

式中:N為盤旋圈數;Th為盤旋一圈所需的時間。

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

2.1 動態規劃算法

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

2.2 貪心策略

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

3 仿真算例

隨機產生100個先到先服務飛機隊列,對這100個隊列進行優化調度,并統計優化結果,取其平均值作為算法的性能指標。

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

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

表2 算法運算性能比較Table 2 Performance comparison of two algorithms

圖1給出了平行雙跑道總延誤最小的優化結果。可以看出：算法優化效果隨飛機數量增加逐步提升,這是由于當飛機數量較少時,其相對于大量飛機的可優化空間亦相對較小;不同的飛機數量和k值均會影響運算時間,但即使是70架飛機、k=3時用時也僅為2.53 s,完全能夠滿足實時調度的需求。

圖1 平行雙跑道優化結果Fig.1 Optimum results of parallel runways

4 結束語

本文針對飛機排序問題提出一種快速優化方法,在生成子節點時引入貪心策略,通過簡化搜索過程的復雜度,提高算法運行效率。仿真結果表明,在保持優化效果相當的情況下,加入貪心策略后算法運算速度提高了近100倍,滿足實際運行需求。

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

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

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

[3] 王世東,張越,張智海,等.繁忙機場航班降落排序的多目標優化[J].交通運輸系統工程與信息,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] 孟祥偉,張平,李春錦.到場飛機排序及調度問題的Memetic算法[J].西南交通大學學報,2011,46(3):488-493.

[6] 張勰,趙嶷飛,劉宏志.基于協同進化遺傳算法的航班進港優化調度[J].交通運輸系統工程與信息,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；

時間：2015-05-13 17:14

國家自然科學基金資助(U1333108)；國家科技支撐計劃資助(2011BAH24B10)；中央高校基本科研業務費專項資助(3122014C020)

張勰(1981-)，男，陜西咸陽人，助理研究員，博士，研究方向為空中交通管理系統優化理論與方法。

V355.2

A

1002-0853(2015)05-0467-04