基于動態信譽的飛機推出時隙分配Stackelberg博弈*

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

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

0 引 言

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

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

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

1 基于動態信譽的飛機推出時隙分配混合決策

1.1 動態信譽優先概念

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

1.2 基于動態信譽和FCFS的混合決策算法行為規則

1.3 推出時隙分配混合決策

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

注：虛線框內是決策過程公司信譽優先級的動態變化圖1 基于動態信譽的飛機推出時隙分配混合決策流程

(1)

2 信譽機制下的飛機推出Stackelberg博弈模型

2.1 Stackelberg博弈建模

2.2 上層機場收益

i=1,2,…,n

(2)

(3)

2.3 下層公司收益

將公司收益轉換為最小化本公司單架飛機平均地面成本

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

(4)

(5)

(6)

3 改進人工魚群算法

3.1 算法步驟

為了加快求解速度和保證精度，本論文對AFSA鄰域中心及最優解選擇進行改進.

步驟2計算初始魚群各個體適應值，取最優AF狀態及其值賦給公告板.

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

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

步驟5公告板上最優解滿足收斂準則，算法結束，否則轉步驟3.

3.2 鄰域中心

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

3.3 面向未違約公司的最優解

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

4 仿真分析

4.1 數據準備

表1 計算相關數據

注：資料來源河南省機場集團有限公司.

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

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

表2 飛機-時隙分配對

4.2 仿真設計

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

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

AF經過45次迭代由分散到集聚，兩個目標函數達到最優4.87 min/人、447元/架.

4.3 結果分析

表3 仿真結果

圖4 每架飛機地面成本

圖5 單架飛機滑出時間

5 結 束 語

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

[1] 董瑩,安然.機場航空器地面滑行時間優化研究[J].交通運輸系統工程與信息,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] 楊雙雙,朱華慶.航空器推出決策的優化研究[J].武漢理工大學學報(交通科學與工程版),2014,38(1):227-231.

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

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

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

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