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

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

0 引 言

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

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

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

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

1 系統(tǒng)模型

1.1 模型參數(shù)定義

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

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

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

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

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

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

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

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

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

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

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

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

1.3.1 最小化機(jī)位沖突概率

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

(10)

1.3.2 最大化乘客靠橋率

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

(11)

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

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

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

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

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

2 基于強(qiáng)化學(xué)習(xí)的機(jī)位和分配算法

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

2.1 馬爾可夫決策過(guò)程建模

強(qiáng)化學(xué)習(xí)算法中有3個(gè)關(guān)鍵因素需要確定,分別為狀態(tài)空間、動(dòng)作空間和立即獎(jiǎng)勵(lì)的定義。

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

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

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

(1-W)yitkpit

(12)

2.2 基于異步優(yōu)勢(shì)動(dòng)作評(píng)價(jià)的機(jī)位預(yù)分配算法

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

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

(13)

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

(14)

在A3C結(jié)構(gòu)中,Actor和Critic網(wǎng)絡(luò)采用n步TD(temporal difference)誤差法[13]學(xué)習(xí)動(dòng)作概率函數(shù)和值函數(shù)。在本算法的學(xué)習(xí)方法中,n步TD誤差的計(jì)算是通過(guò)初始狀態(tài)的狀態(tài)估計(jì)值V(s0)與n步后的估計(jì)值的差來(lái)實(shí)現(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)

在計(jì)算TD誤差后,A3C結(jié)構(gòu)中的每個(gè)Worker網(wǎng)絡(luò)不直接更新其網(wǎng)絡(luò)權(quán)值,而是用其計(jì)算出的梯度更新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′為各個(gè)Worker網(wǎng)絡(luò)中Critic網(wǎng)絡(luò)的權(quán)值;αa和αc分別為Actor和Critic網(wǎng)絡(luò)的學(xué)習(xí)率。

GABA3C算法偽代碼如下:

輸入:航班信息表及機(jī)位占用信息

輸出:機(jī)位分配結(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不是終止?fàn)顟B(tài) andt-tstart≠tmaxdo

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

獲得立即獎(jiǎng)勵(lì)rt和新?tīng)顟B(tài)st+1,執(zhí)行t←t+1;

end

ifst為終止?fàn)顟B(tài)

R←0;

else ifst為非終止?fàn)顟B(tài)

R←V(st,θv′);

fori∈{N-1,…,1}

R←ri+γR;

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

end for

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

ep←ep+1;

end

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

3 仿真分析

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

本節(jié)介紹基于異步優(yōu)勢(shì)動(dòng)作評(píng)價(jià)的機(jī)位預(yù)分配算法參數(shù)設(shè)置。本實(shí)驗(yàn)設(shè)置場(chǎng)景實(shí)例SCE-1,具體參數(shù)如下:航班數(shù)量N=42,機(jī)位數(shù)量M=17,最小安全時(shí)間間隔β=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ò),學(xué)習(xí)率分別為0.001和0.002。設(shè)置折扣因子γ為0.9。航班起飛延誤中,兩正態(tài)分布的均值和方差分別為μ11=0.255,σ11=6.403以及μ12=15.330,σ12=14.962;航班到達(dá)延誤分布的均值μ2=0.175,方差σ2=7.849。

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

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

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

圖1 GABA3C算法的收斂性能

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

圖2 機(jī)位分配甘特圖

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

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

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

針對(duì)3組不同場(chǎng)景實(shí)例,分別采用4種算法運(yùn)行20次繪制盒狀圖,如圖3所示。

圖3 不同場(chǎng)景實(shí)例下4種算法的目標(biāo)函數(shù)值比較

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

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

表2 不同場(chǎng)景實(shí)例下的消融實(shí)驗(yàn)結(jié)果

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

4 結(jié) 論

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