吳 維, 魏 明*, 葉志堅, 孫 博

(1.中國民航大學民航航班廣域監(jiān)視與安全管控技術重點實驗室, 天津 300300； 2.中國民航大學空中交通管理學院, 天津 300300)

由于各個航班的航空器型號(決定尾流)和跑道運行模式對間隔影響差異,當機場的飛機流量迅速增加時,如果不通過進離場航班的排序與調度(flight arrivals and departures scheduling problems,FADSP),必然出現(xiàn)航空器在終端區(qū)的大面積擁堵與延誤問題。與傳統(tǒng)排序問題不同,隨著航班運行環(huán)境和運行規(guī)則的變化,FADSP具有獨特的運行特征,具體表現(xiàn)在:①新運行標準和安全間隔的發(fā)生變化；②多跑道混合運行模式并存；③涉及多種競爭性資源限制,尤其管制工作負荷帶來影響。該問題是一個非確定性多項式(non-deterministic polynomial,NP-hard)難題,為此,很多學者針對該問題進行了研究以提升機場中跑道資源的有效利用,提升運行效率。

目前,針對FADSP的中外研究按照跑道使用主要劃分為單、多跑道,進場、離場以及進離場混合；目標函數(shù)分為:單、多目標；約束條件分為:確定和不確定。張兆寧等[1-2]研究一類多跑道運行模式、替代航路的FADSP,以減航班延誤為目標；Lieder等[3]研究了不同運行模式下(相關和獨立運行)的多跑道FADSP；張啟錢等[4]根據(jù)新的尾流間隔標準和多跑道屬性差異構建一類FADSP,追求管制員工作負荷和產(chǎn)生延誤成本最??；Bae等[5]研究了一類離場航班的多目標FADSP,引入飽和度以降低排序方案可能引起的總延誤成本增加；Sureshkumar等[6]針對不同跑道構建FADSP的動態(tài)規(guī)劃模型,平衡機場容量和航班延誤之間關系；S?lveling等[7]構建了FADSP的兩階段隨機規(guī)劃模型；張軍峰等[8]考慮管制運行約束、跑道容量和航跡預測,研究不同時間窗的進場FADSP；Sam[9]等研究了繁忙機場進離場動態(tài)優(yōu)化的多目標FADSP；戴喜妹等[10]、周雨凡等[11]探討了不確定因素引起的交通量猛增下的FADSP；Faye[12]研究綜合考慮著陸航空器著陸時間、跑道可用性和間隔標準的FADSP; 張建同等[13]和張軍峰等[[14]分別探討了基于優(yōu)先級和復合分派規(guī)則的FADSP；王莉莉等[15]、馬園園等[16]和張軍峰等[17]研究了多機場協(xié)同下的FADSP。在算法設計方面,針對大規(guī)模的規(guī)劃問題求解主要采用滾動規(guī)劃時間窗啟發(fā)式方法[1,3-4],動態(tài)規(guī)劃方法[2,12]、分支定界算法[6-8]、近似啟發(fā)式算法[5,9,14-15]、蟻群算法[13]、遺傳算法[10-11,16]、模擬退火[17]。

綜上可知,現(xiàn)有研究主要不足在于:①現(xiàn)有FADSP均是假設航班的進離場跑道固定已知,較少涉及航班的不同跑道分配方案對FADSP的影響；②現(xiàn)有FADSP忽略了相鄰跑道距離較近時,可能導致兩個跑道無法同時進行航空器進離場的影響；③現(xiàn)有FADSP缺少分析管制員工作負荷導致跑道容量限制給排序結果帶來的影響以及不同類型機型對跑道占用時間的影響。為此,研究一類考慮相鄰跑道干擾的多目標FADSP,以航班延誤和跑道利用效率為目標,綜合考慮管制員可以調配每個時段進離場航空器總量限制。根據(jù)問題特征,設計該問題的NSGA-II,定義染色體編碼、產(chǎn)生初始種群的啟發(fā)式算法、遺傳操作等。最后,結合某機場的實際數(shù)據(jù),給出最佳排序方案并進行模型的參數(shù)靈敏度分析,從而驗證模型和算法的有效性。

1 FADSP的多目標數(shù)學規(guī)劃模型構建

1.1 問題描述

某機場在一段時間內有多個進離場航班,每個航班的計劃時間、到達或離開、機型(尾流時間和跑道占用時間)提前可以預知,考慮管制員的最大管制負荷以及相鄰跑道之間航班運行干擾性,將它們分配給一條或多條跑道依次進離場,確定全部航班的實際起飛或降落時間,同時追求跑道的利用效率最大化以及航班延誤最少。根據(jù)問題特征,建立FADSP的多目標混合整數(shù)數(shù)學規(guī)劃模型,尋找其Pareto最優(yōu)解,從機場和乘客角度揭示不同優(yōu)化方案對利益均衡性的影響。

不失一般性,研究的前提假設條件包括:①可以獲取某段時間機場的進離場航班、機場跑道運行模式與管制負荷；②同一個航班不能同時被分配給兩條跑道,一條跑道不能同時起飛或降落兩個航班,不考慮復飛等起降特情；③航班進離場排序不受航班滑行排隊的影響；④不考慮隨機干擾影響航班不能正常起飛或降落。

1.2 數(shù)學模型

如表1所示,給出FADSP的相關符號變量定義,據(jù)此描述該數(shù)學模型的目標函數(shù)和約束條件,如下所示。

表1 變量定義和數(shù)學符號Table 1 Variable definition and symbols

1.2.1 目標函數(shù)

從機場和乘客角度,探討航班進離場的延誤時間、跑道作業(yè)分配之間最佳指派耦合關系,其中,機場方面關心跑道利用效率最高(空閑時間最少),用Z1表示；乘客方面關注航班總延誤最少,用Z2表示。

(1)

(2)

1.2.2 約束條件

(1)航班指派跑道約束,即每個航班只能分配給一個跑道完成起降過程。

(3)

(2)跑道上航班起降順序約束,即:每個航班進離場過程只被指派給一條跑道,同時一條跑道同一時間只能完成一個航班起降運行。

(4)

(5)

(3)避免子回路約束。

?i,j∈F;?r∈R

(6)

(4)某跑道完成相鄰航班進離場運行的時間約束,即前續(xù)航班進離場運行的結束時間(即實際開始時間、跑道占用時間和尾流時間之和)不早于其后續(xù)航班進離場運行的開始時間。

(7)

(5)某航班進離場的計劃和實際時間之間最大延誤約束。

(8)

(6)相鄰跑道運行模式的干擾約束,即如果相鄰跑道之間距離較近采用相關運行模式,當某跑道的航班進離場運行時,相鄰跑道的航班進離場運行必須提前或者滯后一定時間。

?i,j∈F;?r,k∈R

(9)

(7)基于管制工作負荷確定的各個時段跑道容量約束,包括每個時段的起飛、到達和總起飛降落航空器數(shù)量。

h∈H;?r∈R

(10)

?i∈F};h∈H;?r∈R

