飛機(jī)地面除冰運(yùn)行合作博弈模型研究

崔艾軍，邢志偉

（1.北京首都國際機(jī)場股份有限公司飛行區(qū)管理部，北京 100621；2.中國民航大學(xué)航空自動化學(xué)院，天津 300300）

飛機(jī)地面除冰運(yùn)行合作博弈模型研究

崔艾軍1，邢志偉2

（1.北京首都國際機(jī)場股份有限公司飛行區(qū)管理部，北京 100621；2.中國民航大學(xué)航空自動化學(xué)院，天津 300300）

通過對飛機(jī)除冰運(yùn)行問題的分析研究,以合作博弈的思想為理論基礎(chǔ),建立了在允許合作選擇對策并且進(jìn)行支付轉(zhuǎn)移規(guī)則下的航空公司博弈模型,通過對模型核心與特征函數(shù)的分析,基于Shapley向量的博弈核心求解方法得以提出.仿真結(jié)果表明,該合作博弈模型有效激勵了航空公司間的合作行為,基于Shapley向量核心解法兼顧了聯(lián)盟的集體理性與個體理性,對比顯示,其分配方案合理、較優(yōu).

資源分配；飛機(jī)地面除冰；聯(lián)盟；合作博弈；Shapley向量

公平、高效分配除冰資源是避免冬季航班延誤的重要途徑之一，因此，除冰資源分配與調(diào)度的優(yōu)化是飛機(jī)除冰運(yùn)行的實(shí)質(zhì)。飛機(jī)除冰資源爭奪的利益主體由駐場航空公司及其聯(lián)盟構(gòu)成，在共同爭奪除冰資源的過程中形成博奕關(guān)系。如何通過利益主體的合作博奕實(shí)現(xiàn)除冰資源的高效、公平分配是本文探討的主要內(nèi)容。Tijs等[1]提出了一種基于τ值的成本差額分配方法(costgap allocation method)。Curiel等[2-3]結(jié)合了合作博弈和排序理論。文獻(xiàn)[4]建立一種新的合作博弈模型，且該模型是基于兩種性能指標(biāo)函數(shù)的。文獻(xiàn)[5]使用全新的思想，將資源分配的方法應(yīng)用在OFDM系統(tǒng)中。

本文在前人方法的基礎(chǔ)之上[6-10]，對其進(jìn)行了改進(jìn)，但仍以博弈思想為核心，借鑒了已有的飛機(jī)除冰運(yùn)行多Agent模型，通過合作方式使各航空公司Agent隨機(jī)建立聯(lián)盟，建立了在允許合作選擇對策并且進(jìn)行支付轉(zhuǎn)移規(guī)則下的航空公司博弈模型，提出了基于Shapley向量的博弈核心求解方法。結(jié)論表明，該算法進(jìn)一步提高了沖突解決能力，保證了各航空公司間的利益公平性，增加了決策算法的動態(tài)穩(wěn)定裕度。

1 飛機(jī)地面除冰問題描述及運(yùn)行流程

預(yù)先分配其除冰資源是當(dāng)前飛機(jī)地面除冰運(yùn)行過程的一般方法，也就是說，用于飛機(jī)地面除冰的一系列資源在規(guī)劃的時間ti內(nèi)都已預(yù)先分配給各航空公司的航班。在除冰資源分配過程中，各航空公司作為資源申請過程中的局中人都是私利的，在此過程中存在信息與策略交互，即構(gòu)成了博弈關(guān)系。文獻(xiàn)[10]從除冰運(yùn)行三方主體的角度分析了非合作博弈模型及其NASH均衡解，各航空公司被看做一個利益整體來分析，然而，在實(shí)際除冰作業(yè)過程中，航空公司Agent內(nèi)部各航空公司間的利益沖突并不是簡單的零和情形，原因在于各航空公司的利益可能交叉，而不一定是對立的，某些情形下可以出現(xiàn)對各航空公司都有益的局勢，于是，聯(lián)盟條件下的合作博弈應(yīng)運(yùn)而生。

現(xiàn)假設(shè)有n個航空公司有組成聯(lián)盟A的意愿，聯(lián)盟A存在需要滿足聯(lián)盟個體理性條件和聯(lián)合理性條件，即

其中：

1）s=（s1，s2，…，si）是由ADC為給航空公司分配的資源集，由s′=（s1′，s2′，…，si′）表示的資源分配集來源于聯(lián)盟內(nèi)部；

