單跑道連續(xù)離場(chǎng)條件下的航班排序優(yōu)化方法

黃 濤，馬 雙，黃研清,袁 媛

(沈陽(yáng)航空航天大學(xué) a.通用航空產(chǎn)業(yè)發(fā)展研究中心;b.民用航空學(xué)院;c.航空制造工藝數(shù)字化國(guó)防重點(diǎn)學(xué)科實(shí)驗(yàn)室，沈陽(yáng) 110136)

近幾年，民航運(yùn)輸產(chǎn)業(yè)在我國(guó)迅猛發(fā)展，飛行流量的需求呈上升趨勢(shì)，而被民航飛機(jī)可利用的飛行區(qū)域相對(duì)有限，造成特定空域和特定時(shí)段內(nèi)機(jī)場(chǎng)、航空公司和管制員三方?jīng)_突。雖然我國(guó)已采取縮小垂直間隔、引進(jìn)新導(dǎo)航管理方式來(lái)改善流量控制局面，但仍不足以滿(mǎn)足我國(guó)飛行流量使用需求。此背景下引入?yún)f(xié)同決策系統(tǒng)CDM(Collaborative decision making system)用于我國(guó)空中交通流量管理工作中。航空公司、機(jī)場(chǎng)與空中交通管制部門(mén)之間通過(guò)決議計(jì)劃互換、數(shù)據(jù)同享共同提高交通管理效力,確保ATC、航空公司與機(jī)場(chǎng)獲得關(guān)于航班的及時(shí)精確信息,以幫助加快決議計(jì)劃進(jìn)程,使用協(xié)作技術(shù)改善空中交通流量管理方式,進(jìn)而達(dá)到多方受益的理想狀態(tài)，為航行信息的數(shù)據(jù)管理提供有利依據(jù)。20世紀(jì)末美國(guó)針對(duì)協(xié)同技術(shù)做了一項(xiàng)測(cè)試，測(cè)試表明利用協(xié)同決策技術(shù)可大大降低航班的總體延誤時(shí)間。2014年，中國(guó)蘇南機(jī)場(chǎng)實(shí)施了CDM二級(jí)運(yùn)營(yíng)管理；2017年底，華北空管局完善了多機(jī)場(chǎng)放行協(xié)同決策系統(tǒng)，由此說(shuō)明協(xié)同決策系統(tǒng)在我國(guó)的發(fā)展進(jìn)入新階段。

航班排序問(wèn)題的研究文獻(xiàn)較多。文獻(xiàn)[1]加入了飛機(jī)在跑道滑行路線產(chǎn)生沖突的考慮因素，對(duì)離港航班的推出時(shí)間用遺傳算法進(jìn)行了單目標(biāo)優(yōu)化。航班離港計(jì)劃的本質(zhì)是優(yōu)化航班離港順序，削減飛機(jī)滯留時(shí)間，充分利用跑道時(shí)隙。該研究主要設(shè)置單一目標(biāo)進(jìn)行優(yōu)化，然而，航班起飛調(diào)度問(wèn)題涉及多個(gè)目標(biāo)點(diǎn)和利益點(diǎn)，所以有必要將多目標(biāo)優(yōu)化問(wèn)題引入到航班排序中。文獻(xiàn)[2]采用融合回溯算法，考慮航路流控的情況后對(duì)離港航班進(jìn)行排序；文獻(xiàn)[3]采用兩步算法與多跑道程序相結(jié)合的方法，第一步以最小吞吐量為目標(biāo)，第二步以每架航班最小化延遲為目標(biāo)，減少飛機(jī)在跑道運(yùn)行中的延誤，具有較好的可行性。文獻(xiàn)[4]考慮連續(xù)航班的影響，對(duì)離場(chǎng)航班用NSGAII算法進(jìn)行多目標(biāo)排序，得出最優(yōu)解集的航班起飛時(shí)間序列。