(11)

0|?i∈F};h∈H;?r∈R

(12)

2 NSGA-II算法設計

非支配排序遺傳算法(non-dominated sorted genetic algorithm-Ⅱ，NSGA-Ⅱ),其特征在于包含快速非支配排序、擁擠度和擁擠度比較三個算子,不僅降低了算法的復雜度,而且保持了種群的多樣性。鑒于NSGA-Ⅱ的容易使用、原理簡單等優(yōu)點,已經(jīng)被推廣應用在交通、經(jīng)濟和工程等領域,是多目標進化基準算法之一。

借鑒NSGA-II求解FADSP的成熟思路[11,17],設計求解問題的啟發(fā)式算法,給出了染色體編碼方案,設計了產(chǎn)生初始種群構造算法,并給出了具體算法過程。

2.1 染色體編碼

用二維向量U=(U1,U2)刻畫FADSP的一個解,其中，U1=(u1,u2,…,uF),任意元素ui表示進離場航班i被分配的跑道號；在U2=(uF+1,uF+2,…,u2F),任意元素ui表示進離場航班i-F開始使用跑道的實際時間。例如,一個染色體 ={112222 7:30 7:40 7:30 7:40 7:40 7:50} 涉及6個航班(F1～F6)和3個跑道(R1～R3),將其可以解碼為F1、F2被分配給R1,時間為7:30、7:40；F3、F4被分配給R2,時間為7:30、7:40；F5、F6被分配給R3,時間為7:40、7:50。

