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

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

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

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

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

1 研究背景

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

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

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

2.1 排序模型設(shè)計

min(rj-r1)

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

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

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

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

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

表1 變量描述

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

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

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

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

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

①EOBT。

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

表2 EOBT計算方法

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

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

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

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

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

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

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

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

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

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集合中的個體進行排序

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ù)值大小對每個個體進行排序；

②對每個個體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進行升序排序

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

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

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

3.4 精英策略選擇算子

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

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

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

(2)t=0;

(3)通過錦標(biāo)賽法從Pt中選擇個體，進行交叉和變異重要操作，產(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分鐘，意味著航空公司能較快地組織旅客登機，提高航空公司的服務(wù)品質(zhì)，增加了旅客的出行滿意度。此方法優(yōu)化后其中共有十架飛機差值為0，改變航班的撤輪擋時刻較少，能減少管制員的工作負擔(dān)。圖5對此兩種算法下起飛時間總用時進行了對比，不難看出優(yōu)化后的45架飛機起飛序列總用時較FCFS算法共縮短了74分鐘，使飛機較快地離場起飛從而減少了延誤時間。

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

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

5 結(jié)論

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