左杰俊，王 強(qiáng)，鐘 琦，劉 懿

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

1 引言

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

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

2 問題描述

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

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

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

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

3.1 模型構(gòu)建

3.1.1 符號說明

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

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

ATD 實(shí)際離港時間

ETD 計劃離港時間

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

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

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

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

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

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

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

決策變量

(1)

3.1.2 目標(biāo)函數(shù)

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

(2)

式中i=1，2，..，m，j=1，2，..，n?？紤]到實(shí)際情況，在大多數(shù)情況下，實(shí)際到達(dá)時間幾乎不可能與預(yù)計時間一致，因此做出如下規(guī)定：實(shí)際起飛時間比預(yù)計起飛時間早或相等的情況視為延誤時間為0，模型建立如下。

(3)

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

3.1.3 約束條件

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

(4)

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

(5)

機(jī)場容量約束，為了更好地使得航班計劃符合實(shí)際運(yùn)行情況，制定更加精細(xì)化的航班計劃，本文將對連續(xù)時間區(qū)間長度為5分鐘、15分鐘以及60分鐘的容量進(jìn)行限制。式(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)化的實(shí)質(zhì)是航班排序，對不同飛機(jī)對重新組合，使得總延誤時間或延誤成本最小。對于數(shù)據(jù)量不大的排序問題可以使用列舉法進(jìn)行精確求解，也可以用數(shù)學(xué)規(guī)劃法快速求解，但針對航班時刻資源配置問題，維度大，復(fù)雜性高，屬于NP難題。鑒于此，本文采用遺傳算法進(jìn)行求解，求解過程如下圖所示：

圖1 遺傳算法求解流程

3.3 遺傳算法步驟

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

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

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

步驟4：計算與航班隊(duì)列對應(yīng)的染色體的目標(biāo)函數(shù)；

步驟5：計算種群中個體的適應(yīng)度值；

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

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

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

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

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

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

4 實(shí)例分析

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

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

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

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

選取上海虹橋國際機(jī)場某日07：00-09：00共40個航班運(yùn)行數(shù)據(jù)，按文中所提算法模型，設(shè)置種群規(guī)模200，最大進(jìn)化代數(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ù)進(jìn)行優(yōu)化，可以減少總延誤時間39%。優(yōu)化前有32架次航班發(fā)生延誤，平均延誤24.7分鐘。優(yōu)化后，發(fā)生延誤的航班減少為19架次，平均延誤15.05分鐘。

4.1 AirTop仿真驗(yàn)證

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

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

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

5 結(jié)論

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