2）u=（u1，u2，…，ui）是表示效用配置的集合，而且該集合與s相對應(yīng)，對于博弈方，用ui來表示其期望效用，ui∶S→R；u′=（u1′，u2′，…，ui′）為s′相應(yīng)的效用配置集；

5）ui′=ui′（s′）≥ui=ui（s）表示個體理性的約束條件，其所包含的意義為每個博弈方的得益都必須不少于其不參與聯(lián)盟的得益。

上述所有條件都滿足的聯(lián)盟合作博弈及其存在條件構(gòu)成了合作博弈形成的核心問題。

2 航空公司合作博弈模型

假設(shè)n個航空公司的航班需要申請（ti+1，ti+2）時間段內(nèi)的除冰資源Re=（{sloti}，{bayi}），Re>0且數(shù)量受限，i=1，…，n，Airlinei為第i個航空公司，sloti為除冰時間資源，bayi為除冰坪資源。

考察規(guī)范型非零和對策，Airline之間的博弈關(guān)系可表示為

其中：N={1，…，n}表示所有航班的集合，且這些航班屬于參與申請除冰的航空公司，換言之，也就是局中人的集合；Xi為Airlinei的策略集合；Hi為表示Airlinei的支付函數(shù)，且該支付函數(shù)定義在笛卡爾乘積X=上。

記Airlinei分配的除冰資源量xi，x={x1，…，xi}之下Airlinei獲得支付Hi（x1，…，xi），給定正數(shù)θ，當(dāng)時，由于除冰擁擠而造成資源效用顯著降低。

支付函數(shù)可表示為

μ=（μ1，…，μn）為表示混合策略局勢的變量，其中，假定Airlinei選擇純策略的概率為μi（xi），也就是說，Airlinei采用自己的混合策略μi。由于純策略均衡局勢通常不存在，對策Γ進(jìn)行混合擴(kuò)充，即

N的子集S?N表示博弈中的聯(lián)盟，用P（N）來代表集合，該集合由N的所有子集構(gòu)成。

定義1 Airlinei聯(lián)盟博弈的支付函數(shù)

設(shè)N={1，…，n}，聯(lián)盟A上的實(shí)值函數(shù)由K（A）表示，其中A表示N的所有子集，若

則K（A）為該聯(lián)盟博弈的支付函數(shù)。

定義2 航空公司聯(lián)盟博弈模型

用t時刻、n個航空公司之間、動態(tài)的合作博弈關(guān)系來表示航空公司的聯(lián)盟博弈模型，N的所有子集均可由A表示

其中：N為一個集合，表示方式，是各個航空公司在t時刻組建資源分配聯(lián)盟的方法為t時刻合作方式i的所有可行混合策略的有限集合；{Ki}i∈N為期望效用函數(shù)的集合，且該集合是在時刻t、合作方式i的所有混合策略的期望效用函數(shù)；K（A）為聯(lián)盟A在t時刻的總支付。

定義3 聯(lián)盟博弈目標(biāo)函數(shù)

由除冰調(diào)度總體目標(biāo)：Min{ΣΔti，ΣNdelayi，F(xiàn)lid/Fli}可得此博弈模型的目標(biāo)函數(shù)為

其中：M*={μij*}表示均衡局勢，且該局勢對應(yīng)于對策Γ的協(xié)同混合策略。

3 聯(lián)盟合作博弈算法求解

由于航空公司聯(lián)盟博弈最終還是博弈方（各航空公司）的策略選擇問題，因此類似非合作博弈的占優(yōu)分析是有意義的；但聯(lián)盟博弈的本質(zhì)又是利益分配問題，因此類似納什解法的公理化方法在聯(lián)盟博弈分析中也是有效的。

3.1 優(yōu)超與核心

定義4 分配優(yōu)超

定義5 聯(lián)盟博弈核心

稱配置集為核心（Core），且該配置集能夠保證聯(lián)盟穩(wěn)定存在，也就是說，對于合作博弈為n人的B（N，v），不被任何分配優(yōu)超的分配全體，同時，該全體存在于分配集P（N）中

3.2 聯(lián)盟博弈核心的Shapley向量解法

Shapley向量解法基于3個公理，提出于1953年，在研究多人合作對策問題時由Shapley發(fā)現(xiàn)[11]。假定n個除冰主體達(dá)成合作聯(lián)盟，則通過組成聯(lián)盟其任意一個主體可以獲得多少份額的支付，成為各除冰主體最感興趣的問題之一。其出發(fā)點(diǎn)在于：如果參與方建立具有約束力的合作聯(lián)盟的前提是，該方案分配公平合理；按照參與方對于合作聯(lián)盟的貢獻(xiàn)分配支付的做法是較為客觀的。

