基于遺傳算法的離場航班時刻優化

左杰俊，王 強，鐘 琦，劉 懿

(1.成都佰行航空技術服務有限公司，四川 成都 610093；2.中國民用航空局第二研究所，四川 成都 610041；3.西南地區空中交通管理局，四川 成都 610202)

1 引言

航班延誤是制約世界航空業發展的問題之一，目前，世界各國已采取各種措施減少航班延誤。我國許多機場通過增加跑道數量和其它方法來提高容量，從而減輕航班延誤。由于機場跑道是空中交通系統中最關鍵的單元之一，因此在一定時間內，充分利用跑道資源可以有效緩解航班延誤。另外，進場和離港航班調度在減少航班延誤方面也起著重要作用，因此合理的航班調度對確保航班安全，提高資源利用率，減少延誤損失以及改善航班狀況都有重大意義。在我國，主要采用FCFS(先到先得)原則安排進離港航班。事實表明，FCFS并不是最大程度地利用現有機場容量的最佳策略[1]。從20世紀初開始，國內外學者就進行了航班優化調度問題的研究。Dear和Sherif提出了一種在高密度終端區對飛機進行排序和調度的方法。這種方法被稱為約束位置偏移(CPS)，并對其有效性進行了測試[2]。Abela等描述了解決飛機著陸時間安排問題的兩種方法。他們還將此問題表述為混合整數程序(MIP)，并為其解決方案開發了分支定界算法[3]。Saraf和Slater開發了一種新的高效調度算法，該算法使用組合優化技術來找到在特定參考點上飛機的最佳到達飛機序列和最佳到達時間，前提是指定了從FCFS序列位置切換的最大數量，該算法還能夠根據航空公司的偏好對飛機進行優先級排序，并在沿著飛機路線的所有扇區之間最佳地分配延誤[4]。Hancerliogullari等人研究了以同時最小化飛機著陸和起飛的總加權延誤為目標的多跑道混合模式下的飛機排序問題。它可以被建模為準備時間、目標時間和截止時間的并行機器調度問題[5]。與其它發達國家相比，我國空中交通流量管理的研究起步較晚。張妍考慮間隔約束建立了固定航線的進港航班排序模型[6]。侯亞偉以蕭山國際機場為例利用Anylogic建立機場場面運行仿真模型，通過模擬仿真，尋找某時段航班延誤的瓶頸環節，然后針對瓶頸環節對航班時刻進行優化[7]。張軍峰等人將多機場終端區視為一個系統，航班計劃視為與該系統相關的航班流，構建了多機場終端區進離場排序模型[8]。崔昳昕等人建立了單跑道機場進離港航班排序強化學習模型，并與先來先服務算法、蟻群算法進行比較[9]。李昂等人，以京津冀機場群為例，尋求最高航班正點率為目標，建立了機場群航班時刻優化模型[10]。

盡管學者們已經對航班排序優化方法進行了很多研究，但是它們仍然有不足之處。例如，某些模型是在理想情況下建立的，并未考慮天氣、空中交通管制、機場周圍環境等的實際情況。此外，大多數模型是針對單跑道或者簡單的把多跑道視為獨立運行的跑道，并不符合機場的實際運行情況。本文將機場場空側視為一個系統，考慮機場實際放行能力、和管制間隔建立了離港航班時刻優化模型。通過遺傳算法對模型進行求解，減少了航班延誤損失。并將優化后的航班計劃輸入AirTop進行仿真。仿真證明文中所提方法是正確的。

2 問題描述

近年來，隨著中國民航的飛速發展，場旅客運輸需求顯著增加，導致民航運輸機場尤其是大型樞紐機場在短時間內不能滿足航班流量增加的需求，隨之而來的是航班延誤的問題。中國民航的流量管理手段也開始從基于經驗的粗放型管理策略向基于科學技術的精細化管理策略轉變。因此，本文從機場運行角度出發考慮機場實際放行能力、空中交通管制間隔、航班調度難度等多種因素構建離港航班時刻優化模型，在保證安全的前提下合理安排離場航班，將總的航班延誤時間降到相對最低的水平。

為防止主動延誤發生，對機場歷史運行數據就行分析，提取相應時間段的容量值作為容量限制，以防止安排的航班量超出機場運行保障能力造成延誤。因此，本模型對連續時間區間長度為 5 分鐘、15分鐘、60分鐘的機場時刻容量進行限制。

航空公司的期望時刻有一個最大可接受的調整幅度，因為過大的調整會影響后續航段的飛行。同時，如果對航班的調整范圍過大，也會增加管制工作負荷。將優化后的航班時刻限定在某一范圍之內，不但符合實際情況，也可提高模型的求解效率。

3 航班時刻優化模型

3.1 模型構建

3.1.1 符號說明

f待優化航班，?f∈F

t0優化調整的時間片長度

ATD 實際離港時間

ETD 計劃離港時間

m待優化的航班f的數量

n可用的時刻數(以5分鐘為一個時刻則9：00-21：00有144個時刻)

aij航班i分配到第j個時刻時的延誤時間

bij航班i分配到第j個時刻時的時刻調整量

c5機場在5分鐘內的時刻容量

c15機場在15分鐘內的時刻容量

c60機場在60分鐘內的時刻容量

決策變量

(1)

3.1.2 目標函數

