面向場面運行效率提升的離場航班調度優(yōu)化

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

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

1 引言

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

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

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

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

2.1 問題描述

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

2.2 模型建立

假設調度時間段內離場航班集合為F,非受控離場航班集合為FN,受控離場航班集合為FC,起飛跑道集合為R。

2.2.1 模型假設

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

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

2.2.2 目標函數

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

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

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

(1)

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

(2)

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

(3)

式中:α為受控離場航班延誤權重

2)最大化跑道容量

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

(4)

3)最小化跑道分配

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

(5)

2.2.3 約束條件

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

1)跑道唯一性約束

調度時間段內每架離場航班只允許分配一條起飛跑道,即

(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)為尾流間隔約束,限制同一跑道起飛的前后航班需要保持對應的尾流間隔,約束(9)和約束(10)判斷航班是否處于同一跑道,當航班i和航班j都分配給同一條跑道時,yij為1,否則為0。

3)時間窗約束

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

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

(11)

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

(12)

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

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

(13)

5)其它變量/參數約束

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

(14)

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

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

(15)

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

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

(16)

vi∈{1,2}

(17)

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

(18)

3 算法設計

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

3.1 算法流程

步驟 1:確定模型相關參數;

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

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

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

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

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

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

3.2 算法實現

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

根據文獻[8],將將離場航班的最大延誤時間設置為40分鐘,航班最大位置轉換約束為3。

2)編碼與解碼

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

3)遺傳算子

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

3.3 算法性能評價

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

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

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

(19)

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

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

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

(20)

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

3)超體積(Hyper Volume,HV)

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

(21)

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

4 實例驗證

4.1 實驗設計

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

表1 部分離場航班算例

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

4.2 結果分析

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

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

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

圖2 種群進化過程指標值變化趨勢

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

圖3 不同策略下三個目標函數值

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

圖4 調度時間段內兩種策略航班的起飛次序

5 結論

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