何玉建,胡明華,*,袁立罡

(1. 南京航空航天大學(xué)民航學(xué)院,江蘇 南京 211106;2. 國家空管飛行流量管理技術(shù)重點實驗室,江蘇 南京 211106)

1 引言

隨著民航的快速發(fā)展,航空運輸業(yè)的需求也逐年迅速增長,隨之而來的航班延誤,終端區(qū)擁擠、場面滑行沖突等問題制約了空中交通的正常運行,如何在有限的空域容量內(nèi)滿足空中交通流量的需求是亟需解決的問題,機(jī)場作為航班運行保障的主體單位,其運行效率和保障水平很大程度上影響了空中交通運行整體水平,因此充分利用機(jī)場有限的資源,合理調(diào)度航班起降,有效提升航班服務(wù)保障是解決現(xiàn)階段民航發(fā)展過程中所遇到的問題的關(guān)鍵手段。目前我國大多數(shù)機(jī)場為多跑道配置,多跑道作為制約大型繁忙機(jī)場起降航班的重要瓶頸區(qū),科學(xué)調(diào)度航班流量對于促進(jìn)多跑道協(xié)同運行、提高機(jī)場運行效率、保障航班安全具有重要意義。

關(guān)于跑道調(diào)度問題國內(nèi)外積累了一定的研究成果,針對單跑道運行下航班排序,Desai[1]和?E?EN[2]以航班延誤最小為目標(biāo)函數(shù)建立了混合整數(shù)線性規(guī)劃模型。Malik采用多目標(biāo)動態(tài)規(guī)劃算法[3]、張軍峰采用多目標(biāo)帝國競爭算法[4]分別對跑道調(diào)度問題進(jìn)行求解。江灝改進(jìn)了已有文獻(xiàn)中評估航空公司延誤公平性的目標(biāo)函數(shù),滿足了不同利益相關(guān)方的需求[5]。針對多跑道運行條件下航班排序,Hancerliogullari將航班調(diào)度問題建模為并行的機(jī)器調(diào)度問題,并采用啟發(fā)式算法進(jìn)行求解[6]。Chandrasekar和王菲采用分支定界方法來優(yōu)化航班進(jìn)離場排序[7]。尹嘉男考慮了綠色機(jī)場發(fā)展理念,并將最小化環(huán)境污染作為優(yōu)化目標(biāo)函數(shù)之一[8]。針對多機(jī)場終端區(qū)運行條件下的進(jìn)離場交通流排序,馬園園提出了“航班滿意度”的概念[9],葛騰騰采用了改進(jìn)模擬退火算法對進(jìn)離場排序模型進(jìn)行求解[10]。Liu將兩階段無等待混合流水車間模型應(yīng)用于多機(jī)場調(diào)度問題[11],Zhong考慮了不同航班流向的延誤差異,設(shè)計了自適應(yīng)禁忌搜索算法對所建立的多目標(biāo)整數(shù)規(guī)劃模型進(jìn)行求解[13]。

已有研究針對跑道調(diào)度問題取得了一定的成果,但是并沒有考慮起飛跑道與停機(jī)位的位置關(guān)系,針對于航站樓位于兩條或者多條跑道中心的機(jī)場來說,盡量減少航班在場面的滑行時間對于提高場面運行效率至關(guān)重要,因此本文從減少場面運行時間角度來優(yōu)化離場航班排序。

2 多跑道離場航班調(diào)度優(yōu)化模型

2.1 問題描述

多跑道離場航班調(diào)度是指根據(jù)預(yù)期的離場交通流需求,考慮停機(jī)位,跑道配置,天氣因素等條件對離場航班起飛時間以及順序進(jìn)行優(yōu)化,優(yōu)化的同時要盡量滿足空管、機(jī)場以及航司的訴求,實現(xiàn)科學(xué)合理安排最優(yōu)起飛時間、離場順序以及跑道,使其調(diào)度時間段內(nèi)機(jī)場運行總效率最高,航班總延誤成本最小,航班調(diào)整次序變動最少的目的。

2.2 模型建立

假設(shè)調(diào)度時間段內(nèi)離場航班集合為F,非受控離場航班集合為FN,受控離場航班集合為FC,起飛跑道集合為R。

2.2.1 模型假設(shè)

1)研究時段內(nèi)的離場航班停機(jī)位信息和航班計劃起飛時間等信息是已知的;

