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

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

1 引言

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

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

2 問題描述

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

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

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

3 航班時刻優(yōu)化模型

3.1 模型構(gòu)建

3.1.1 符號說明

f待優(yōu)化航班，?f∈F

t0優(yōu)化調(diào)整的時間片長度

ATD 實際離港時間

ETD 計劃離港時間

m待優(yōu)化的航班f的數(shù)量

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

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

bij航班i分配到第j個時刻時的時刻調(diào)整量

c5機場在5分鐘內(nèi)的時刻容量

c15機場在15分鐘內(nèi)的時刻容量

c60機場在60分鐘內(nèi)的時刻容量

決策變量

(1)

3.1.2 目標函數(shù)

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

(2)

式中i=1，2，..，m，j=1，2，..，n?？紤]到實際情況，在大多數(shù)情況下，實際到達時間幾乎不可能與預計時間一致，因此做出如下規(guī)定：實際起飛時間比預計起飛時間早或相等的情況視為延誤時間為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)中任意整數(shù)，j=1，2，..n。

(4)

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

(5)

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

(6)

(7)

(8)

3.2 模型求解

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

圖1 遺傳算法求解流程

3.3 遺傳算法步驟

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

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

步驟3：隨機產(chǎn)生初始化種群P；

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

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

步驟6：在當前條件下尋找最優(yōu)個體；

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

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

步驟9：執(zhí)行步驟4～步驟6；

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

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

4 實例分析

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

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

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

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

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

表1 優(yōu)化前后航班信息

圖4 遺傳算法求解過程

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

4.1 AirTop仿真驗證

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

表2 AirTop離港仿真航班計劃及結(jié)果

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

5 結(jié)論

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