基于沖突避免的離場調度優化算法

徐 磊，胡明華,謝 華,王 也

(1.國家飛行流量管理技術重點實驗室，南京 211106；2.南京航空航天大學 民航學院，南京 211106)

我國航空業持續蓬勃的發展使機場系統面臨運行與管制的壓力.而離場航班調度優化問題作為機場流量管理的重要組成部分，是近年來各國學者研究的熱點.針對離場排序目前主流的算法包括先到先服務(FCFS)算法[1]、帶有位置約束轉移的算法[2]和動態規劃法[3]等.

國內外對于離場航班調度優化展開了廣泛深入的研究，Montoya[4]等人以航班延誤最小和增加跑道容量作為多目標優化問題，使用多目標動態規劃方法進行建模并設計算法求解了帕累托前沿解集，最后在達拉斯國際機場驗證了模型效果.Sama M[5]等人將終端區進場航班調度問題和航空器軌跡優化問題結合在一起并采用字典式優化框架，其中航班調度問題以總航班延誤最小為目標而軌跡優化以飛行時間和油耗最小為目標函數.2012年，張啟錢，胡明華[6]將航班總延誤最小設為目標函數，以最大位置偏移為約束建立多跑道進離場航班排序模型，并采取滾動時域結合遺傳算法的方式對模型求解，最后以白云機場30條仿真數據作驗證，結果相較于FCFS延誤大幅下降.周姝媛，羅軍[7]在機場約束條件的基礎上建立了航班協同模型，并以成都終端區為實例，結合具體的航班時刻表進行預測，并將最后結果與FCFS作比較.在離場航班優化調度中，目前對于多跑道機場的航空器離場問題方面的研究較為欠缺，在實際運行中，管制員通常采用FCFS算法進行調度.然而FCFS算法在很大程度上依賴管制員的經驗，導致平均延誤時間較長，降低了安全和效率.

該本文針對多跑道機場，結合跑道分配[8]和航班排序，建立了以航班總延誤最少為目標函數的優化模型.模型使用遺傳算法進行求解，并將所得優化結果與FCFS方式作對比，結果表明所用算法明顯優于FCFS算法.

1 模型建立

1.1 機場節點-邊網絡模型

機場的場面結構網絡可以表示為一個有向圖G=(V，E)[9]，其中V與E分別代表機場各路段節點與滑行路徑的集合.機場結構示意圖見圖1.

圖1 機場結構示意圖

1.2 參數和變量

1.3 目標函數

本文以離場航班總延誤最小為目標函數，航班總延誤可由所有離場航班的實際起飛時間與預計起飛時間的差值求和得到.

(1)

其中：k表示航空器號，r表示跑道號，AT表示離場航班實際起飛時間，ET表示預計起飛時間.

1.4 約束條件

(2)

(3)

tATk-tATj≥Sjkyjk,

(j,k=1,2,…,N,j=k-1)

(4)

tATk≥tETk,(k=1,2,…,N)

(5)

tATk-tETk≤Tdmax,(k=1,2,…,N)

(6)

式(2)表示任意一架航班k只能從一條跑道起飛；式(3)表示在跑道端排隊的航空器數量不能超過在該段時間的跑道容量；式(4)表示以航班的尾流間隔為約束，場面上連續兩架航班j、航班k在同一條跑道起飛的間隔應不小于Sik.對于Sik，采用國際民航組織規定的最小尾流間隔標準.式(5)表示任意一架航班k不能在規定的預計起飛時間前起飛.式(6)表示任意一架航班延誤時間不能超過極限值.

2 基于遺傳算法的算法設計

2.1 算法優化步驟

由于上述模型是典型的NP-Hard[10]問題，伴隨著問題規模的增加，用一般線性整數規劃[11]進行精確求解難度較大且速度較慢，為了在較短時間內能得到一個實用性高的解，本文在這里選用遺傳算法[12](Genetic Algorithm, GA)進行求解.遺傳算法雖然不一定能在最短時間內求出一個全局最優解，但是可以在較短時間內獲得一個實用性較強的局部最優解.

根據調度優化模型的建立思路，設計如下推出時刻優化步驟：

1)根據離場航班數據以及FCFS原則求出航班推出時刻參考值序列.根據離場航班的預計起飛時間與無沖突滑行時間，按照FCFS原則對離場航班進行排序并計算出每架航班的推出時刻及航班總的延誤時間；

2)根據航班數據得出所有航班的最小安全時間間隔矩陣；

3)根據計算得出的最小時間間隔矩陣利用遺傳算法求出離場航班最優序列AR1；

4)依據每架航班的無沖突滑行時間，求得所有航班的滑行時間數組，以步驟3)得出的序列AR1為基礎，計算得到每架航班的推出時刻，如果發生多架離場航班推出時刻相同的情況時，則將優先級較低的航班延誤到下一時刻，這時可得最優的航班推出序列AR2.