2)航班離場排序過程中,每架航班只能分配一個時隙;

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

為了符合機(jī)場協(xié)同決策的理念,考慮了空管、機(jī)場和航司三方的利益訴求,從航班延誤、跑道運行能力以及跑道就近分配三個角度建立優(yōu)化目標(biāo)。

1)最小化離場航班總延誤

將所有離場航班按照是否受流控影響分為受控離場航班和非受控離場航班,受控離場航班延誤根據(jù)《民航航班正常性統(tǒng)計辦法》來計算,非受控航班延誤等于優(yōu)化起飛時間與計劃關(guān)艙門時間和標(biāo)準(zhǔn)地面滑行時間之和的差值的絕對值。

(1)

針對于受控航班,全國流量管理系統(tǒng)會以航班計劃為基礎(chǔ),依據(jù)流量管理措施和航班優(yōu)先級為受控航班分配計算起飛時間(Calculated Take Off Time,CTOT)。受控航班須在發(fā)布的計算起飛時間前后一定容差范圍內(nèi)起飛,根據(jù)《中國民航空管流量管理運行規(guī)則》:CTOT時隙容差分為一類和二類容差,基于容量管理的流量管理措施為一類容差,容差范圍為(-5,10)分鐘;基于間隔管理的流量管理措施為二類容差,容差范圍為(-3,3)分鐘,為了盡量保障受控航班符合CTOT運行,將受控航班離場延誤定義為優(yōu)化起飛時間與CTOT差值的絕對值

(2)

考慮到受控航班相比于非受控航班具有更大的優(yōu)先級,可以對受控離場航班的延誤賦予更大的權(quán)重,重點保障受控離場航班CTOT的準(zhǔn)點率,因此調(diào)度時間段內(nèi)離場航班總延誤定義為

(3)

式中:α為受控離場航班延誤權(quán)重

2)最大化跑道容量

將調(diào)度時間段內(nèi)所有起飛跑道容量最大作為目標(biāo)進(jìn)行優(yōu)化,它近似等于調(diào)度時間段內(nèi)最后一架起飛航班的優(yōu)化起飛時間與第一架離場航班的優(yōu)化起飛時間之差,即

(4)

3)最小化跑道分配

大多數(shù)機(jī)場都是遠(yuǎn)距平行跑道,航站樓位于兩條跑道中間或者一側(cè),停機(jī)位處于航站樓附近,為了降低場面運行時間,考慮離場航班機(jī)位與跑道之間的距離,以就近分配跑道原則作為優(yōu)化目標(biāo),即

(5)

2.2.3 約束條件

離場航班調(diào)度考慮的約束條件主要有:唯一性約束、尾流間隔要求、時間窗約束以及最大約束位置轉(zhuǎn)換約束。

1)跑道唯一性約束

調(diào)度時間段內(nèi)每架離場航班只允許分配一條起飛跑道,即

(6)

2)尾流間隔約束

φij+φji=1

(7)

(8)

yij≥ξir+ξjr-1

(9)

yij≤(ξir+ξjr)/2

?i,j∈F,且i≠j

(10)

約束(7)限制離場航班i和航班j前后順序的唯一性,約束(8)為尾流間隔約束,限制同一跑道起飛的前后航班需要保持對應(yīng)的尾流間隔,約束(9)和約束(10)判斷航班是否處于同一跑道,當(dāng)航班i和航班j都分配給同一條跑道時,yij為1,否則為0。

3)時間窗約束

由于受控航班和非受控航班在機(jī)場地面保障有所差異,因此將時間窗約束分為受控離場航班時間窗約束以及非受控離場航班時間窗約束,每架離場航班必須在規(guī)定的起飛時間窗內(nèi)完成起飛。

非受控離場航班優(yōu)化起飛時間應(yīng)當(dāng)不早于航班預(yù)計撤輪擋時間與無障礙滑行時間之和,不能晚于航班預(yù)計關(guān)艙門時間與計劃起飛時間與最大延誤時間之和,即:

(11)

受控離場航班的優(yōu)化起飛時間應(yīng)滿足在CTOT時隙容差范圍內(nèi)完成起飛,即

(12)

4)最大約束位置轉(zhuǎn)換約束(Maximum Position Shift, MPS)

為了降低管制員負(fù)荷及考慮航空公司的利益,設(shè)定航班優(yōu)化前后的調(diào)動次序不超過最大位置轉(zhuǎn)換約束,即

