基于非合作博弈的航班時刻優(yōu)化研究

陳 彬， 翟文鵬

(中國民航大學(xué)空中交通管理學(xué)院， 天津 300300)

航班時刻是一個有限的資源，隨著航班量的不斷增加，航班延誤出現(xiàn)得越來越頻繁。因此如何高效地利用有限的航班時刻資源，減少航班延誤這一問題亟待解決。為了從根本上解決該問題，就需要從航班時刻優(yōu)化入手。目前解決航班時刻優(yōu)化問題，建立優(yōu)化模型時，大致都是以減少航班總延誤時間，和航班最大調(diào)整量作為目標(biāo)函數(shù)。

Corolli等[1]針對多機(jī)場網(wǎng)絡(luò)，考慮機(jī)場容量的不確定性，以盡可能減少時間調(diào)整偏移和預(yù)期運(yùn)行延誤的總和為目的，提出了兩階段航班時刻優(yōu)化模型；王倩等[2]為減少航班延誤，并且降低航班調(diào)整對航空公司帶來的影響，建立了機(jī)場群航班時刻優(yōu)化及動態(tài)排隊(duì)模型，并設(shè)計(jì)了改進(jìn)的迭代尋優(yōu)算法,以珠三角機(jī)場群為例對模型算法進(jìn)行了驗(yàn)證；胡明華等[3]針對中國樞紐機(jī)場運(yùn)營高峰時段分析了機(jī)場航班運(yùn)行規(guī)律和存在問題,在保證正班航班運(yùn)輸需求的基礎(chǔ)上提出基于歷史數(shù)據(jù)的航班時刻優(yōu)化模型,并改進(jìn)匈牙利算法求解,以達(dá)到航空公司申請時刻調(diào)整量和航班地面等待時間整體最小的目標(biāo)；汪夢蝶等[4]針對戰(zhàn)略航班時刻優(yōu)化問題,提出可接受調(diào)整量水平的概念,分析航班時刻表功效性與可接受性的權(quán)衡關(guān)系，建立雙目標(biāo)航班時刻優(yōu)化模型, 基于ε-約束法的分步求解策略,采用帶變異算子的改進(jìn)粒子群算法進(jìn)行求解。從中外研究現(xiàn)狀可以看出，對于航班時刻的優(yōu)化的結(jié)果好壞，大體以航班總延誤和航班總調(diào)整量的最小值為依據(jù)。但是這兩者在優(yōu)化過程中，必然存在相互影響，相互制約。因此，擬從博弈論的角度對這兩個目標(biāo)進(jìn)行分析，使航班總延誤和航班總調(diào)整量在優(yōu)化過程中達(dá)到一個均衡的狀態(tài)，使整體得到一個最佳結(jié)果。

博弈論目前已經(jīng)在分析航空公司之間的競爭，航空公司與高鐵的競爭，航班時隙分配等問題中得到了運(yùn)用[5-7]。在航班時刻多目標(biāo)優(yōu)化問題中，各個目標(biāo)一般存在競爭關(guān)系，且每個目標(biāo)都期望達(dá)到自己的最優(yōu)值。那么可以運(yùn)用博弈論對每個目標(biāo)確定一個權(quán)重系數(shù)，解決已有多目標(biāo)優(yōu)化問題中，主次目標(biāo)受到?jīng)Q策主觀性的影響，最后依據(jù)納什均衡給出每個目標(biāo)的最優(yōu)權(quán)重系數(shù)。

綜上所述，將航班總延誤時間和航班總調(diào)整量作為目標(biāo)，然后通過基于零和博弈的多目標(biāo)線性加權(quán)法得到最佳權(quán)重系數(shù)，構(gòu)建數(shù)學(xué)模型，并采用螢火蟲算法(FA)求解。以杭州蕭山國際機(jī)場為例，驗(yàn)證該模型對航班時刻優(yōu)化結(jié)果的有效性。

1 機(jī)場航班時刻優(yōu)化模型

1.1 基于零和博弈的多目標(biāo)線性加權(quán)法

為解決原問題中各個目標(biāo)函數(shù)的量綱存在差異，需要進(jìn)行歸一化處理，即

(1)

(2)

式(2)中：A′為成本。參與方1期望A′達(dá)到最大，而參與方2就是期望A′達(dá)到最小，因此零和博弈模型為

(3)

(4)

(5)

求解該模型等價(jià)于求解兩個線性規(guī)劃問題：

(6)

(7)

(8)

(9)

式中：wi為概率α′i與支付A′的比值；vj為概率β′j與支付A′的比值。

求解上述兩個規(guī)劃問題得到最優(yōu)支付為

(10)

得納什均衡解為

(11)

依據(jù)納什均衡解可以得出原問題各個目標(biāo)的權(quán)重系數(shù)：

(12)

式(12)中：aii為選擇ai和bi策略的支付。