2.2 產(chǎn)生初始種群的啟發(fā)式算法

當FADSP的多個航班被分配給同一或相關聯(lián)跑道時,若這些航班的跑道占用時間窗重疊,其造成這個解不可行。因此,隨機產(chǎn)生的染色體很難是可行個體。鑒于此,構造算法生成若干可行個體,組成初始種群,具體步驟如下。

步驟2對航班F″,設置可行初始跑道集合R，令i=1。

步驟4i=i+1。若i≤|F|,轉至步驟3；否則,算法結束。

2.3 非劣排序和擁擠距離排序

2.3.1 非劣排序

步驟1設Sx表示某個解?x∈P所支配的個體集合,nx表示某個解?x∈P所支配的個體數(shù)量,令Sx=?和nx=0。對任意兩個解?q,x∈P,若q>x,則Sx=Sx∪{q}；否則,nx=nx+1。

步驟2產(chǎn)生的新一代種群為Q,當Q=?,令xrank=1和i=1,其中xrank為變量x的非支配排序值,滿足F1={x|nx=0,?x∈P}。

步驟3對任意?x∈Fi的?q∈Sx,令nq=nq-1。若nq=0,qrank=i+1且Q=Q∪{q}。

步驟4如果Q≠?,i=i+1且Fi=Q,轉步驟3；否則,算法結束。

2.3.2 擁擠距離

2.3.3 選擇算子

為使Pareto解均勻散布,對任意兩個個體,當它們的非支配排序差異時,偏好序號低的個體,否則優(yōu)先選取擁擠距離小的個體,即: ①i>j當且僅當irankD(xj)。

2.4 算法流程

步驟1設置算法參數(shù),包括:染色體數(shù)N、迭代次數(shù)Niter以及遺傳操作概率等。

步驟2隨機產(chǎn)生第t=0代初始種群P0。

步驟3在第t代,對種群Rt內的若干個體進行選擇、變異和交叉操作,生成下一代子代種群Qt,將其與父代種群合并,即Rt=Pt∪Qt。

步驟4對Rt的2N個體,計算它們的非支配序和擁擠距離,按照一定規(guī)則選取較好個體,當個體數(shù)量達到N時,將它們組成新種群Pt+1。

步驟5當t=t+1,若t≥Niter,算法迭代結束,輸出結果；否則,返回步驟3。

3 算例分析

某機場在7:00—9:00期間有123個航班進離場,主要涉及輕、中型機兩種機型,其中，進場72班次,離場51班次。根據(jù)全部航班的計劃時間,圖1刻畫全部進離場航班占用跑道的數(shù)量隨著時間變化而波動(差異較大),最少和最多分別為2條和11條,平均數(shù)為5.4條。若該機場跑道數(shù)不滿最大需求,按照現(xiàn)有航班計劃時間,部分時段的航班就會被延誤。為了減少航班的大面積延誤,必須通過航班的跑道分配和進離場時刻協(xié)調優(yōu)化,使每條跑道在各個時段的進離場航班數(shù)相對均衡。

圖1 全部進離場航班占用跑道的數(shù)量時變關系Fig.1 Time varying relationship between the number of occupied runways and all inbound and outbound flights

表2 不同跑道數(shù)下的模型結果對比Table 2 Comparison of model results under different runway numbers

(1)當且僅有1條跑道時,由于沒有相鄰跑道之間干擾,兩個模型的結果一致。

(2)當2條以上跑道時,隨著跑道數(shù)增加時,對于無相鄰跑道干擾的FADSP,由于某個跑道可以不受干擾銜接兩個相鄰進離場航班,故跑道空閑時間總保持為零；同時,跑道數(shù)的增加讓更少航班的進離場計劃時刻調整,故航班的延誤時間逐步減少。