(13)

5)其它變量/參數(shù)約束

離場航班索引、跑道索引、離場航班初始起飛次序和優(yōu)化起飛次序均為正整數(shù),即

(14)

航班起飛先后關(guān)系判定輔助決策變量以及航班跑道分配輔助決策變量均為0-1離散變量,即

ξij,φij,yij∈{0,1}

(15)

受控離場航班CTOT時隙容差上/下界的取值集合、非受控離場航班和受控航班時隙容差類別的取值集合為

?={5,3},Δ={10,3}

(16)

vi∈{1,2}

(17)

受控離場航班延誤權(quán)重、非受控離場航班的最大延誤時間、尾流間隔、預(yù)計撤輪擋時間、計劃關(guān)艙門時間、標(biāo)準(zhǔn)地面滑行時間、不同機(jī)位與跑道的平均滑行時間、無障礙滑行時間、計劃/優(yōu)化起飛時間等均為非負(fù)值,即:

(18)

3 算法設(shè)計

跑道調(diào)度問題屬于典型的NP-hard問題,一般很難求解得到精確解,因此采用啟發(fā)式算法多目標(biāo)遺傳算法(NSGA-Ⅱ)對所建立的多目標(biāo)優(yōu)化模型進(jìn)行求解,該算法通過快速非支配排序以及擁擠距離排序可以得到綜合權(quán)衡多個優(yōu)化目標(biāo)的Pareto最優(yōu)解。

3.1 算法流程

步驟 1:確定模型相關(guān)參數(shù);

步驟 2:讀取航班信息、跑道信息、停機(jī)位信息;

步驟3:確定所有離場航班的起飛時間窗、以起飛時間窗作為基礎(chǔ)確定決策變量的上下界,隨機(jī)生成初始種群;

步驟4:解碼,確定離場航班的初始離場順序、離場時間;

步驟5:約束條件符合性檢驗。根據(jù)式(7)-(10)判斷種群內(nèi)個體是否滿足間隔要求,若滿足,根據(jù)目標(biāo)函數(shù)計算各個目標(biāo)函數(shù)的值,如果不滿足,則設(shè)置個體的目標(biāo)函數(shù)(M,M,M),其中M為任意大的正數(shù);

步驟6:執(zhí)行快速非支配排序以及擁擠距離計算,采用選擇、交叉和變異等遺傳算子操作,得到子代種群;父代種群和子代種群合并,執(zhí)行快速非支配排序,生成各層級Pareto前端,通過采用擁擠算子對所有可行解進(jìn)行擁擠距離排序,選取最優(yōu)個體組成新的父代種群,執(zhí)行種群進(jìn)化迭代過程;

步驟7:若算法滿足預(yù)先設(shè)定的終止條件(如達(dá)到最大進(jìn)化代數(shù)),輸出Pareto最優(yōu)解;若否,進(jìn)化代數(shù)加1,轉(zhuǎn)至步驟4。

3.2 算法實現(xiàn)

1)非受控航班時間窗約束與MPS約束

根據(jù)文獻(xiàn)[8],將將離場航班的最大延誤時間設(shè)置為40分鐘,航班最大位置轉(zhuǎn)換約束為3。

2)編碼與解碼

將每條染色體分為空間編碼片段和時間編碼片段,先將以時分秒形式的時間戳格式轉(zhuǎn)換為秒來表示,即將a時b分轉(zhuǎn)換成秒的轉(zhuǎn)換公式為:a×3600+b×60,根據(jù)離場航班的起飛時間窗,采用整數(shù)編碼的方式對離場航班的優(yōu)化起飛時間進(jìn)行時間編碼,空間編碼片段亦采用整數(shù)編碼對跑道號進(jìn)行編碼。

3)遺傳算子

在算法執(zhí)行過程中存在兩個階段的選擇,第一次采用二元錦標(biāo)賽選擇,第二次根據(jù)非支配分層以及擁擠距離度量的選擇方法,選擇的交叉算子為模擬二進(jìn)制交叉;采用的變異算子是多項式變異,由于采用整數(shù)編碼,因此在進(jìn)行多項式變異時候先按照實數(shù)值進(jìn)行突變,然后四舍五入進(jìn)行取整。

3.3 算法性能評價

從帕累托最優(yōu)解的收斂性和多樣性角度出發(fā),選取以下三個多目標(biāo)優(yōu)化算法性能評價指標(biāo)來評估模型解集的優(yōu)劣。