2.2 遺傳算子與參數調整

1)由于算法既要對離場航班進行排序又要對跑道進行分配，因此在編碼方法上采取雙層編碼[13]的方式.上層采用實數編碼，表示航班的起飛順序；下層采用二進制編碼，表示每架離場航班對應的跑道.編碼示意圖如圖2所示

圖2 航班編碼示意圖

2)初始化：本文采取隨機生成一系列1～N的離場航班序列組成可行解，重復這一過程P次則生成數量為P的初始種群，本文將初始種群數量設為10.

3)選擇：對種群中的個體采取輪盤賭的方式進行選擇，按這種方式進行選擇時個體被選中的概率與其適應度函數成比例.因此適應度最高的個體最有可能被選中進行重組.同時采取最優保存策略，在每一代種群中，適應度在前20%的個體會被保留而剩下則會被新一代個體取代.

4)交叉：本文采取單點交叉的方式，隨機選取截斷點切割再組合并且按照交叉概率Pc確定交叉位置，在本文中交叉概率設置為0.8.

5)變異：變異概率通常會被設置的較低，一般在0.005～0.1之間.變異概率不能設置的過高因為很高的變異概率Pm會導致算法擴展搜索空間而使收斂時間變長.因此在本文中變異概率設置為0.1，且由于離場航班是用實數進行編碼，因而在本文中采取實值變異的方式進行.為了保證解的可行性，當變異發生時將變異的兩個位置的基因進行對調.

6)適應度函數：本文取目標函數的倒數為適應度函數，具體表示如下：

(7)

式(7)表明離場航班在地面的總延誤時間越短時適應度值越高.在多次迭代期間適應度值決定了種群可行解的性能.

3 算例仿真

本文選取南京路口機場的部分航班仿真數據在Matlab上進行仿真以驗證模型的正確性.祿口機場為雙跑道，因此將跑道的容量值設為13，選取4月份某日10∶00～10∶20共計20 min內20架離場航班數據作為樣本仿真，主要包括每架航班的機型以及航班時刻信息包括預計起飛時間、無沖突滑行時間、航班號、跑道號等.依據ICAO規定可得知航空器按照不同的機型可以分為輕型(L)、中型(M)、重型三類(H)，任意兩種類型航空器的最小尾流間隔標準矩陣Sjk[14]可表示如下：

(8)

其中：前后機分別為j,k，單位為 min.

航班的無沖突滑行時間通過離場航班從停機位到跑道的距離與滑行速度計算獲得.按照相關管理[15]規定，航空器的滑行速度不得小于2.78 m·s-1，不得超過13.9 m·s-1.本文取其平均值，即8 m·s-1.

離場航班信息如表1所示.

表1 離場航班信息

根據FCFS法則，先到跑道端的航班優先起飛，后續飛機按照優先級原則依次排隊，如果后續航班預計起飛時間不滿足尾流間隔則對起飛時間進行相應延誤，最后再依據無沖突滑行時間計算出航班推出時刻.結果如表2所示.

表2結果表明利用FCFS方法對求各航班離場推出時刻，產生的航班延誤總時間為36 min.根據表中結果能夠看出當離場航班以FCFS原則排序時，當某一架航班出現延誤時，后續航班受前面航班的影響也會出現相應延誤，延誤累計也會伴隨航班量增加而增加.與此相對的按照本文中的遺傳算法求解時，求得的仿真結果如表3所示.

表2 采用FCFS所得推出時刻表

表3結果表明利遺傳算法求出各航班離場推出時刻，產生的航班總延誤時間為23 min，相較于FCFS算法求得的總延誤時間少13 min，同比減少了約36%，且并不會產生延誤累積的情況.此外，由于算法在對推出時刻優化的同時對跑道也做出了分配，航班的滑行路徑會有所不同，航班的無沖突滑行時間也會隨之變化.針對本問題利用啟發式算法很好的優化了航班推出時刻，提高了離場航班的準點率，為推出航班排序提供了更加可靠的依據.

表3 采用遺傳算法所得推出時刻表

采用FCFS排序與遺傳算法排序時結果對比圖如圖3所示.

圖3 FCFS與遺傳算法對比圖

由圖3結果可以得知遺傳算法相對于FCFS算法不僅在推出時刻上進行了優化，同時對起飛跑道也做出了合理的分配，在減少了航班延誤時間的同時增加了起飛跑道的利用率.

4 結 語

本文研究了多跑道機場的離場航班調度問題，在考慮離場航班排序和跑道分配的條件下建立了以航班總延誤時間最小為目標的優化模型，采用遺傳算法對模型進行求解并將最終結果與FCFS算法作比較，發現了使用遺傳算法求解得到的航班總延誤明顯減少，且跑道分配更加合理，提高了場面運行效率.