飛機(jī)除冰資源申請(qǐng)過程航空公司的博弈研究

邢志偉，張彭城

（1.中國民航大學(xué)民航地面特種設(shè)備研究基地，天津 300300；2.中國民航大學(xué)航空自動(dòng)化學(xué)院，天津 300300）

飛機(jī)結(jié)冰是影響民航機(jī)場冬季航班安全的關(guān)鍵問題之一。同時(shí)，飛機(jī)地面除冰效率低下也是造成冰雪天氣大型樞紐機(jī)場航班大面積延誤的直接原因之一。在除冰設(shè)備固定的情況下，飛機(jī)地面除冰過程的調(diào)度與優(yōu)化則成為影響飛機(jī)地面除冰質(zhì)量和效率的關(guān)鍵。

飛機(jī)地面除冰過程是一種典型的隨機(jī)服務(wù)系統(tǒng)?，F(xiàn)行的飛機(jī)地面除冰過程大多數(shù)實(shí)行的是先到先服務(wù)方式。冰雪天氣情況下，各航空公司下屬航班均到除冰坪統(tǒng)一排隊(duì)等候。這種除冰模式最為簡單，但是效率也較低，沒有考慮航空公司的信譽(yù)度和航班的緊急程度而采取有針對(duì)性的排隊(duì)方式，因而在冬季飛機(jī)起飛較集中的時(shí)段，容易造成大面積航班延誤。

目前，國內(nèi)外專門針對(duì)飛機(jī)地面除冰運(yùn)行調(diào)度問題的研究還處于起步階段。趙青、馮香玲[1]等人研究了飛機(jī)地面除冰整體操作過程中可提高除冰效率的程序；邢志偉、李軼[2]建立了基于Multi-Agent的預(yù)約除冰模型，按照各航空公司的信譽(yù)度高低來分配除冰資源，極大地提高了飛機(jī)地面除冰過程的效率，同時(shí)兼顧了各航空公司的公平性和除冰資源的利用規(guī)律，為飛機(jī)地面除冰調(diào)度開辟了新的途徑。然而上述研究在航空公司申請(qǐng)資源的處理上考慮有欠周全，各航空公司之間沒有有效的協(xié)商合作機(jī)制，從而造成了一部分除冰資源的浪費(fèi)，同時(shí)也沒有涉及對(duì)于航空公司申請(qǐng)到除冰資源后的違約問題。本文在邢志偉、李軼等人建立的基于Multi-Agent飛機(jī)地面除冰運(yùn)行模型的基礎(chǔ)上，以合作博弈[3-7]為分析工具，研究如何建立各航空公司之間的合作組織，分析航空公司在除冰資源申請(qǐng)過程中的博弈行為，從而使航空公司組織的利益最大化。最后通過分析合作前后收益的變化，來驗(yàn)證這種合作組織的合理性和有效性。

1 除冰資源預(yù)約分配過程簡介

機(jī)場除冰調(diào)度并非實(shí)時(shí)調(diào)度，而是采取預(yù)先分配資源的策略，在規(guī)劃時(shí)間上進(jìn)行除冰資源的預(yù)先分配機(jī)場指揮中心和地面服務(wù)公司通信，取得往后1 h內(nèi)的除冰申請(qǐng)航班信息以及這段時(shí)間內(nèi)的可用除冰資源，規(guī)劃完畢后發(fā)送分配信息給航空公司確認(rèn)，收到航空公司的確認(rèn)信息之后即完成一個(gè)周期。

航空公司在申請(qǐng)除冰資源的過程中，機(jī)場指揮調(diào)度中心根據(jù)各個(gè)航空公司的信譽(yù)度來判定其申請(qǐng)資源的優(yōu)先級(jí)。優(yōu)先級(jí)高的航空公司申請(qǐng)到除冰資源的概率較高。航空公司的信譽(yù)度由其在申請(qǐng)到除冰資源之后是否能及時(shí)趕到現(xiàn)場除冰來判斷。規(guī)定此除冰系統(tǒng)模型中，因航班自身問題而不能及時(shí)到達(dá)除冰坪使用已經(jīng)申請(qǐng)到的資源時(shí)，此航班所屬航空公司需支付違約費(fèi)用。

2 除冰資源申請(qǐng)中航空公司的博弈

