面向航班延誤場景的機位預(yù)分配模型及算法研究

王鑫晨, 呂增威,2, 魏振春,2, 張 浩

(1.合肥工業(yè)大學 計算機與信息學院,安徽 合肥 230601; 2.安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心,安徽 合肥 230601; 3.飛友科技有限公司,安徽 合肥 230031)

0 引 言

近年來,隨著中國民航業(yè)的迅猛發(fā)展,旅客需求及機場數(shù)量不斷增加,飛機已成為主要的運輸選擇之一。機位是機場的關(guān)鍵資源,是乘客上下飛機和維護飛機的重要場所,高效地利用停機位資源可以提高機場的容量和服務(wù)效率。如何在機位資源有限條件下為到港的每架航班分配合適的停機位,以提升乘客滿意度和實現(xiàn)機場的服務(wù)效率,被稱為機位分配[1]。機位分配問題多年來一直是一個熱門的研究課題[2-3],是航空公司運營和管理的核心環(huán)節(jié)。

在機位分配研究中,現(xiàn)有文獻大部分研究普適性更高場景下的機位分配問題,以保證機場的正常運行,少部分學者研究了航班延誤場景下的機位分配問題。針對航班延誤場景下航班時刻表易出現(xiàn)擾動問題,文獻[4]提出了新的二元整數(shù)規(guī)劃模型來解決機位再分配問題,該模型將乘客換乘的成功率作為目標函數(shù)進行評估。為解決機場航班延誤問題,文獻[5]提出了一種具有較高魯棒性的機位分配模型,以最小化機位空間時間為目標,并利用雙流國際機場的數(shù)據(jù)進行仿真驗證,結(jié)果表明所提模型穩(wěn)定性優(yōu)于現(xiàn)有模型。然而在航班延誤場景下,現(xiàn)有研究大多以最小化機位空間時間為目標來解決機位沖突問題,較少考慮航班沖突概率與機位空閑時間的密切關(guān)系。最小化航班沖突概率可以更有效地避免因航班延誤造成的預(yù)分配機位變更問題,使得機位分配方案具有更高的魯棒性和抗延誤性,也可大幅降低機位再分配的難度。

針對機位分配問題,現(xiàn)有文獻大部分采取精確算法、啟發(fā)式算法等算法來求解,較少采用深度強化學習方法。文獻[6]將停機位分配問題建模為馬爾可夫決策模型,提出了基于策略梯度的機位分配算法來求解該問題。由于深度強化學習技術(shù)的迅猛發(fā)展,已經(jīng)有大量學者采用深度強化學習方法來解決機場領(lǐng)域的優(yōu)化問題。針對大型機場航班的離港管理問題,文獻[7]將該問題建模為馬爾可夫決策過程,提出了一個強化學習模型來解決該問題,并選取世界上最繁忙的機場之一肯尼迪國際機場進行仿真驗證。文獻[8]以機場貨運資源優(yōu)化為目標,將深度強化學習技術(shù)應(yīng)用于機場貨運業(yè)務(wù)的仿真模型開發(fā),提出了將深度強化學習與機場貨運業(yè)務(wù)仿真模型相結(jié)合的決策支持系統(tǒng)框架。

針對現(xiàn)有研究的不足,本文首先建立了航班延誤場景下的停機位分配模型,并將其建模為馬爾可夫決策模型,提出基于深度強化學習的機位分配算法進行求解,以解決航班延誤場景下的預(yù)分配機位變更問題。

1 系統(tǒng)模型

1.1 模型參數(shù)定義

設(shè)進離港航班集合為U={1,2,…,N},N為航班數(shù)量;停機位集合為G={1,2,…,M},M為停機位數(shù)量。航班信息包括計劃到港時刻、計劃離港時刻、航班型號、上下機旅客人數(shù);停機位信息包括停機位的數(shù)量及其屬性等。采用變量xik表示航班i與停機位k的分配關(guān)系,當航班i被分配至停機位k中,則xik=1;否則xik=0。ui、vi分別代表航班i計劃到港時刻和計劃離港時刻,mi表示航班i的機型,gk表示停機位k的大小屬性。設(shè)li為航班i的屬性,若航班i為國際航班,則li=1;若航班i為國內(nèi)航班,則li=0。同理,ok為機位k的屬性,若ok=1,則機位k僅供國際航班?？?否則ok=0。