(3)對于考慮相鄰跑道干擾的FADSP,由于跑道空閑時間包含干擾時間,故其不為零；另外,當跑道數(shù)增加時,被干擾跑道的分配進離場航班數(shù)減少,這引起跑道的空閑時間也逐漸減少。同理,該模型的航班延誤時間也隨著跑道數(shù)量增加而減少。

(4)當相鄰跑道距離較近時,為保障航空器運行間隔受擾動跑道的需要增大運行時間間隔導致部分時間無法提供航班進離場服務,需要延長時間才能使全部航班飛機起飛或降落,這導致航班的延誤時間增加。因此,雖然考慮相鄰跑道干擾的FADSP比傳統(tǒng)問題的延誤時間增加,但更加符合實際管制運行過程。

以5條跑道為例,全部跑道采用混合運行模式,找到6個FADSP的Pareto解,航班延誤時間的上下限為1 968 min和2 208 min,跑道空閑時間的上下限為39 min和61 min。如圖2所示,隨著跑道的空閑時間減少,航班的延誤時間增加。這是因為更多的航班進離場時刻需要調整,才能充分使用跑道資源,計算結果符合直觀分析。圖3給出了優(yōu)化前后全部進離場航班占用跑道數(shù)的對比分析。從圖3可知，在優(yōu)化前,部分時刻的多個航班同時進離場導致所需要的跑道數(shù)遠超過實際,因而引起航班大面積延誤；進一步地,各個時段所需要的跑道數(shù)量波動變化比較大,部分時段跑道資源不夠,部分時段跑道資源閑置；優(yōu)化后,通過調整部分航班的進離場時刻,各個時段進離場航班數(shù)相對穩(wěn)定,一方面減少航班延誤,另一方面提升跑道利用效率。圖4進一步給出了優(yōu)化前后各個時段航班延誤時間的對比,與圖3的分析一致,從圖4中可知，優(yōu)化前,采用單跑道完成全部航班進離場,這些航班的延誤發(fā)生時間是進離場航班數(shù)量大于所需占用跑道數(shù)量時,若需求大于供給時,這些航班的延誤隨著時間往后推移可能呈現(xiàn)擴大趨勢，否則該趨勢縮??；優(yōu)化后,在多跑道運行模式下,協(xié)調全部航班的跑道分配和進離場時刻,可以極大地減少航班延誤。

圖2 Pareto解的不同目標之間變化關系Fig.2 The changing relationship among different goals of Pareto solution

圖3 優(yōu)化前后各個時段進離場航班占用跑道數(shù)量對比Fig.3 Comparison the number of runways occupied by flights in different periods before and after optimization

圖4 優(yōu)化前后各個時段航班延誤時間的對比Fig.4 Comparison flight delay time in different periods before and after optimization

4 結論

考慮相鄰跑道干擾的多目標FADSP,將進離場的航班分配給不同跑道,綜合考慮多跑道運行模式下航空器尾流影響、管制工作負荷、航空器安全間隔和航班最大延誤等約束,確定每個航班的起飛或降落時間,尋求跑道分配和進離場航班排序之間最佳資源匹配關系,同時兼顧追求航班延誤最少與跑道利用效率最大兩個目標。得到如下結論。

(1)隨著跑道的空閑時間減少,航班的延誤時間增加。這是因為更多的航班進離場時刻需要調整,才能充分使用跑道資源。

(2)當跑道數(shù)增加時,跑道的空閑時間和航班的延誤時間均隨之減少。這是因為無干擾跑道的分配進離場航班數(shù)量隨跑道數(shù)量增加而增加,這些跑道運行彼此獨立航班運行互不干擾,這引起跑道的空閑時間也逐步減少。同理,跑道數(shù)量的增加可以無需調整時刻完成航班進離場,故航班的延誤時間減少。

(3)當相鄰跑道距離較近時,若一個跑道正在進行航空器起飛或者著落時,受擾動跑道的此段時間禁止進離場,故該需要更多的時間才能使全部航班起飛或降落,這引起航班的延誤時間增加。

然而,本文模型假設進離場航班的預計起飛或降落時間是確定的,沒考慮地面保障資源、滑行路徑、天氣等約束導致的不確定性。因此,如何考慮相關不確定因素,研究隨機航班起飛或降落時間的FADSP是一個未來值得的研究方向。