最后將上述得到的權(quán)重系數(shù)應(yīng)用的原問題，將多目標(biāo)轉(zhuǎn)換為單目標(biāo)進(jìn)行求解，即

(13)

式(13)中：A為目標(biāo)函數(shù)的優(yōu)化結(jié)果。

1.2 目標(biāo)函數(shù)

將航班總延誤時間和總調(diào)整量兩個目標(biāo)轉(zhuǎn)換為單目標(biāo)作為一個整體，使此整體達(dá)到最小化，建立如下目標(biāo)函數(shù)：

(14)

式(14)中：f∈F，集合F={1,2,3,…,n}為航班的集合;t∈T，集合T={1,2,3,…,m}為時間片集合，每個時間片長度取5 min；α1、α2分別為航班總延誤時間和航班總調(diào)整量基于零和博弈的權(quán)重系數(shù)；wft為在t時間片的航班f的延誤時間；Vft為在t時間片的航班f的調(diào)整量；

1.3 約束條件

(1)航班的唯一性。一個航班僅分配一個時間片。

(15)

(2)機(jī)場進(jìn)場容量限制。機(jī)場運(yùn)行時間t內(nèi)，可允許飛機(jī)降落的架次受到容量的限制。

(16)

(17)

(18)

式中：a5、a15、a60分別為機(jī)場在5、15、60 min內(nèi)的進(jìn)場航班容量限制；k={1,2,3,…,190},q={1,2,3,…,181}。

(3)時間片調(diào)整量限制。一個航班的時間片調(diào)整應(yīng)該在原時刻基礎(chǔ)上的一定范圍之內(nèi)。

(19)

式(19)中：p為在時間片t的航班f的時間片調(diào)整量不超過p。

2 螢火蟲算法

螢火蟲算法(FA)是一種啟發(fā)式算法，它將空間中各個解看成螢火蟲，利用發(fā)光強(qiáng)的個體會吸引發(fā)光低的個體的特性。當(dāng)在發(fā)光弱的個體向發(fā)光強(qiáng)的個體移動的過程中，更新自身的位置，獲得新解，如此往復(fù)不斷迭代，當(dāng)最后達(dá)到迭代限制或者達(dá)到精度要求，便完成尋優(yōu)過程，將得到的最優(yōu)位置作為最優(yōu)解[9]。與遺傳算法相比，螢火蟲算法有計(jì)算精度更高、收斂速度更快，并且參數(shù)少，易于實(shí)現(xiàn)的特點(diǎn)[10]。

建立螢火蟲算法需要滿足以下條件：①設(shè)所有螢火蟲性別相同且相互吸引；②吸引度只與發(fā)光強(qiáng)弱和間隔距離有關(guān)，發(fā)光強(qiáng)個體吸引發(fā)光弱個體，吸引度與距離成反比，發(fā)光強(qiáng)的個體做隨機(jī)運(yùn)動；③目標(biāo)函數(shù)決定個體發(fā)光強(qiáng)弱，并且成比例關(guān)系。

因此，尋優(yōu)過程中螢火蟲有兩個重要參數(shù)，分別是發(fā)光亮度和相互吸引度。

設(shè)計(jì)算法如下：

(1)初始化。設(shè)置螢火蟲的數(shù)目為n個，每一個螢火蟲的所在位置表示一個解，即航班時刻表，解的維數(shù)為d，即一個航班時刻表所包含的航班架次數(shù)；最大吸引度為β0，光強(qiáng)吸收系數(shù)為γ，步長因子為α，迭代次數(shù)為t，最大迭代次數(shù)為m。

(2)隨機(jī)生成螢火蟲的位置，計(jì)算螢火蟲的目標(biāo)函數(shù)值作為各自最大發(fā)光亮度I0。

(3)計(jì)算螢火蟲之間的相對亮度I和吸引度β。根據(jù)這兩個參數(shù)決定螢火蟲移動的方向和快慢。涉及的公式為

(20)

I=I0e-γrij

(21)

(22)

式中：Xi、Xj分別為螢火蟲i、j的位置坐標(biāo)；Xik、Xjk分別為螢火蟲i、j坐標(biāo)向量第k個坐標(biāo)位置；e為自然常數(shù)。

(4)位置更新。對螢火蟲所在位置進(jìn)行更新，向亮度最高的螢火蟲移動。

(23)

式(23)中：rand為在[0，1]上服從均勻分布的隨機(jī)數(shù)。

(5)對位置更新后的螢火蟲重新計(jì)算亮度。

(6)當(dāng)?shù)玫降淖顑?yōu)解達(dá)到所需要的精度或者最大迭代次數(shù)，則算法停止并輸出最優(yōu)解和最優(yōu)值；否則迭代次數(shù)加1，轉(zhuǎn)步驟(3)，繼續(xù)進(jìn)行搜索?；谖灮鹣x算法的航班時刻優(yōu)化流程圖如圖1所示。

圖1 算法流程圖

3 算例分析