1.2 預(yù)分配約束條件

為保證航班安全到港,需要充分考慮機位分配過程中的安全要求規(guī)則、運行規(guī)則等信息,本文考慮為航班分配機位所需滿足的約束條件如下:

xik+xjk≤1, ?Rij=1,?i,j=1,…,N, ?k=1,…,M

(1)

Tjk=(uj-vi)yijk

(2)

(3)

lixik=ok, ?i=1,…,N,?k=1,…,M

(4)

?k=1,…,M

(5)

(gk-mi)xik≥0, ?i=1,…,N,?k=1,…,M

(6)

|Cik-Djl|≥βxikxjlzkl

(7)

|Djl-Dik|≥βxikxjlzkl

(8)

|Cjl-Cik|≥βxikxjlzkl

(9)

式(1)為魯棒性約束。定義同機位兩架連續(xù)航班之間的沖突概率大于q,則這兩架航班不可分配到同一機位,該約束能有效避免可能發(fā)生的機位占用沖突。對于分配至同一機位上的兩架航班i和j,pij表示航班i與航班j可能面臨的機位沖突概率[9],并引入Rij表示航班i與航班j的機位沖突概率pij與q的大小關(guān)系,若pij≥q則Rij=1;否則Rij=0。

式(2)為同機位空閑時間定義,其中Tjk表示機位k中航班j與緊前航班i的空閑時間,若航班i與航班j停靠同一機位k,且航班i是航班j的前驅(qū)航班,則yijk=1;否則yijk=0。

式(4)為停機位區(qū)域約束。

式(5)是唯一性約束,即航班進港時必須為其分配停機位,且僅可分配至一個停機位。

式(6)為機型匹配約束。

式(7)為出入沖突約束,其中β為避免沖突所需的安全時間間隔,若機位k與機位l為相鄰機位,則zkl=1;否則zkl=0。Cik表示航班i進入機位k的時刻,即Cik=uixik;Djl表示航班j離開機位l的時刻,即Djl=vjxjl。

式(8)和式(9)分別為雙入和雙出沖突約束。

1.3 預(yù)分配目標函數(shù)

惡劣天氣、航班延誤和航班取消等干擾在機場運營中屢見不鮮,可能會出現(xiàn)機位占用沖突使得復雜的機位預(yù)分配計劃被打亂,并可能導致嚴重的后果?，F(xiàn)有研究主要通過設(shè)置同機位最小安全時間間隔約束以避免機位沖突,然而同機位連續(xù)航班間的空閑時間并不能較準確地反映兩架航班之間的機位沖突。故本文根據(jù)機位沖突概率理論增加了機位沖突概率最小化優(yōu)化目標,該機位預(yù)分配模型不但可以大幅提升旅客的滿意度,而且具有較好的抗延誤特性。

1.3.1 最小化機位沖突概率

由于惡劣天氣時常出現(xiàn),航班延誤現(xiàn)象經(jīng)常發(fā)生,建立具有較高魯棒性的機位分配方案非常重要。機位沖突概率可以更準確地表達同機位兩航班在延誤場景下可能存在的沖突概率大小,進而可以通過調(diào)整機位沖突概率以避免沖突。因此,本文以最小化機位沖突概率為第1個優(yōu)化目標,即

(10)

1.3.2 最大化乘客靠橋率

乘客滿意度對于機位分配的結(jié)果尤為重要。航班降落到達機場時,離港和到港乘客會更偏向于較短的步行距離以及等待時間。由于航班被分配至近機位時,乘客的步行距離更短,乘客的滿意度會更高。相反,若航班被分配至遠機位,乘客須乘坐擺渡車到達停機位或返回行李寄存處,乘客滿意度較低。本文以最大化乘客靠橋率作為第2個優(yōu)化目標,即

(11)

其中:Gn為近機位的集合;bi、hi分別為從航班i進港和從航班i離港的旅客人數(shù)。

1.3.3 組合優(yōu)化目標

根據(jù)上述對優(yōu)化目標以及約束條件的闡述,本文綜合考慮了機場及旅客利益,以最大化乘客靠橋率和最小化機位沖突概率為組合優(yōu)化目標。組合優(yōu)化目標表示如下:

