考慮相鄰跑道干擾的多目標(biāo)進(jìn)離場航班排序優(yōu)化模型

吳 維, 魏 明*, 葉志堅(jiān), 孫 博

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

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

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

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

1 FADSP的多目標(biāo)數(shù)學(xué)規(guī)劃模型構(gòu)建

1.1 問題描述

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

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

1.2 數(shù)學(xué)模型

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

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

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

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

(1)

(2)

1.2.2 約束條件

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

(3)

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

(4)

(5)

(3)避免子回路約束。

?i,j∈F;?r∈R

(6)

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

(7)

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

(8)

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

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

(9)

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

h∈H;?r∈R

(10)

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

(11)

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

(12)

2 NSGA-II算法設(shè)計(jì)

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

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

2.1 染色體編碼

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

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

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

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

步驟4i=i+1。若i≤|F|,轉(zhuǎn)至步驟3；否則,算法結(jié)束。

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

2.3.1 非劣排序

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

步驟2產(chǎn)生的新一代種群為Q,當(dāng)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,轉(zhuǎn)步驟3；否則,算法結(jié)束。

2.3.2 擁擠距離

2.3.3 選擇算子

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

2.4 算法流程

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

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

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

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

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

3 算例分析

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

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

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

(1)當(dāng)且僅有1條跑道時(shí),由于沒有相鄰跑道之間干擾,兩個(gè)模型的結(jié)果一致。

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

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

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

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

圖2 Pareto解的不同目標(biāo)之間變化關(guān)系Fig.2 The changing relationship among different goals of Pareto solution

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

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

4 結(jié)論

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

(1)隨著跑道的空閑時(shí)間減少,航班的延誤時(shí)間增加。這是因?yàn)楦嗟暮桨噙M(jìn)離場時(shí)刻需要調(diào)整,才能充分使用跑道資源。

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

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

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