選取杭州蕭山國際機(jī)場2020-11-16當(dāng)天8:00—24:00的航班時刻，該時間段內(nèi)共降落航班321架次。分別以5 min、15 min、1 h作為時間片，對航班的進(jìn)場架次在時間上進(jìn)行合理的安排。時間片長度設(shè)置為5 min時，只有4個時間片降落航班架次為4架次，不超過3架次的時間片占97.92%，故設(shè)置機(jī)場5 min容量為3架次；時間片長度設(shè)置為15 min時，只有5個時間片降落航班架次為8架次，不超過7架次的時間片占92.19%，故設(shè)置機(jī)場15 min容量為7架次；時間片長度設(shè)置為1 h時，只有1個時間片降落航班架次為28架次，不超過24架次的時間片占93.75%，故設(shè)置機(jī)場1 h容量為24架次。并在優(yōu)化過程中設(shè)置最小調(diào)整量為5 min，最大調(diào)整量為15 min。

表1 航班時刻優(yōu)化問題零和博弈的支付矩陣

由式(3)建立的零和博弈問題，可求得納什均衡解α1=0.13，α2=0.87。由圖2看出，在15∶00至16∶00落地航班量為24架次，航班量較大，所以選擇在這一個小時的情況下，多目標(biāo)優(yōu)化結(jié)果和基于零和博弈模型的優(yōu)化結(jié)果進(jìn)行對比。

圖2 每小時航班降落架次

圖3(a)是主要考慮航班總延誤的多目標(biāo)優(yōu)化后航班時刻表，和基于零和博弈模型優(yōu)化后的航班時刻表的對比，可以看出兩者在優(yōu)化后整體相對重合，但是多目標(biāo)優(yōu)化的調(diào)整量會相對較大；圖3(b)是主要考慮航班總調(diào)整量的多目標(biāo)優(yōu)化后航班時刻表，和基于零和博弈模型優(yōu)化后的航班時刻表的對比，可以看出兩者調(diào)整幅度比較相近，但是多目標(biāo)優(yōu)化的曲線略高于零和博弈模型的優(yōu)化，即延誤較高；圖3(c)是基于零和博弈模型優(yōu)化后的航班時刻表和實(shí)際航班時刻表的對比，可以看出優(yōu)化后的航班時刻表曲線比實(shí)際的要低，即延誤有減少，且幅度較低，即調(diào)整量少。

圖3 航班時刻優(yōu)化對比圖

表2給出了不同優(yōu)化方式下的結(jié)果。單目標(biāo)優(yōu)化指僅以航班總延誤或航班總調(diào)整量為目標(biāo)；多目標(biāo)優(yōu)化指線以其中一個目標(biāo)為主目標(biāo)，而將另外一個目標(biāo)作為約束條件再進(jìn)行優(yōu)化；零和博弈指本文使用零和博弈模型確定權(quán)重，再用螢火蟲給算法進(jìn)行優(yōu)化。可以看出基于零和博弈模型的優(yōu)化得出的結(jié)果可以更好地均衡航班總延誤時間和航班總調(diào)整量。

表2 不同優(yōu)化方法結(jié)果

在圖4和圖5中，時間片長度分別為15 min和60 min的情況下，對比優(yōu)化前的機(jī)場容量和零和博弈下優(yōu)化后的機(jī)場容量，優(yōu)化后均未超出機(jī)場容量限制，并且每個時間片的航班分布更加均勻。由表3可知，機(jī)場整體延誤情況，也得到了有效的改善，航班準(zhǔn)點(diǎn)率提高了9.7%。

圖4 15 min優(yōu)化前后航班量對比

圖5 60 min優(yōu)化前后航班量對比

表3 航班時刻優(yōu)化前后延誤情況對比

4 結(jié)論

(1)相較于以往主觀或客觀定義權(quán)重的方式，另兩個目標(biāo)之間為使各自效益最大化進(jìn)行博弈，得出納什均衡策略下的最佳權(quán)重系數(shù)，可以使航班總延誤和航班總調(diào)整量均達(dá)到相對滿意的結(jié)果。

(2)與傳統(tǒng)的不同優(yōu)化方法之間相互比較，可以看出，基于零和博弈的航班時刻優(yōu)化模型在優(yōu)化上，使航班總延誤相比于單目標(biāo)優(yōu)化只增加21.3%，航班總調(diào)整只增加19.5%，即整體優(yōu)化效果要高于傳統(tǒng)的多目標(biāo)優(yōu)化。

(3)使用零和博弈的航班時刻優(yōu)化模型進(jìn)行優(yōu)化的結(jié)果與實(shí)際航班數(shù)據(jù)進(jìn)行對比，可以看出航班量分布更加均勻，在最大航班量限制以下。同時航班整體延誤得到了改善。但隨著航班量的增加，通過調(diào)整航班時刻，很難將機(jī)場的延誤有效地降低，所以兩者之間的博弈關(guān)系仍然需要進(jìn)一步討論。