1)世代距離(Generational Distance,GD)

GD是常用于評價多目標(biāo)算法收斂性的指標(biāo),其值越小說明算法的收斂性越好,GD的計算式為

(19)

式中;w表示算法得到的帕累托前端中解的個數(shù),p表示目標(biāo)維數(shù);du表示算法中得到的帕累托前端中每個解距離真實帕累托前端的最近歐氏距離。

2)反轉(zhuǎn)世代距離(Inverted Generational Distance,IGD)

IGD可以反映多目標(biāo)算法收斂性以及解的多樣性,其值越小則算法的性能越好,IGD的計算式為

(20)

式中:q表示真實帕累托前端中解的個數(shù),ds表示真實帕累托前端中每個解距離算法得到的帕累托前端的最近歐氏距離。

3)超體積(Hyper Volume,HV)

HV表示算法獲得的非支配解與參照點圍成的目標(biāo)空間中區(qū)域的體積,HV值越大,說明算法的綜合性能越好。HV的計算式為

(21)

式中:δ(·)表示勒貝格測度,用來測量體積,Vk表示第k個點與參考點圍成的區(qū)域超體積。

4 實例驗證

4.1 實驗設(shè)計

選取國內(nèi)某大型機(jī)場2020年6月3日某個時間段內(nèi)的航班數(shù)據(jù)為例進(jìn)行仿真驗證,部分航班計劃如表1所示。

表1 部分離場航班算例

綜合考慮算法的運行時間和收斂效果,多次進(jìn)行仿真,最終得到的算法參數(shù)為:算法最大進(jìn)化代數(shù)為200;種群個體數(shù)為100;種群個體染色體長度為2|F|,交叉概率為1,變異概率為1/2|F|,分布指數(shù)為20。

4.2 結(jié)果分析

將基于先到先服務(wù)策略與本文所提的離場航班調(diào)度方法進(jìn)行對比, 如圖1為算法執(zhí)行結(jié)束得到的不同目標(biāo)函數(shù)在種群完成進(jìn)化時所得到的部分Pareto最優(yōu)解集。

圖1 種群進(jìn)化得到的部分Pareto最優(yōu)解

圖2為模型在進(jìn)化過程中不同評價指標(biāo)數(shù)值變化趨勢,可以看出隨著種群的不斷進(jìn)化,GD和IGD的數(shù)值逐漸降低并趨向于一致,HV值逐漸增大并最終趨于穩(wěn)定。

圖2 種群進(jìn)化過程指標(biāo)值變化趨勢

選取其中一個pareto最優(yōu)解進(jìn)行分析,如圖3所示,可以得到先到先服務(wù)(First Come First Serve, FCFS)策略下的航班總延誤為4049.16秒,優(yōu)化策略下的航班總延誤為1201.4秒,相比降低70.33%,FCFS策略下的跑道調(diào)度時間為2920.20秒,優(yōu)化策略下的跑道調(diào)度時間為1730秒,相比降低40.76%,FCFS策略下的航班總平均滑行時間為15033秒,而優(yōu)化策略下的時間為14655秒,相比降低了3%左右。因此優(yōu)化模型在降低航班延誤以及提升跑道容量方面效果顯著。

圖3 不同策略下三個目標(biāo)函數(shù)值

如果離場航班優(yōu)化起飛次序與計劃起飛次序偏差較大,則會增加管制員工作負(fù)荷,同時降低旅客滿意度。如圖4所示,基于優(yōu)化模型結(jié)果的航班起飛次序與FCFS策略安排的起飛次序變化均滿足MPS約束,因此符合實際管制運行的需要。

圖4 調(diào)度時間段內(nèi)兩種策略航班的起飛次序

5 結(jié)論

航班離港是空中交通運行的重要組成部分,為了提升場面運行效率,從時空角度出發(fā),考慮了尾流間隔、時間窗等約束,在已有文獻(xiàn)目標(biāo)函數(shù)的基礎(chǔ)上提出了以最小化跑道分配的多目標(biāo)離場航班調(diào)度模型,并采用多目標(biāo)遺傳算法進(jìn)行求解最優(yōu)解,以實例數(shù)據(jù)進(jìn)行仿真驗證,結(jié)果表明了相比FCFS策略,優(yōu)化后的航班延誤以及場面運行時間明顯得到降低,可以用于實際管制中的輔助決策。