對(duì)于航空公司來說，機(jī)場除冰資源相對(duì)短缺，尤其在飛機(jī)集中起飛的時(shí)刻，如何申請(qǐng)到除冰資源和保證及時(shí)除冰、按時(shí)起飛是每個(gè)航空公司首要考慮的問題；其次，當(dāng)申請(qǐng)到除冰資源后，航空公司下屬的某個(gè)航班由于某種原因不能及時(shí)到達(dá)機(jī)場，由于采用預(yù)約制，此時(shí)的除冰資源不能再用于其他航班，而浪費(fèi)了資源；同時(shí)，此違約的航空公司也要因?yàn)檫`約而信譽(yù)受損甚至受到懲罰。所以，航空公司之間如何通過協(xié)商合作來獲得盡可能多的除冰資源，最大程度地利用申請(qǐng)到的資源，以及將因違約而帶來的損失降至最小，成為航空公司首要考慮的問題。

如圖1所示，當(dāng)不同航空公司的航班處于狀態(tài)1和狀態(tài)2時(shí)，各自的策略空間及定性收益如表1所示。其中，X表示沒有申請(qǐng)到除冰資源的航空公司的策略，Y表示申請(qǐng)到資源的航空公司的策略。

圖1 航班從降落到起飛的簡易流程圖Fig.1 Flowchart of aircraft deicing operation

表1 除冰資源申請(qǐng)過程中航空公司的策略空間及支付Tab.1 Airline′s sets of strategy and payoffs

在申請(qǐng)除冰資源時(shí)，各航空公司為了自己的航班不延誤，其個(gè)體理性條件下最優(yōu)策略都是申請(qǐng)資源。但是由于除冰資源有限，其申請(qǐng)成功的概率設(shè)為P。未申請(qǐng)到資源的航空公司只有等待申請(qǐng)下一時(shí)段的資源或者等待其他航空公司轉(zhuǎn)讓申請(qǐng)到的資源。

申請(qǐng)到除冰資源的航空公司，一般情況下選擇自己使用資源。當(dāng)由于某種原因不能及時(shí)到達(dá)機(jī)場除冰時(shí)，有兩種選擇：直接違約或?qū)①Y源轉(zhuǎn)讓。直接違約將會(huì)影響該航空公司的信譽(yù)度以及受到懲罰，所以，此時(shí)的最優(yōu)策略是將資源轉(zhuǎn)讓，即在申請(qǐng)資源的過程中各航空公司進(jìn)行協(xié)商合作。合作能實(shí)現(xiàn)多贏，不合作則集體受損。假設(shè)，加入合作組織的航空公司，在申請(qǐng)資源的過程中具有比未加入組織的航空公司更高的可能性，并且會(huì)較大幾率地得到別的成員轉(zhuǎn)讓的資源和將自己即將造成違約的資源轉(zhuǎn)讓出去。

合作組織不可能自發(fā)形成，也可能由于成員外博弈方的利誘而破裂。所以，除了提高可保證實(shí)現(xiàn)的最大合作總得益之外，還要引進(jìn)一定的措施來懲罰試圖瓦解合作的成員。

除冰資源申請(qǐng)過程中，在合作組織內(nèi)部，成員的不合作行為表現(xiàn)為，為了獲取更大的收益，將自己不用的申請(qǐng)到的資源轉(zhuǎn)讓給組織外部的航空公司，并且此時(shí)組織內(nèi)部有需要除冰而未申請(qǐng)到資源的成員。

在一次除冰資源處理的博弈中，假設(shè)某個(gè)航空公司的收益為k，其一次沒有合作（將除冰資源轉(zhuǎn)讓給組織外的航空公司）而獲得較大的收益為j。懲罰措施為，其他組織成員在此后的資源處理中不與其合作，這家航空公司的收益變?yōu)閘，且j>k>l。

假設(shè)航空公司一直存在，所以這種除冰資源申請(qǐng)過程可視為無限次重復(fù)博弈。為了便于分析航空公司合作與不合作收益的大小，需將以后的收益折算為現(xiàn)在的值，故引入貼現(xiàn)率r（r≥0）。

某航空公司若在本次博弈中合作，其總收益為

若在本次不合作，總收益為

令合作收益大于不合作收益，即A>B，則得

式（3）是懲罰有效的前提，即使某一航空公司在本次資源申請(qǐng)博弈中采取合作的條件。在無限次重復(fù)博弈情況下，只要貼現(xiàn)率r小于某一值，航空公司組織采取的懲罰就是有效的，成員會(huì)自動(dòng)選擇合作。

在航空公司申請(qǐng)除冰資源的博弈過程中，某些成員往往會(huì)采取私利的策略性行為，從而使合作無法形成。因此，合作組織需要采取有效的措施，使合作成為各個(gè)航空公司的最優(yōu)策略。為此，下一節(jié)提出了一種改進(jìn)的航空公司協(xié)商算法。

3 基于Agent效用的協(xié)商算法設(shè)計(jì)

協(xié)調(diào)的主體是各駐場航空公司，航空公司Agent之間各自處于相對(duì)平等的地位，彼此通信協(xié)調(diào)選擇各自的伙伴參與協(xié)商聯(lián)盟，是基于協(xié)商的協(xié)調(diào)，協(xié)商決策完全為航空公司Agent的自主行為。整個(gè)過程是以Agent效用為基礎(chǔ)的合作選擇過程。

定義1 駐場航空公司協(xié)商是一個(gè)多元組〈T，Agt，C，δ，Utility〉，其中：

1）T={T1，T2，T3，…，Ti，…}為協(xié)商行為集合；

2）Agt={Agent1，Agent2，…，Agenti，…}為參與協(xié)商的駐場航空公司Agent；

3）C：?（T）→R+，?（φ）=0 為協(xié)商代價(jià)；

4）δ={TY，TN}為伙伴任務(wù)集合；

式中：utility（δ）Y為手握除冰資源方Agent的協(xié)商效用；utility（δ）N為除冰資源請(qǐng)求方Agent接收除冰資源的效用。設(shè)手握除冰資源方Agent為Agent iY，資源請(qǐng)求方 Agent為 Agent jN。Agent iY的內(nèi)在成本為 C（TY0），即Agent iY執(zhí)行違約的成本，其聯(lián)結(jié)成本即協(xié)商成本為 C（TY）。Agent jN的內(nèi)在成本為 C（TN0），聯(lián)結(jié)成本為C（TN）。C（TY0）、C（TY）、C（TN）、C（TN0）的算法如下

由于各個(gè)航空公司Agent追求各自效益最大化，這里的目標(biāo)函數(shù)為Agent協(xié)商效用最大化，即max[utility（δ）Y，utility（δ）N]，則約束條件為：Agent jN的侯選伙伴滿足1≤Agent iN≤2，且ST≤S。其中：TY0為Agent iN執(zhí)行違約行為；TN0為Agent jN執(zhí)行等待，不參與協(xié)商；TY為Agent iN出讓資源，不做違約行為；TN為Agent jN接受Agent iN出讓的除冰資源，不執(zhí)行等待；α1為調(diào)節(jié)系數(shù)；S為計(jì)劃起飛時(shí)間；ST為實(shí)際起飛時(shí)間。

4 仿真結(jié)果與分析

對(duì)于此合作組織，用除冰費(fèi)用分?jǐn)偟暮侠硇詠碓u(píng)價(jià)其公平性。費(fèi)用分?jǐn)偠x為某航空公司因?yàn)楹桨嘌诱`而浪費(fèi)掉已經(jīng)申請(qǐng)的除冰資源所需要支付的費(fèi)用。采用基于Agent效用的協(xié)商算法結(jié)合Shapley值[8]解方法解決除冰費(fèi)用如何公平分?jǐn)偟膯栴}，根據(jù)各局中人給組織的增值，把組織的總支付分配給各局中人。然后，與幾種常見費(fèi)用分?jǐn)偡桨缸霰容^，對(duì)比出所給分?jǐn)偡桨傅暮侠硇浴?/p>

