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

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

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

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

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

1 研究背景

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

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

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

2.1 排序模型設(shè)計

min(rj-r1)

目的一：全部航班Tj總和最?。?/p>

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

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

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

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

表1 變量描述

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

EOBT：預(yù)計撤輪擋時刻，航空公司也稱其為開車時刻。飛機(jī)在停機(jī)坪停放時為避免非正常移位，在飛機(jī)前放置輪擋。機(jī)長收到推出指令后，由機(jī)組人員將輪擋撤掉，飛機(jī)可以正常滑行。

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

SOBT：計劃離港時刻，是在沒有客觀因素的影響下，飛機(jī)正點起飛的時間。

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

①EOBT。

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

表2 EOBT計算方法

表3 TOBT申請席位分類及申請依據(jù)

在參與排序時考慮的優(yōu)先順序為TOBT(流量席位)>TOBT(塔臺)>TOBT(航空公司)>EOBT>SOBT。

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

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

⑤CTO：航班飛越流量控制點時刻。

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

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

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

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

圖1 受控航班排序流程圖

3.1 NSGAII算法航班排序流程圖

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

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

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

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

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

圖2 NSGAII算法流程圖

偽代碼：

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

F=[]#集合F

forpinP:#對于種群P中每個個體p

sp=[]#集合sp

np=0#np為0的個體

forqinP:#對于P中個體q

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

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

else ifp

np=np+1#則把np加1

ifnp=0:#如果該個體的np為0

p_rank=1 #則該個體為Pareto為第一級

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

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

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

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

Q[]#集合Q

forpinF[i]:#對F中的個體排序

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

np=np-1#每個個體減1

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

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

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

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

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

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

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

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

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

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

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

偽代碼：

defcrowding_distance_assignment(I)#擁擠距離算法

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

foriinI:#對于I中的每個個體i

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

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

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

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

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

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

3.4 精英策略選擇算子

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

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

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

(2)t=0;

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

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

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

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

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

圖3 NSGAII算法圖示

4 可行性分析

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

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

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

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

圖4 不同算法下撤輪擋時刻分析對比圖

圖5 不同算法下起飛時間總和對比圖

5 結(jié)論

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