邢志偉，張彭城

（1.中國民航大學民航地面特種設備研究基地，天津 300300；2.中國民航大學航空自動化學院，天津 300300）

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

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

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

1 除冰資源預約分配過程簡介

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

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

2 除冰資源申請中航空公司的博弈

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式中：utility（δ）Y為手握除冰資源方Agent的協(xié)商效用；utility（δ）N為除冰資源請求方Agent接收除冰資源的效用。設手握除冰資源方Agent為Agent iY，資源請求方 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）的算法如下

由于各個航空公司Agent追求各自效益最大化，這里的目標函數(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為計劃起飛時間；ST為實際起飛時間。

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

對于此合作組織，用除冰費用分攤的合理性來評價其公平性。費用分攤定義為某航空公司因為航班延誤而浪費掉已經(jīng)申請的除冰資源所需要支付的費用。采用基于Agent效用的協(xié)商算法結(jié)合Shapley值[8]解方法解決除冰費用如何公平分攤的問題，根據(jù)各局中人給組織的增值，把組織的總支付分配給各局中人。然后，與幾種常見費用分攤方案做比較，對比出所給分攤方案的合理性。

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

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

通過首都機場當日航班時刻表可知，在某些時刻，航空公司a的航班即將違約，而其他航空公司的航班正在等待除冰資源，此時，兩個航空公司若同為合作組織成員即可轉(zhuǎn)讓除冰資源，以使整體收益最大化。事實上，若a、b、c兩兩單獨合作，有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個航空公司按照Shapley值分配的違約費用分別為40、7.7、7.4。下面考慮傳統(tǒng)分配方法：“按初始增量取費”。

“初始增量（initial increment）”：以局中人單獨所需費用之比作為分攤費用的比例標準，即f（a，b，c）=55按f（a）∶f（b）∶f（c）=48∶13.5∶18的比例分攤給3家航空公司，得分攤向量：α =（33，9.3，12.3），如圖 3所示。

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

5 結(jié)語

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

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

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

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

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

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

[3]黃武軍，劉天虎.N人合作博弈的Nash及演化均衡穩(wěn)定策略分析[J].計算機工程與應用，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]姚 韻，朱金福，柏明國.航班過站地面服務的優(yōu)化調(diào)度算法[J].信息與控制，2007，36（4）：486-492.

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