s.t.式(1)～式(9)

其中,W為權(quán)重系數(shù),根據(jù)每個目標的重要性,對不同數(shù)據(jù)組合的多個實驗進行分析,最終確定更合適的權(quán)重系數(shù)值。

2 基于強化學習的機位和分配算法

本文提出的優(yōu)化問題屬于NP-hard問題[10],由于約束條件較多,局部最優(yōu)解之間高度離散。以往的研究大多采取傳統(tǒng)算法進行求解,然而傳統(tǒng)算法從一個局部最優(yōu)解探索到另一個局部最優(yōu)解非常困難,因此容易陷入局部最優(yōu)。深度強化學習算法極其適合于解決復雜順序決策問題[11],然而由于基于行動者-評估家(actor-critic,AC)框架的深度強化學習算法收斂較慢,本文引入異中的概念,即異步優(yōu)勢動作評價(asynchronous advantage actor-critic,A3C)算法。A3C算法是基于AC框架的異步訓練方法,由于多智能體并行與環(huán)境交互學習動作策略,因此收斂速度較快。

2.1 馬爾可夫決策過程建模

強化學習算法中有3個關(guān)鍵因素需要確定,分別為狀態(tài)空間、動作空間和立即獎勵的定義。

1) 狀態(tài)空間。定義在時間步t的狀態(tài)空間St=〈B(t),Gpro,E(t),H(t)〉。其中:B(t)表示當前時間步t各停機位仍需被占用的時間;Gpro表示各停機位的屬性,分別包含遠近屬性、大小屬性和國際國內(nèi)屬性;E(t)表示在時間步t的進離港時刻信息;H(t)表示時間步t的航班屬性信息,分別包含第t架航班的登機人數(shù)、下機人數(shù)、大小屬性和國際國內(nèi)屬性。

2) 動作空間。動作空間A描述的是在時間步t時智能體可采取的動作at(at∈A)的集合。其中,at∈{1,2,…,M}表示航班t必須從集合{1,2,…,M}中選取一個動作,即必須?？壳覂H可?？恳粋€停機位。智能體可采取的動作at需根據(jù)約束條件進行縮減。

3) 立即獎勵。智能體每執(zhí)行一個動作,就會獲得一個立即獎勵r。立即獎勵應(yīng)與優(yōu)化目標有關(guān),故預(yù)分配模型在時間步t的立即獎勵rt表示為:

(1-W)yitkpit

(12)

2.2 基于異步優(yōu)勢動作評價的機位預(yù)分配算法

為求解本文問題,本文在非并行A2C(adrantage actor-critic)算法基礎(chǔ)上提出了一種基于異步優(yōu)勢動作評價的機位預(yù)分配算法(gate assignment algorithm based on asynchronous advantage actor-critic,GABA3C)。非并行A2C算法基于AC框架,僅含有1個Actor網(wǎng)絡(luò)和1個Critic網(wǎng)絡(luò),智能體與環(huán)境互動以學習最優(yōu)的策略。而本文所提GABA3C算法設(shè)置了1個全局網(wǎng)絡(luò)和多個AC結(jié)構(gòu),每個智能體即AC結(jié)構(gòu)并行與環(huán)境進行互動學習動作策略,并將學習到的梯度反饋給全局網(wǎng)絡(luò),由全局網(wǎng)絡(luò)更新自身參數(shù),因此學習效率更高、收斂速度更快,這是本文所提算法的改進之處和創(chuàng)新點。A3C算法引入了優(yōu)勢函數(shù)A(s,a)[12],表明智能體在當前狀態(tài)下采取行動a后所具有的優(yōu)勢值。優(yōu)勢函數(shù)定義如下:

A(s,a)=rt+γrt+1+…+γn-1rt+n-1+γnV(s′)-V(s)

(13)

其中,V(s)和V(s′)的值是通過Critic網(wǎng)絡(luò)學習所得到的。各個線程中的Actor網(wǎng)絡(luò)損失函數(shù)定義如下:

(14)

在A3C結(jié)構(gòu)中,Actor和Critic網(wǎng)絡(luò)采用n步TD(temporal difference)誤差法[13]學習動作概率函數(shù)和值函數(shù)。在本算法的學習方法中,n步TD誤差的計算是通過初始狀態(tài)的狀態(tài)估計值V(s0)與n步后的估計值的差來實現(xiàn)的,即

