基于動態(tài)信譽(yù)的飛機(jī)推出時隙分配Stackelberg博弈*

劉麗華 張亞平 王明輝 邢志偉

(河南城建學(xué)院土木與交通工程學(xué)院1) 平頂山 467036) (哈爾濱工業(yè)大學(xué)交通科學(xué)與工程學(xué)院2) 哈爾濱 150090)(江蘇省蘇州市吳江區(qū)公安局3) 蘇州 215200) (中國民航大學(xué)航空地面特種設(shè)備研究基地4) 天津 300300)

0 引 言

高峰時段的場面擁堵及航班延誤是國內(nèi)外機(jī)場面臨的共性問題，不僅降低機(jī)場運(yùn)營效率，也給航空公司帶來巨大損失.依靠基礎(chǔ)設(shè)施擴(kuò)建已無法滿足場面需求的增長，場面運(yùn)行管理至關(guān)重要.場面運(yùn)行管理涉及推出管理、路徑優(yōu)化[1]等，傳統(tǒng)先到先服務(wù)(first come first serve，F(xiàn)CFS)推出管理下，推出需求在時間上集中、極易引發(fā)擁堵，而合理的推出管理能分散推出需求，大幅降低擁堵和地面成本.

Fornés[2]分析了推出率控制的停機(jī)位等待約束.楊雙雙等[3]提出基于場面監(jiān)視雷達(dá)系統(tǒng)的滑行推出許可決策啟發(fā)式控制方法.張亞平等[4]從機(jī)場場面滑行容量的角度對飛機(jī)推出時段進(jìn)行了研究.實(shí)際推出過程中，如果飛機(jī)未按約定時刻推出，按照現(xiàn)行的FCFS分配原則，該飛機(jī)將延遲較長時間推出，航空公司(以下簡稱公司)不會因違約受到懲罰，不但浪費(fèi)推出資源，對未違約公司也不公平.現(xiàn)代博弈論認(rèn)為解決違約行為最有效方法是給違約一方足夠嚴(yán)厲的懲罰，邢志偉等[5]在飛機(jī)除冰研究中提出浮動優(yōu)先級算法對違約公司進(jìn)行了懲罰.

違約行為下的推出時隙分配需要先確定飛機(jī)-時隙對，然后求解最優(yōu)推出時刻.本文首先設(shè)計基于動態(tài)信譽(yù)優(yōu)先的飛機(jī)推出時隙分配混合決策流程得到飛機(jī)-時隙對，接著利用Stackelberg博弈建立雙層規(guī)劃模型，并設(shè)計改進(jìn)的人工魚群算法求解最優(yōu)推出時刻，最后將其應(yīng)用于新鄭機(jī)場飛機(jī)推出研究，驗(yàn)證模型及算法性能.

1 基于動態(tài)信譽(yù)的飛機(jī)推出時隙分配混合決策

1.1 動態(tài)信譽(yù)優(yōu)先概念

①為了讓更多小公司公平參與競爭，信譽(yù)優(yōu)先級僅考慮履約與否；②優(yōu)先級最高的公司享有優(yōu)先權(quán)，若選定飛機(jī)按時推出，該公司優(yōu)先級保持不變；若違約，優(yōu)先級降低；③參與申請但優(yōu)先級較低沒有獲得資源的公司，下次分配中適當(dāng)提高其優(yōu)先級，作為對失去資源的補(bǔ)償；④沒有參與資源爭奪的公司信譽(yù)不受影響.

1.2 基于動態(tài)信譽(yù)和FCFS的混合決策算法行為規(guī)則

1.3 推出時隙分配混合決策

對于每一個時隙依次執(zhí)行如下步驟：確定待選飛機(jī)、公司集合，利用混合決策算法確定飛機(jī)-時隙對，根據(jù)是否違約進(jìn)行決策，直到所有時隙分配完算法結(jié)束，決策流程見圖1.

注：虛線框內(nèi)是決策過程公司信譽(yù)優(yōu)先級的動態(tài)變化圖1 基于動態(tài)信譽(yù)的飛機(jī)推出時隙分配混合決策流程

(1)

2 信譽(yù)機(jī)制下的飛機(jī)推出Stackelberg博弈模型

2.1 Stackelberg博弈建模

2.2 上層機(jī)場收益

i=1,2,…,n

(2)

(3)

2.3 下層公司收益

將公司收益轉(zhuǎn)換為最小化本公司單架飛機(jī)平均地面成本

i=1,2,…,nl,l=1,2,…,u

(4)

(5)

(6)

3 改進(jìn)人工魚群算法

3.1 算法步驟