航空公司聯(lián)盟博弈核心的Shapley向量解法，即將聯(lián)盟收益按向量（φ1，…，φn）分配，在最大化聯(lián)盟和支付的條件下公平分配各方的利益，其中

其中：k=|S|表示S中所包含的航空公司數(shù)量，也就是聯(lián)盟規(guī)模的大?。幌蛄浚é?，…，φn）為 B（N，v）的“Shapley值”，φi是Airlinei的Shapley值；v（S）-v（S {i}）為參與或不參與聯(lián)盟S對特征函數(shù)值的影響，反映了其對聯(lián)盟S的貢獻(xiàn)；（以隨機(jī)方式結(jié)盟時參與聯(lián)盟S的概率（記為p（|S|））。

衡量聯(lián)盟博弈中每個博弈方價值的最好指標(biāo)正是各個 Airlinei參與聯(lián)盟博弈的期望貢獻(xiàn)，亦即Shapley值。于是，公平分配聯(lián)盟之間的有限除冰資源，使聯(lián)盟之間避免無休止的對抗，從而根本解決聯(lián)盟博弈問題的有效方法就是求解Shapley值。

4 算例分析

4.1 Shapley值優(yōu)化分析

以國內(nèi)某大型樞紐機(jī)場冬季某天9:00～11:00三大航空公司（CA，MU，CZ）航班計(jì)劃為例，采取預(yù)先分配資源的策略，也就是在規(guī)劃時間ti，先將某一除冰坪的除冰時間資源，采取預(yù)先分配資源的策略，預(yù)先分配給各航空公司。除冰隊(duì)列已按照除冰優(yōu)先級算法[7]得到，依次為A1、A2、A3，即N={A1，A2，A3}，其預(yù)分配除冰時間分別為27、37、36，其在對應(yīng)已分配時間區(qū)間不能按時除冰的概率分別為10%、5%、15%；若按時除冰，航空公司收益為1，若未按時除冰，航空公司收益為-2；聯(lián)盟外部資源轉(zhuǎn)讓損失率為5%，聯(lián)盟內(nèi)部一次資源轉(zhuǎn)讓無損失，二次轉(zhuǎn)讓損失率5%。除冰資源分配按非合作、部分合作及完全合作3種博弈策略進(jìn)行分析，不同博弈策略下的Shapley值如表1～表3所示。

表1 A1航班Shapley值計(jì)算參數(shù)Tab.1 Shapley value calculating parameters of flight A1

根據(jù)表1～表3，可得到向量φ=（φA1，φA2，φA3）=（1.091 7，1.041 7，0.866 7）即為該三方聯(lián)盟博弈的解，是該博弈的核心，從而最佳資源分配方案為

表2 A2航班Shapley值計(jì)算參數(shù)Tab.2 Shapley value calculating parameters of flight A2

表3 A3航班Shapley值計(jì)算參數(shù)Tab.3 Shapley value calculating parameters of flight A3

4.2 Shapley值違約概率的影響分析

各航空公司組成最大聯(lián)盟之后由Shapley向量進(jìn)行除冰資源分配的方案，其聯(lián)盟期望總收益為各合作方式及非合作方式中的最大值，時間資源損耗同時也為其中最小值，說明了Shapley分配方法是較優(yōu)的。在部分合作博弈中，A2選擇與A3合作的情況下，其期望總支付為3種合作方式最大值，且資源損耗比其他兩種情況較小，說明違約概率較大的南方航空公司與東方航空公司之間形成聯(lián)盟可降低由于違約帶來的懲罰風(fēng)險，達(dá)成交換協(xié)議后時間損耗也為最小，是各部分合作博弈中的較優(yōu)策略；非合作博弈方式下，期望總支付為3種情況下最小值，同時資源損耗也較大。

圖1 違約概率與Shaply向量值Fig.1 Default probability and Shaply vector value

不同違約概率條件下的Shapley分配向量值如圖1所示，根據(jù)結(jié)果可得出:違約概率越大的公司在聯(lián)盟中由Shapley向量法獲得的分配將越少，改變各航空公司的違約概率，使A1、A2、A3的違約概率由5%、10%、15%降至4%、9%、14%，得到的對比數(shù)據(jù)如圖2所示?？梢钥闯?，降低違約概率后，各種分配方式獲得的期望總支付都獲得了增加，資源損耗有所下降。說明本文建立的合作模型以及做出的分配分析合理有效。