e=r0+γr1+γ2r2+…+γn-1rn-1+γnV(sn)-V(s0)

(15)

其中,γ為折扣因子。TD誤差反映了Actor網(wǎng)絡(luò)中所選行為的好壞,Critic網(wǎng)絡(luò)損失函數(shù)定義如下:

(16)

在計算TD誤差后,A3C結(jié)構(gòu)中的每個Worker網(wǎng)絡(luò)不直接更新其網(wǎng)絡(luò)權(quán)值,而是用其計算出的梯度更新Global網(wǎng)絡(luò)的參數(shù)。更新公式如下:

θ=θ+αa(dθ+θ′lgπ(a|s;θ′)A(s,a))

(17)

(18)

其中:θ為Global網(wǎng)絡(luò)中Actor網(wǎng)絡(luò)的權(quán)值;θ′為Worker網(wǎng)絡(luò)中Actor網(wǎng)絡(luò)的權(quán)值;θv為Global網(wǎng)絡(luò)中Critic網(wǎng)絡(luò)的權(quán)值;θv′為各個Worker網(wǎng)絡(luò)中Critic網(wǎng)絡(luò)的權(quán)值;αa和αc分別為Actor和Critic網(wǎng)絡(luò)的學習率。

GABA3C算法偽代碼如下:

輸入:航班信息表及機位占用信息

輸出:機位分配結(jié)果

初始化t←1,ep←1;

while ep<=EP-MAX do

初始化Global網(wǎng)絡(luò)中Actor參數(shù)為θ,Critic參數(shù)為θv。初始化AC結(jié)構(gòu)中Actor參數(shù)θ′←θ,Critic參數(shù)θv′←θv;

tstart=t;

初始化梯度dθ←0和dθv←0;

初始化環(huán)境狀態(tài)st;

whilest不是終止狀態(tài) andt-tstart≠tmaxdo

根據(jù)Worker網(wǎng)絡(luò)中的策略π(at|st;θ′)選擇動作at,即第t架航班選擇at號機位?？?

獲得立即獎勵rt和新狀態(tài)st+1,執(zhí)行t←t+1;

end

ifst為終止狀態(tài)

R←0;

else ifst為非終止狀態(tài)

R←V(st,θv′);

fori∈{N-1,…,1}

R←ri+γR;

計算Actor梯度:dθ←dθ+θlgπ(ai|si;θ′)A(si,ai);

end for

梯度dθ和dθv計算完成后,通過式(17)、(18)更新Global網(wǎng)絡(luò)中的θ和θv;

ep←ep+1;

end

策略網(wǎng)絡(luò)πθ擬合后,將初始狀態(tài)s0輸入到πθ中,進行N次迭代,得到預(yù)分配的機位分配結(jié)果。

3 仿真分析

3.1 參數(shù)設(shè)置

本節(jié)介紹基于異步優(yōu)勢動作評價的機位預(yù)分配算法參數(shù)設(shè)置。本實驗設(shè)置場景實例SCE-1,具體參數(shù)如下:航班數(shù)量N=42,機位數(shù)量M=17,最小安全時間間隔β=3 min,沖突概率p=0.16。設(shè)置最大迭代次數(shù)EP-MAX=10 000,Worker網(wǎng)絡(luò)數(shù)量為3。Actor和Critic都設(shè)置為全連接神經(jīng)網(wǎng)絡(luò),學習率分別為0.001和0.002。設(shè)置折扣因子γ為0.9。航班起飛延誤中,兩正態(tài)分布的均值和方差分別為μ11=0.255,σ11=6.403以及μ12=15.330,σ12=14.962;航班到達延誤分布的均值μ2=0.175,方差σ2=7.849。

3.2 預(yù)分配仿真結(jié)果及對比分析

在仿真實驗中,利用我國某中型機場的實際運行數(shù)據(jù)進行模型仿真與算法實現(xiàn)。為了驗證所提GABA3C算法的性能,本文進行了一系列仿真,來評估本文的GABA3C算法性能,并與自適應(yīng)并行遺傳算法(adaptive parallel genetic algorithm,APGA)[14]、近端策略優(yōu)化(proximal policy optmization,PPO)算法以及深度Q網(wǎng)絡(luò)(deep Q-network,DQN)算法進行對比。針對不同權(quán)重系數(shù),在場景實例SCE-1下采用4種算法運行20次獲得目標數(shù)據(jù),見表1所列。本文以W=0.4作為機位預(yù)分配模型的權(quán)重系數(shù)。