為了加快求解速度和保證精度，本論文對AFSA鄰域中心及最優(yōu)解選擇進(jìn)行改進(jìn).

步驟2計算初始魚群各個體適應(yīng)值，取最優(yōu)AF狀態(tài)及其值賦給公告板.

步驟3個體依次進(jìn)行追尾、覓食、聚群行為(若超過try_number次后仍無明顯進(jìn)步就加入隨機(jī)行為)，生成新魚群.

步驟4評價所有個體.若某個體優(yōu)于公告板，則γ將公告板更新為該個體.

步驟5公告板上最優(yōu)解滿足收斂準(zhǔn)則，算法結(jié)束，否則轉(zhuǎn)步驟3.

3.2 鄰域中心

為了避免求解過程陷入局部最優(yōu)，設(shè)計新的鄰域中心[7]計算方法：將y的Visual鄰域AF按照目標(biāo)函數(shù)值y由小到大排列；取y值較小的前50%條組成新的集合U，在U中選擇新的狀態(tài)tv；如果(ys-yv)/ys<γ(為誤差，考慮到成本加權(quán)值變化程度不大，令γ介于10%～20%)，接受，這些U0組成新的集合U0(U0∈U).若U0非空，則在U0中任選一個作為y，否則將y作為中心.

3.3 面向未違約公司的最優(yōu)解

AFSA最優(yōu)解可能并不唯一：y相等狀態(tài)y不同.在y相同情況下考慮未違約公司利益：至少有一家未違約公司平均成本低于違約公司，選擇能夠使某未違約公司平均成本最小的結(jié)果.

4 仿真分析

4.1 數(shù)據(jù)準(zhǔn)備

表1 計算相關(guān)數(shù)據(jù)

注：資料來源河南省機(jī)場集團(tuán)有限公司.

假設(shè)飛機(jī)編號f8，f10違約，由式(2)及表1得到飛機(jī)-時隙對見表2(無違約和違約下飛機(jī)f1～f7、f15～f16、f21～f29的分配對fi-sj中編號一致，不再列出).

f8、f10與后續(xù)飛機(jī)順序均下滑，下滑程度隨a值變大而明顯，體現(xiàn)了違約懲罰.a=2時，PN在f8之后的飛機(jī)未受影響，懲罰力度不夠；a=6時波及到f10之后的第6架，導(dǎo)致懲罰過重.綜上a=[3,5].

表2 飛機(jī)-時隙分配對

4.2 仿真設(shè)計

圖2 AF搜索過程(a=3，橫、縱坐標(biāo)x、y為魚在水域中位置)

圖3 AFSA收斂過程(a=3)

AF經(jīng)過45次迭代由分散到集聚，兩個目標(biāo)函數(shù)達(dá)到最優(yōu)4.87 min/人、447元/架.

4.3 結(jié)果分析

表3 仿真結(jié)果

圖4 每架飛機(jī)地面成本

圖5 單架飛機(jī)滑出時間

5 結(jié) 束 語

本文研究違約行為下的推出時隙分配優(yōu)化，提出動態(tài)信譽(yù)優(yōu)先理論及混合決策算法；將推出時刻優(yōu)化的非合作博弈描述為雙層規(guī)劃問題，考慮因素更加全面；并對人工魚群算法進(jìn)行改進(jìn)，以加速找到全局最優(yōu). 仿真結(jié)果表明本方法既能對違約公司適度懲罰，又能兼顧各方利益，同時降低滑出時間和地面運(yùn)行成本.

[1] 董瑩,安然.機(jī)場航空器地面滑行時間優(yōu)化研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2011,11(5):141-146.

[2] FORNéS MARTINEZ H. Analysis of potential implementations of pushback control at LaGuardia Airport[D]. Boston: Massachusetts Institute of Technology,2015.

[3] 楊雙雙,朱華慶.航空器推出決策的優(yōu)化研究[J].武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版),2014,38(1):227-231.

[4] 張亞平,劉麗華,郝斯琪,等.基于彈性滑行容量的飛機(jī)有效推出時隙研究武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版),2016,40(6):937-942.

[5] 邢志偉,喬曉輝.飛機(jī)地面除冰運(yùn)行的非合作博弈研究[J].系統(tǒng)仿真學(xué)報,2011,23(3):433-437.

[6] 劉麗華,張亞平,邢志偉,等.基于離散差分進(jìn)化的飛機(jī)推出決策優(yōu)化[J].交通運(yùn)輸系統(tǒng)工程與信息,2016,16(6):196-203.

[7] 王飛.地面等待策略中的時隙分配模型與算法研究[D].南京:南京航空航天大學(xué),2010.