陳 彬， 翟文鵬

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

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

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

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

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

1 機(jī)場(chǎng)航班時(shí)刻優(yōu)化模型

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

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

(1)

(2)

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

(3)

(4)

(5)

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

(6)

(7)

(8)

(9)

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

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

(10)

得納什均衡解為

(11)

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

(12)

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

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

(13)

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

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

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

(14)

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

1.3 約束條件

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

(15)

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

(16)

(17)

(18)

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

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

(19)

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

2 螢火蟲算法

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

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

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

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

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

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

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

(20)

I=I0e-γrij

(21)

(22)

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

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

(23)

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

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

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

圖1 算法流程圖

3 算例分析

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

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

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

圖2 每小時(shí)航班降落架次

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

圖3 航班時(shí)刻優(yōu)化對(duì)比圖

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

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

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

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

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

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

4 結(jié)論

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

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

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