以上文獻(xiàn)雖然針對(duì)航班排序問(wèn)題提出很多解決方法，但有幾點(diǎn)不足。一方面有的文獻(xiàn)對(duì)于離場(chǎng)航班的排序沒(méi)有考慮到連續(xù)航班的影響，也有沒(méi)考慮流量控制的影響。例如文獻(xiàn)[2]中雖然考慮到流量控制情況但其算法模型在優(yōu)化過(guò)程中對(duì)航班進(jìn)行了部分舍棄，這會(huì)給航空公司收益帶來(lái)?yè)p失；文獻(xiàn)[4]中的多目標(biāo)算法模型沒(méi)有加入受流量控制影響的情況，問(wèn)題考慮不全面。另一方面由引言前部分可知，隨著計(jì)算機(jī)技術(shù)的發(fā)展和民航運(yùn)輸需求的劇增，協(xié)同決策流量管理系統(tǒng)將會(huì)得到廣泛使用。然而，以往關(guān)于協(xié)同交通管理的研究文獻(xiàn)大多基于關(guān)鍵技術(shù)、管理方法和少數(shù)航路選擇的優(yōu)化。協(xié)同交通管理模式下的航班排序研究文獻(xiàn)太少，說(shuō)明協(xié)同技術(shù)還不成熟。本文在協(xié)同流量管理系統(tǒng)背景下，對(duì)單跑道機(jī)場(chǎng)連續(xù)離場(chǎng)航班進(jìn)行排序。此外，增加流量控制因素，既能防止空中交通擁堵，又減少地面延誤現(xiàn)象的發(fā)生，提高了航空公司的運(yùn)行質(zhì)量，有較好的可實(shí)施性。

1 研究背景

協(xié)同流量管理系統(tǒng)提供了各種飛行相關(guān)信息,包括出發(fā)和目的地機(jī)場(chǎng)、預(yù)計(jì)和實(shí)際起飛時(shí)間、預(yù)計(jì)和實(shí)際到達(dá)時(shí)間、飛行路線等。除此之外為解決容流平衡問(wèn)題，系統(tǒng)中加入航班過(guò)點(diǎn)時(shí)刻，即每個(gè)航班到達(dá)航路上某點(diǎn)的時(shí)刻，過(guò)點(diǎn)時(shí)刻可由系統(tǒng)計(jì)算出來(lái)，通過(guò)篩選可以看到在特定時(shí)間段內(nèi)航班通過(guò)同一航路點(diǎn)的時(shí)刻。但流量控制出現(xiàn)時(shí)，會(huì)導(dǎo)致通過(guò)同一航路點(diǎn)中的一些航班發(fā)生沖突，對(duì)于這些航班需進(jìn)行重新排序以維持正?？罩薪煌ㄖ刃颉３份啌鯐r(shí)刻是航空公司組織乘客登機(jī)的依據(jù)，計(jì)算撤輪擋時(shí)刻由起飛時(shí)刻和滑行時(shí)間反推出來(lái)，但結(jié)果不是精確的，如果將過(guò)點(diǎn)時(shí)刻與撤輪擋時(shí)刻結(jié)合進(jìn)行排序決策，既能減緩容流不平衡問(wèn)題又能滿(mǎn)足流控需求。

2 協(xié)同流量管理下航班排序方案

針對(duì)單跑道機(jī)場(chǎng)連續(xù)離場(chǎng)航班，考慮在航班受流控影響的情況下，達(dá)到對(duì)航班的EOBT(預(yù)計(jì)撤輪擋時(shí)刻)優(yōu)化的目的，此次優(yōu)化以CTO(航班飛越流量控制點(diǎn)時(shí)刻)為基準(zhǔn)。假設(shè)航路上某一點(diǎn)流控影響、流控影響時(shí)間段已知。根據(jù)流控信息找出受流控影響的航班集合，先對(duì)這些航班的CTO(航班到達(dá)流控點(diǎn)時(shí)刻)進(jìn)行排序，排序后將獲得這些受控航班新的到達(dá)流控點(diǎn)時(shí)刻，繼而推算出撤輪擋時(shí)刻，最后將全部航班進(jìn)行多目標(biāo)排序。

2.1 排序模型設(shè)計(jì)

min(rj-r1)

目的一：全部航班Tj總和最??；

目的二：全部航班總序列用時(shí)最短。

約束條件一：因?yàn)槭轻槍?duì)單跑道機(jī)場(chǎng)建立的模型，也就是同一時(shí)刻跑道上只允許同時(shí)起飛一架航班，且任意兩架相鄰航班的間隔必須大于等于機(jī)場(chǎng)跑道離港航班容量的允許范圍，如果是應(yīng)用在多跑道機(jī)場(chǎng)可分別對(duì)每一條跑道進(jìn)行排序；

約束條件二：相鄰航班之間應(yīng)滿(mǎn)足最小間隔。

將約束條件加入受控航班排序中，不在此處描述。變量具體描述見(jiàn)表1。