圖2 違約概率與期望收益Fig.2 Default probability and expected revenue

5 結(jié)語

基于飛機(jī)除冰運(yùn)行合作博弈模型，分析了兩個除冰主體的合作博弈和航空公司動態(tài)聯(lián)盟博弈分配解的影響因素和構(gòu)造方法，提出了基于聯(lián)盟核心的Shapley向量航空公司聯(lián)盟分配解方法。結(jié)果表明：建立的聯(lián)盟博弈模型使得各博弈方獲得的效益得以增加，有效地激勵了航空公司的合作行為；Shapley向量解不僅滿足了聯(lián)盟成立的條件，而且還能同時兼顧聯(lián)盟的個體理性和集體理性；該模型可以保證聯(lián)盟的長期穩(wěn)定運(yùn)行，違約率較聯(lián)盟平均水平大的航空公司獲得的時間資源要比其理論除冰耗時稍少，從而激勵航空公司降低其違約率。

[1]TIJS S，DRIESSEN T.Game theory and cost allocation problems[J]. Management Science，1986，32（8）：1015-1028.

[2]CURIEL I，PEDERZOLI G，TIJS S.Sequencing games[J].European Journal of Operational Research，1989，40：344-351.

[3]CURIEL I，POTTERS J，PRASAD R.Cooperation in one machine scheduling[J].Methods and Models of Operations Research，1993，38：113-129.

[4]ARANTZA E F，BORM P，CALLEJA P，et al.Sequencing games with repeatedplayers[J].Annalsof OperationsResearch，2008，158：189-203.

[5]CHEET K，LIMC C，CHOOI J.A Cooperative Game Theoretic Framework for Resource Allocation in OFDMA Systems[C]//10th IEEE Singapore International Conference onCommunication Systems（ICCS 2006），Reading，UK，May，2006：1-5.

[6]MAO XIAOYU，ADRIAAN TER MORS，NICO ROOS，et al.Agent-Based Scheduling for Aircraft Deicing[C]//Pierre-Yves Schobbens，Wim Vanhoof and Gabriel Schwanen，Proceedings of the 18th Belgium-Netherlands Conference on Artificial Intelligence，2006：229-236.

[7]MAO XIAOYU，ADRIAAN TER MORS，NICO ROOS，et al.Using Neuro-Evolution in Aircraft Deicing Scheduling[C]//ALAMAS 2007 Adaptive and Learning Agents and Multi-Agent Systems，2007：138-145.

[8]ADRIAAN TER MORS，MAO XIAOYU，NICO ROOS，et al.Multi-A-gent System Support for Scheduling Aircraft Deicing[C]//Proceeding of ISCRAM，2007-Intelligent Human Computer Systems for Crisis Response and Management，2007：467-478.

[9]XING ZHIWEI，WANG GUIFANG，LI YI.Delay analysis and scheduling method for aircraft ground deicing operation[J].Information and Control，2010，39（6）：743-748.

[10]XING ZHIWEI，QIAO XIAOHUI.Research of aircaft ground deicing operation based on non-cooperative game theory[J].Journal of System Simulation，2011，23（3）：433-437.

[11]SHAPLEY L S.A value forn-persons games[J].Annals of Mathematics Studies，1953，28：307-318.

（責(zé)任編輯：楊媛媛）

Cooperative game model for aircraft ground deicing operation

CUI Ai-jun1，XING Zhi-wei2
（1.Department of Airfield Management，Beijing Capital International Airport Co.Ltd.，Beijing 100621；2.College of Aeronautical Automation，CAUC，Tianjin 300300）

Based on cooperative game theory and analysis of aircraft deicing operation，game model under the rules allowing cooperation selection strategy and payment transferring is established for aviation companies.The core game solution method based on Shapley vector is proposed through analysis of the model core and its characteristic function.Simulation results show that the cooperative game model motivate the cooperative behavior among airlines effectively，Shapley vector-based core solution taking into account the alliance's collective rationality and individual rationality simultaneously.Comparison proves that the allocation scheme of the current model is reasonable and comparatively optimal.

resource allocation；aircraft ground deicing；alliance；cooperative game；Shapley vector

V351

:A

:1674-5590(2015)01-0009-04

2014-09-28；

:2014-11-04

國家自然科學(xué)基金項(xiàng)目（U1233124）；國家科技支撐計(jì)劃（2012BAG04B02）

崔艾軍（1974—），男，北京人，工程師，工學(xué)碩士，研究方向?yàn)闄C(jī)場運(yùn)行調(diào)度與控制，機(jī)場安全管理.