分析中采用的數(shù)據(jù)為首都國際機(jī)場2010年1月某日00：00—24：00時(shí)國內(nèi) 3家大型航空公司（分別記為a、b、c）航班出港情況。輸出分配圖形由Matlab軟件繪出?？紤]到只有規(guī)模接近的、占市場份額較大的航空公司之間才有較大的形成組織的可能，故在此也只以3家航空公司的組織作為研究對(duì)象。

為使計(jì)算模型簡化，假設(shè)所有飛機(jī)浪費(fèi)掉申請(qǐng)到的除冰資源所需要的支出均為1。3家航空公司申請(qǐng)除冰資源成功的概率和之后違約的概率依次分別為50%和40%、30%和50%、30%和60%。此日，3家航空公司所需支出的違約費(fèi)用分別為f（a）=48，f（b）=13.5，f（c）=18。

通過首都機(jī)場當(dāng)日航班時(shí)刻表可知，在某些時(shí)刻，航空公司a的航班即將違約，而其他航空公司的航班正在等待除冰資源，此時(shí)，兩個(gè)航空公司若同為合作組織成員即可轉(zhuǎn)讓除冰資源，以使整體收益最大化。事實(shí)上，若a、b、c兩兩單獨(dú)合作，有f（a，b）=55，f（a，c）=50，f（b，c）=20。若a、b、c結(jié)盟，有f（a，b，c）=55。此組織的 Shapley值 φ =（40、7.7、7.4）。