本文在訓練過程中記錄每代的總獎勵值,即目標函數(shù)值,為GABA3C算法訓練的目標函數(shù)值隨迭代次數(shù)變化關(guān)系,如圖1所示,由圖1可知GABA3C算法訓練效果顯著。

圖1 GABA3C算法的收斂性能

由于機位預(yù)分配的目標優(yōu)化模型是一個NP-hard問題,采用GABA3C算法來尋找最優(yōu)解,得到的停機位分配結(jié)果用甘特圖表示,如圖2所示。圖2中:0～10號機位為近機位;11～16號機位為遠機位,10、15、16號機位僅供國際航班使用;其余機位供國內(nèi)航班使用,每架航班都標注了航班號。

圖2 機位分配甘特圖

根據(jù)表1和圖2可以發(fā)現(xiàn),GABA3C算法求得的解在乘客靠橋率方面已達到63.78%,乘客的滿意度得以提升。另外,機位沖突總概率也較小,僅僅為1.025,可以有效避免因航班延誤造成的機位預(yù)分配結(jié)果變更問題。

由表1可知,當權(quán)重系數(shù)為0.4時,在機位沖突概率方面,GABA3C算法獲得的解分別比APGA、PPO、DQN算法低23.5%、10.0%、17.4%,故所提算法能夠有效避免因航班延誤造成的機位變更問題;同時,在近機位乘客分配率方面,GABA3C算法獲得的解分別比APGA、PPO、DQN算法高5.7%、4.6%、5.8%,故本文算法能夠較好地提高旅客的滿意度。為了驗證本文所提算法在各種變化場景下的適用性,本節(jié)新增2組不同機場實際運行數(shù)據(jù)的場景實例(SCE-2、SCE-3)對本文算法進行分析,其中SCE-2場景實例中具體參數(shù)設(shè)置如下:航班數(shù)量N=30,機位數(shù)量M=15,沖突概率p=0.16,最小安全時間間隔β=4 min;SCE-3場景實例中具體參數(shù)設(shè)置如下:航班數(shù)量N=38,機位數(shù)量M=14,沖突概率p=0.16,最小安全時間間隔β=3 min。

為保證公平性,3組場景實例沖突概率p都設(shè)置相同,最小安全時間間隔由不同機場規(guī)則要求確定。

針對3組不同場景實例,分別采用4種算法運行20次繪制盒狀圖,如圖3所示。

圖3 不同場景實例下4種算法的目標函數(shù)值比較

由圖3可知,3組不同場景實例下,GABA3C算法獲得的解的最大值、最小值、中位數(shù)均比其他3種算法更高,故本文所提算法在不同場景下的適用性較好,所獲得解的質(zhì)量更高,具有很強的尋優(yōu)性能和較強的穩(wěn)定性。

為了測試算法改進前后的性能增益,本文針對3組不同場景實例分別設(shè)置消融實驗,分別采用非并行A2C算法和GABA3C算法運行20次,獲得最優(yōu)目標數(shù)據(jù)見表2所列。

表2 不同場景實例下的消融實驗結(jié)果

由表2可知,在不同場景實例下,相比于非并行A2C算法,GABA3C算法獲得的解在3個評價指標上的值更優(yōu)。因此,本文所提算法能夠更好地避免因航班延誤造成的機位沖突問題的同時,還能夠顯著提升旅客的滿意度。

4 結(jié) 論

針對航班延誤場景下因航班延誤帶來的預(yù)分配機位變更問題,本文提出了具有良好抗延誤特性的機位預(yù)分配模型,并將其建模為馬爾可夫決策模型,提出了基于異步優(yōu)勢動作評價的機位預(yù)分配算法來求解該問題。為驗證所提算法在各種變化場景下的適用性,本文設(shè)置了3組場景實例。仿真實驗表明,本文所提GABA3C算法在提升旅客滿意度的同時,還可以有效避免因航班延誤造成的機位沖突問題。