表1 變量描述

2.2 協(xié)同流量管理系統(tǒng)相關(guān)說(shuō)明

EOBT：預(yù)計(jì)撤輪擋時(shí)刻，航空公司也稱(chēng)其為開(kāi)車(chē)時(shí)刻。飛機(jī)在停機(jī)坪停放時(shí)為避免非正常移位，在飛機(jī)前放置輪擋。機(jī)長(zhǎng)收到推出指令后，由機(jī)組人員將輪擋撤掉，飛機(jī)可以正?；?。

TOBT：目標(biāo)撤輪擋時(shí)刻，流量管理系統(tǒng)通過(guò)前站航班的起飛報(bào)中的到港時(shí)間和最小過(guò)站時(shí)間推算而得。

SOBT：計(jì)劃離港時(shí)刻，是在沒(méi)有客觀因素的影響下，飛機(jī)正點(diǎn)起飛的時(shí)間。

2.3 排序方案數(shù)據(jù)的輸入

①EOBT。

②TOBT：在協(xié)同流量管理系統(tǒng)中TOBT有三種(見(jiàn)表3)。

表2 EOBT計(jì)算方法

表3 TOBT申請(qǐng)席位分類(lèi)及申請(qǐng)依據(jù)

在參與排序時(shí)考慮的優(yōu)先順序?yàn)門(mén)OBT(流量席位)>TOBT(塔臺(tái))>TOBT(航空公司)>EOBT>SOBT。

③流量控制信息：流量控制時(shí)間段、流控點(diǎn)、受影響的機(jī)場(chǎng)、航班線路等。

④SLIP：飛機(jī)滑行時(shí)間即從停機(jī)位滑行到跑道端的用時(shí)。

⑤CTO：航班飛越流量控制點(diǎn)時(shí)刻。

2.4 受控航班排序流程設(shè)計(jì)

對(duì)受控航班進(jìn)行排序前先根據(jù)當(dāng)前流控情況設(shè)置參數(shù)，其中n為受影響航班架次；a分鐘內(nèi)b架次航班；最小航班間隔c分鐘。按順序進(jìn)行先進(jìn)行第一個(gè)航班CTO與第二個(gè)航班CTO的比較，直到滿(mǎn)足最小間隔后，如若不滿(mǎn)足c分鐘則每比較一次加一分鐘。其次繼續(xù)進(jìn)行比較是否滿(mǎn)足航班間隔在a分鐘內(nèi)的條件，如果滿(mǎn)足，則第一個(gè)受控航班和第二個(gè)受控航班的CTO排序完成；若是不滿(mǎn)足，在a分鐘內(nèi)只實(shí)行第一個(gè)航班。接著對(duì)第三個(gè)航班和第二個(gè)航班進(jìn)行比較，按上述步驟循環(huán)遍歷全部航班。具體流程見(jiàn)圖1。

3 協(xié)同流量管理下航班多目標(biāo)排序算法流程

以上闡述了協(xié)同流量管理下航班排序的整個(gè)思想以及對(duì)受控航班進(jìn)行排序的方法，以下為航班多目標(biāo)排序思想。具有精英策略的NSGAII設(shè)計(jì)了快速非支配算子、擁擠度算子和精英保留策略算子，為了避免丟失最優(yōu)解，父代中的優(yōu)秀個(gè)體被保留并直接傳遞給子代。因此我們采用帶精英策略的非支配排序遺傳算法進(jìn)行設(shè)計(jì)。

圖1 受控航班排序流程圖

3.1 NSGAII算法航班排序流程圖

3.2 快速非支配排序算子設(shè)計(jì)

NSGAII中對(duì)種群P中的每一個(gè)個(gè)體p設(shè)有兩個(gè)參數(shù)np和sp。np為在種群中支配個(gè)體p的解的個(gè)體數(shù)目，sp為種群內(nèi)被個(gè)體p所支配的個(gè)體的集合，具體步驟如下。

(1)找到種群中全部np=0的個(gè)體并將他們存儲(chǔ)到當(dāng)前集合F1中；

(2)對(duì)于當(dāng)前集合F1中的每個(gè)個(gè)體i，考察它所支配的個(gè)體集si，將集合si中的每個(gè)個(gè)體l執(zhí)行nl-1 ；