如圖2所示，3個(gè)航空公司按照Shapley值分配的違約費(fèi)用分別為40、7.7、7.4。下面考慮傳統(tǒng)分配方法：“按初始增量取費(fèi)”。

“初始增量（initial increment）”：以局中人單獨(dú)所需費(fèi)用之比作為分?jǐn)傎M(fèi)用的比例標(biāo)準(zhǔn)，即f（a，b，c）=55按f（a）∶f（b）∶f（c）=48∶13.5∶18的比例分?jǐn)偨o3家航空公司，得分?jǐn)傁蛄浚害?=（33，9.3，12.3），如圖 3所示。

可以看出，在分?jǐn)偡桨甫林?，α承?dān)的費(fèi)用太少，致使b和c承擔(dān)費(fèi)用太多，不如獨(dú)立出來單獨(dú)合作，而最終導(dǎo)致組織破裂；而本文采用的基于Agent效用的協(xié)商算法結(jié)合Shapley值解分析的方法較公平地進(jìn)行了除冰費(fèi)用分配，保證了合作組織的穩(wěn)定性；由于采用合作策略同時(shí)也降低了合作組織總體費(fèi)用，使得總體和支付最大化。仿真實(shí)驗(yàn)證明了本方法的有效性和穩(wěn)定性。

5 結(jié)語

本文運(yùn)用博弈論中N人合作對(duì)策的思想，分析了存在合作協(xié)商的飛機(jī)地面除冰調(diào)度問題，將航空公司合作組織中各博弈方的資源轉(zhuǎn)讓策略作為研究的切入點(diǎn)，分析飛機(jī)除冰資源申請(qǐng)過程航空公司的博弈行為及其經(jīng)濟(jì)績效，設(shè)計(jì)了各航空公司合作基礎(chǔ)之上的協(xié)調(diào)算法并進(jìn)行仿真分析，結(jié)論如下：

1）除冰資源申請(qǐng)過程中，各航空公司合作能實(shí)現(xiàn)共贏，給每個(gè)航空公司帶來最大收益。然而，合作組織不能自發(fā)形成，航空公司作為自治主體具備私利性，且由于各博弈方地位關(guān)系的不對(duì)稱而導(dǎo)致組織不斷分化瓦解。本文對(duì)合作博弈解的穩(wěn)定存在條件進(jìn)行了分析，并采用違約懲罰機(jī)制，保證了合作組織存在的合理性，為下一步設(shè)計(jì)成員協(xié)商算法打下基礎(chǔ)。

2）以多Agent協(xié)調(diào)協(xié)商相關(guān)理論為依據(jù)，對(duì)以Agent效用為基礎(chǔ)的合作選擇過程進(jìn)行協(xié)商算法設(shè)計(jì)。

3）采用基于Agent效用的協(xié)商算法結(jié)合Shapley值解分析的方法對(duì)除冰費(fèi)用分?jǐn)偟暮侠硇赃M(jìn)行仿真。結(jié)果顯示，此方法較公平地進(jìn)行了除冰費(fèi)用分配，保證了合作組織的穩(wěn)定性，同時(shí)降低了合作組織總體費(fèi)用，使得總體和支付最大化，對(duì)飛機(jī)除冰資源申請(qǐng)過程進(jìn)行了進(jìn)一步的優(yōu)化。

[1]趙 青，馮香玲.飛機(jī)除冰程序與減少航班延誤關(guān)系的分析[J].機(jī)場建設(shè)，2001（1）：3-9.

[2]邢志偉，李 軼.飛機(jī)地面除冰運(yùn)行延誤分析與調(diào)度方法[J].信息與控制，2010，39（6）：743-748.

[3]黃武軍，劉天虎.N人合作博弈的Nash及演化均衡穩(wěn)定策略分析[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（17）：11-14.

[4]XI Y G，WANG C J.The game theory applications in control planning and scheduling problems[J].Journal of China Jiliang University，2005，16（1）：8-16.

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

[6]XING ZHI-WEI，LI YI.Research of Algorithms for Aircraft Ground Deicing Operation Scheduling Model[C]//Proceedings of the 8th World Congress on Intelligent Control and Automation（WCICA2010），Jinan，China，2010：5973-5977.

[7]姚 韻，朱金福，柏明國.航班過站地面服務(wù)的優(yōu)化調(diào)度算法[J].信息與控制，2007，36（4）：486-492.

[8]于曉輝，張 強(qiáng).基于區(qū)間Shapley值的生產(chǎn)合作利益分配研究[J].北京理工大學(xué)學(xué)報(bào)，2008，28（7）：257-267.