航班延誤時間最小為目標，建立如下目標函數

(2)

式中i=1，2，..，m，j=1，2，..，n。考慮到實際情況，在大多數情況下，實際到達時間幾乎不可能與預計時間一致，因此做出如下規定：實際起飛時間比預計起飛時間早或相等的情況視為延誤時間為0，模型建立如下。

(3)

式中ATDij為航班i分配到第j個時刻時的實際離港時間，ATDij=ATD0+j×t0，比如起始離港時間ATD0為9：00航班i分配到第3個時刻則此時航班i的實際離港時間為9：15，ETDi為航班i的計劃離港時間。

3.1.3 約束條件

航班時刻唯一性約束，為每一個航班分配有且僅一個時刻，式(4)中i∈(1，m)中任意整數，j=1，2，..n。

(4)

航班時刻調整范圍約束，式(5)中ATDi0為優化前航班i的實際離港時刻，i∈(1，m)中任意整數，j=1，2，..n，該約束目的是避免優化后的航班因調整過大而影響后續飛行任務，特別是對聯程航班意義重大。

(5)

機場容量約束，為了更好地使得航班計劃符合實際運行情況，制定更加精細化的航班計劃，本文將對連續時間區間長度為5分鐘、15分鐘以及60分鐘的容量進行限制。式(6)中i∈(1，m)中任意整數，j=1，2，..n，式(7)、(8)中式中i=1，2，..，m，k∈(1，n)中任意整數。

(6)

(7)

(8)

3.2 模型求解

航班時刻優化的實質是航班排序，對不同飛機對重新組合，使得總延誤時間或延誤成本最小。對于數據量不大的排序問題可以使用列舉法進行精確求解，也可以用數學規劃法快速求解，但針對航班時刻資源配置問題，維度大，復雜性高，屬于NP難題。鑒于此，本文采用遺傳算法進行求解，求解過程如下圖所示：

圖1 遺傳算法求解流程

3.3 遺傳算法步驟

步驟1：確定遺傳策略，包括種群數量n，選擇、交叉和變異的方法。同時，確定交叉概率和變異概率，以及其它遺傳參數；

步驟2：定義適應度函數f(x)；

步驟3：隨機產生初始化種群P；

步驟4：計算與航班隊列對應的染色體的目標函數；

步驟5：計算種群中個體的適應度值；

步驟6：在當前條件下尋找最優個體；

步驟7：判斷演化代數是否達到最大遺傳代數。

步驟8：采用輪盤賭選擇，通過單點交叉作圖法進行染色體的交叉操作；

步驟9：執行步驟4～步驟6；

步驟10：評估遺傳算法的效果；

步驟11：輸出最佳功能值，然后獲得最優航班序列。

4 實例分析

以上海虹橋國際機場為例，首先對上海虹橋國際機場離港航班歷史放行數據進行分析，分析結果如圖2-圖4。以每5分鐘為一個時間片，分析了00：00-14：00(UTC時間)共169個時間片的離港航班量，5分鐘內最大放行量為4架次，99%的時間片為超過3架次，可以認為5分鐘的放行能力為3架次。詳細分析方法見參考文獻[11]，用同樣的方法分別得到15分鐘的放行能力為7架次，60分鐘的放行能力為28架次。

圖2 上海虹橋國際機場60分鐘放行航班量

圖3 上海虹橋國際機場15分鐘放行航班量

圖4 上海虹橋國際機場5分鐘放行航班量

選取上海虹橋國際機場某日07：00-09：00共40個航班運行數據，按文中所提算法模型，設置種群規模200，最大進化代數200，變異概率0.4，優化結果如圖5，在43代收斂得到最優一代種群，優化前后航班序列信息如表1所示。

表1 優化前后航班信息

圖4 遺傳算法求解過程

從優化前后的結果可以看出，根據文中所提算法對40條航班數據進行優化，可以減少總延誤時間39%。優化前有32架次航班發生延誤，平均延誤24.7分鐘。優化后，發生延誤的航班減少為19架次，平均延誤15.05分鐘。

4.1 AirTop仿真驗證

考慮跑道離港容量利用AirTop對文中所提算法優化后的航班計劃進行仿真驗證，仿真航班信息和結果見表2所示。

表2 AirTop離港仿真航班計劃及結果

從上表結果可以看出，考慮跑道離港容量利用AirTop對遺傳算法優化后的航班計劃進行仿真，仿真得到40架次航班中延誤航班數量由之前的32架次減少到23架次，總延誤時間從原來的988分鐘減少到668.9分鐘，平均延誤時間從24.7分鐘減少到16.7分鐘。仿真結果表明文中所提航班時刻優化模型可以有效的對航班時刻資源進行優化配置，減少航班延誤時間。如果優化的數據增加，效果會更加明顯，可以更大程度的提高運行效率。

5 結論

本文研究了飛機排序問題(ASP)在空中交通流量管理中的應用，以最大程度地減少總延誤時間為目標。建立了基于機場實際放行能力的離場航班時刻優化模型，利用遺傳算法對模型進行求解，并運用AirTop仿真驗證了模型的有效性。以虹橋機場為例，優化結果表明文中所提方法可以減少離港延誤39%，且能夠減少延誤航班數量。該方法同樣可以應用于進港航班時刻優化算法的開發。