(3)如nl-1=0則將個(gè)體l存入另一個(gè)集H中。最后，將F1作為第一級(jí)非支配個(gè)體集合，把H作為當(dāng)前集合，重復(fù)上述步驟，直到種群內(nèi)的所有個(gè)體被分級(jí)。

圖2 NSGAII算法流程圖

偽代碼：

def fast_nondominated_sort(P): #對(duì)種群P進(jìn)行快速非支配排序

F=[]#集合F

forpinP:#對(duì)于種群P中每個(gè)個(gè)體p

sp=[]#集合sp

np=0#np為0的個(gè)體

forqinP:#對(duì)于P中個(gè)體q

ifp>q： #如果p支配q,把q添加到Sp列表中

sp.append(q)#則將q加入到sp集合中

else ifp

np=np+1#則把np加1

ifnp=0:#如果該個(gè)體的np為0

p_rank=1 #則該個(gè)體為Pareto為第一級(jí)

F1.append(p)#將p加入到F1集合中

F.append(F1)#將F1集合中的元素添加到F集合中

i=0#循環(huán)開(kāi)始

whileF[i]:#對(duì)F中個(gè)體循環(huán)

Q[]#集合Q

forpinF[i]:#對(duì)F中的個(gè)體排序

forqinsp:#對(duì)所有在Sp集合中的個(gè)體進(jìn)行排序

np=np-1#每個(gè)個(gè)體減1

ifnq=0:#如果該個(gè)體的支配個(gè)體數(shù)為0，則該個(gè)體是非支配個(gè)體，

q_rank=i+2#該個(gè)體Pareto級(jí)別為當(dāng)前最高級(jí)別加1，此時(shí)i初始值為0，所以要加2，

Q.append(q)#將序列q添加到集合Q中

F.append(Q)#將Q中元素添加到集合F中

i=i+1#再次循環(huán)

3.3 擁擠距離算子設(shè)計(jì)

在NSGAII遺傳算法中，擁擠度計(jì)算是保證種群多樣性的重要環(huán)節(jié)，具體步驟如下：

(1)對(duì)于每個(gè)個(gè)體i令擁擠距離di=0，i=1,2，…，N；

(2)對(duì)M個(gè)目標(biāo)的每個(gè)目標(biāo)函數(shù)fm:

①根據(jù)目標(biāo)函數(shù)fm的數(shù)值大小對(duì)每個(gè)個(gè)體進(jìn)行排序；

②對(duì)每個(gè)個(gè)體i，計(jì)算di=di+[fm(i+1)-fm(i-1)]，其中d1=dN=。

偽代碼：

defcrowding_distance_assignment(I)#擁擠距離算法

nLen=len(I) #I中的個(gè)體數(shù)量

foriinI:#對(duì)于I中的每個(gè)個(gè)體i

i.distance=0#初始化所有個(gè)體的擁擠距離

for objFun inM:#M為所有目標(biāo)函數(shù)的列表

I=sort(I,objFun)#按照目標(biāo)函數(shù)objFun進(jìn)行升序排序

I[0]=I[len[I]-1]=#對(duì)第一個(gè)和最后一個(gè)個(gè)體的距離設(shè)為無(wú)窮大，

foriinxrange(1,len(I)-2):#計(jì)算范圍為1到倒數(shù)第二個(gè)

#按照步驟中寫(xiě)的公式對(duì)每個(gè)個(gè)體進(jìn)行擁擠距離計(jì)算。

3.4 精英策略選擇算子

初始NSGA算法采用共享函數(shù)方法來(lái)保持物種多樣性，但該方法也存在不足。首先，多樣性的程度取決于參數(shù)值的選擇；第二，每個(gè)解都被拿來(lái)和其他解比較。而在NSGAII中加入了擁擠度算法和精英保留策略取替了上述方法。即將父代中優(yōu)秀的個(gè)體保留下來(lái)直接傳給子代，避免丟失最優(yōu)解。

3.5 主體循環(huán)部分

(1)隨機(jī)初始化開(kāi)始種群P，并對(duì)P進(jìn)行非支配排序，初始化每個(gè)個(gè)體的非支配序(即第幾級(jí))

(2)t=0;

(3)通過(guò)錦標(biāo)賽法從Pt中選擇個(gè)體，進(jìn)行交叉和變異重要操作，產(chǎn)生新一代子種群Qt；

(4)計(jì)算新種群的目標(biāo)函數(shù)obj值；

(5)通過(guò)合并Pt和Qt產(chǎn)生出組合種群Rt；

(6)對(duì)Rt采取非支配排序，通過(guò)擁擠度計(jì)算和精英保留策略找出N個(gè)個(gè)體，形成新一代的種群Pt+1(見(jiàn)圖3)；

(7)跳轉(zhuǎn)到步驟(3)并循環(huán)，直到滿(mǎn)足結(jié)束條件。

圖3 NSGAII算法圖示

4 可行性分析

選取協(xié)同流量管理系統(tǒng)中2019年10月23 日9：00到12：00通過(guò)航路點(diǎn)LJB的航班集合共45架，假設(shè)45架航班受到流量控制。排序后更新撤輪擋得到的結(jié)果見(jiàn)表4。

表4 受控航班排序算法下航班排序

利用圖1中的算法，結(jié)合流控信息，對(duì)45架受控航班排序得到符合流控信息的航班撤輪擋時(shí)刻和相應(yīng)的起飛時(shí)間。將受控航班排序算法應(yīng)用在協(xié)同流量管理系統(tǒng)中，當(dāng)已知一段時(shí)間內(nèi)某區(qū)域受到流控影響，輸入已知流控信息，即可得到新情況下后續(xù)航班過(guò)點(diǎn)時(shí)刻、撤輪擋時(shí)刻和起飛時(shí)刻，促使航班有序離港。此方法既考慮到流控的影響又可預(yù)防航路沖突，使整個(gè)排序結(jié)果更具時(shí)效性、準(zhǔn)確性和實(shí)用性。

對(duì)比FCFS算法結(jié)果見(jiàn)圖4和圖5。圖4結(jié)果表明優(yōu)化后的45架航班撤輪擋總用時(shí)較FCFS算法減少了54分鐘，總用時(shí)縮短了26%；同時(shí)用FCFS算法優(yōu)化后得到的每架航班撤輪擋時(shí)刻與優(yōu)化前的撤輪擋時(shí)刻差值總和為1 481分鐘，而用此方法優(yōu)化后的差值總和為612分鐘，意味著航空公司能較快地組織旅客登機(jī)，提高航空公司的服務(wù)品質(zhì)，增加了旅客的出行滿(mǎn)意度。此方法優(yōu)化后其中共有十架飛機(jī)差值為0，改變航班的撤輪擋時(shí)刻較少，能減少管制員的工作負(fù)擔(dān)。圖5對(duì)此兩種算法下起飛時(shí)間總用時(shí)進(jìn)行了對(duì)比，不難看出優(yōu)化后的45架飛機(jī)起飛序列總用時(shí)較FCFS算法共縮短了74分鐘，使飛機(jī)較快地離場(chǎng)起飛從而減少了延誤時(shí)間。

圖4 不同算法下撤輪擋時(shí)刻分析對(duì)比圖

圖5 不同算法下起飛時(shí)間總和對(duì)比圖

5 結(jié)論

針對(duì)協(xié)同交通流量管理系統(tǒng)中的航班飛行序列問(wèn)題，提出了將受控航班序列與NSGAII算法相融合的思想。此方法按照設(shè)置的兩個(gè)目標(biāo)的排序序列，將得到所有航班的撤輪擋時(shí)刻，將實(shí)際飛機(jī)撤輪擋時(shí)刻+飛機(jī)滑行時(shí)間=實(shí)際飛機(jī)起飛時(shí)刻，也就是通過(guò)此方法進(jìn)行排序可以同時(shí)得到飛機(jī)的撤輪擋時(shí)刻和起飛時(shí)刻，而且在排序過(guò)程中加入了流控影響因素，并將其融入到NSGAII算法設(shè)計(jì)中。當(dāng)協(xié)同流量管理系統(tǒng)中加入受控航班排序程序，通過(guò)系統(tǒng)上數(shù)據(jù)可以了解到關(guān)于本次飛行的各個(gè)關(guān)鍵信息，當(dāng)本架飛機(jī)受到流控影響時(shí)，通過(guò)對(duì)受控航班的過(guò)航路點(diǎn)時(shí)刻排序的更新，讓飛機(jī)駕駛員可以了解到本架飛機(jī)的處境，根據(jù)飛機(jī)當(dāng)前情況進(jìn)行靈活操作，可以減少航班延誤。此方法使排序結(jié)果更貼合實(shí)際、預(yù)防航路擁堵現(xiàn)象發(fā)生，進(jìn)而改善容流不平衡問(wèn)題。