飞机除冰资源申请过程航空公司的博弈研究

邢志伟，张彭城

（1.中国民航大学民航地面特种设备研究基地，天津 300300；2.中国民航大学航空自动化学院，天津 300300）

飞机结冰是影响民航机场冬季航班安全的关键问题之一。同时，飞机地面除冰效率低下也是造成冰雪天气大型枢纽机场航班大面积延误的直接原因之一。在除冰设备固定的情况下，飞机地面除冰过程的调度与优化则成为影响飞机地面除冰质量和效率的关键。

飞机地面除冰过程是一种典型的随机服务系统。现行的飞机地面除冰过程大多数实行的是先到先服务方式。冰雪天气情况下，各航空公司下属航班均到除冰坪统一排队等候。这种除冰模式最为简单，但是效率也较低，没有考虑航空公司的信誉度和航班的紧急程度而采取有针对性的排队方式，因而在冬季飞机起飞较集中的时段，容易造成大面积航班延误。

目前，国内外专门针对飞机地面除冰运行调度问题的研究还处于起步阶段。赵青、冯香玲[1]等人研究了飞机地面除冰整体操作过程中可提高除冰效率的程序；邢志伟、李轶[2]建立了基于Multi-Agent的预约除冰模型，按照各航空公司的信誉度高低来分配除冰资源，极大地提高了飞机地面除冰过程的效率，同时兼顾了各航空公司的公平性和除冰资源的利用规律，为飞机地面除冰调度开辟了新的途径。然而上述研究在航空公司申请资源的处理上考虑有欠周全，各航空公司之间没有有效的协商合作机制，从而造成了一部分除冰资源的浪费，同时也没有涉及对于航空公司申请到除冰资源后的违约问题。本文在邢志伟、李轶等人建立的基于Multi-Agent飞机地面除冰运行模型的基础上，以合作博弈[3-7]为分析工具，研究如何建立各航空公司之间的合作组织，分析航空公司在除冰资源申请过程中的博弈行为，从而使航空公司组织的利益最大化。最后通过分析合作前后收益的变化，来验证这种合作组织的合理性和有效性。

1 除冰资源预约分配过程简介

机场除冰调度并非实时调度，而是采取预先分配资源的策略，在规划时间上进行除冰资源的预先分配机场指挥中心和地面服务公司通信，取得往后1 h内的除冰申请航班信息以及这段时间内的可用除冰资源，规划完毕后发送分配信息给航空公司确认，收到航空公司的确认信息之后即完成一个周期。

航空公司在申请除冰资源的过程中，机场指挥调度中心根据各个航空公司的信誉度来判定其申请资源的优先级。优先级高的航空公司申请到除冰资源的概率较高。航空公司的信誉度由其在申请到除冰资源之后是否能及时赶到现场除冰来判断。规定此除冰系统模型中，因航班自身问题而不能及时到达除冰坪使用已经申请到的资源时，此航班所属航空公司需支付违约费用。

2 除冰资源申请中航空公司的博弈

对于航空公司来说，机场除冰资源相对短缺，尤其在飞机集中起飞的时刻，如何申请到除冰资源和保证及时除冰、按时起飞是每个航空公司首要考虑的问题；其次，当申请到除冰资源后，航空公司下属的某个航班由于某种原因不能及时到达机场，由于采用预约制，此时的除冰资源不能再用于其他航班，而浪费了资源；同时，此违约的航空公司也要因为违约而信誉受损甚至受到惩罚。所以，航空公司之间如何通过协商合作来获得尽可能多的除冰资源，最大程度地利用申请到的资源，以及将因违约而带来的损失降至最小，成为航空公司首要考虑的问题。

如图1所示，当不同航空公司的航班处于状态1和状态2时，各自的策略空间及定性收益如表1所示。其中，X表示没有申请到除冰资源的航空公司的策略，Y表示申请到资源的航空公司的策略。

图1 航班从降落到起飞的简易流程图Fig.1 Flowchart of aircraft deicing operation

表1 除冰资源申请过程中航空公司的策略空间及支付Tab.1 Airline′s sets of strategy and payoffs

在申请除冰资源时，各航空公司为了自己的航班不延误，其个体理性条件下最优策略都是申请资源。但是由于除冰资源有限，其申请成功的概率设为P。未申请到资源的航空公司只有等待申请下一时段的资源或者等待其他航空公司转让申请到的资源。

申请到除冰资源的航空公司，一般情况下选择自己使用资源。当由于某种原因不能及时到达机场除冰时，有两种选择：直接违约或将资源转让。直接违约将会影响该航空公司的信誉度以及受到惩罚，所以，此时的最优策略是将资源转让，即在申请资源的过程中各航空公司进行协商合作。合作能实现多赢，不合作则集体受损。假设，加入合作组织的航空公司，在申请资源的过程中具有比未加入组织的航空公司更高的可能性，并且会较大几率地得到别的成员转让的资源和将自己即将造成违约的资源转让出去。

合作组织不可能自发形成，也可能由于成员外博弈方的利诱而破裂。所以，除了提高可保证实现的最大合作总得益之外，还要引进一定的措施来惩罚试图瓦解合作的成员。

除冰资源申请过程中，在合作组织内部，成员的不合作行为表现为，为了获取更大的收益，将自己不用的申请到的资源转让给组织外部的航空公司，并且此时组织内部有需要除冰而未申请到资源的成员。

在一次除冰资源处理的博弈中，假设某个航空公司的收益为k，其一次没有合作（将除冰资源转让给组织外的航空公司）而获得较大的收益为j。惩罚措施为，其他组织成员在此后的资源处理中不与其合作，这家航空公司的收益变为l，且j>k>l。

假设航空公司一直存在，所以这种除冰资源申请过程可视为无限次重复博弈。为了便于分析航空公司合作与不合作收益的大小，需将以后的收益折算为现在的值，故引入贴现率r（r≥0）。

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

若在本次不合作，总收益为

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

式（3）是惩罚有效的前提，即使某一航空公司在本次资源申请博弈中采取合作的条件。在无限次重复博弈情况下，只要贴现率r小于某一值，航空公司组织采取的惩罚就是有效的，成员会自动选择合作。

在航空公司申请除冰资源的博弈过程中，某些成员往往会采取私利的策略性行为，从而使合作无法形成。因此，合作组织需要采取有效的措施，使合作成为各个航空公司的最优策略。为此，下一节提出了一种改进的航空公司协商算法。

3 基于Agent效用的协商算法设计

协调的主体是各驻场航空公司，航空公司Agent之间各自处于相对平等的地位，彼此通信协调选择各自的伙伴参与协商联盟，是基于协商的协调，协商决策完全为航空公司Agent的自主行为。整个过程是以Agent效用为基础的合作选择过程。

定义1 驻场航空公司协商是一个多元组〈T，Agt，C，δ，Utility〉，其中：

1）T={T1，T2，T3，…，Ti，…}为协商行为集合；

2）Agt={Agent1，Agent2，…，Agenti，…}为参与协商的驻场航空公司Agent；

3）C：ϑ（T）→R+，ϑ（φ）=0 为协商代价；

4）δ={TY，TN}为伙伴任务集合；

式中：utility（δ）Y为手握除冰资源方Agent的协商效用；utility（δ）N为除冰资源请求方Agent接收除冰资源的效用。设手握除冰资源方Agent为Agent iY，资源请求方 Agent为 Agent jN。Agent iY的内在成本为 C（TY0），即Agent iY执行违约的成本，其联结成本即协商成本为 C（TY）。Agent jN的内在成本为 C（TN0），联结成本为C（TN）。C（TY0）、C（TY）、C（TN）、C（TN0）的算法如下

由于各个航空公司Agent追求各自效益最大化，这里的目标函数为Agent协商效用最大化，即max[utility（δ）Y，utility（δ）N]，则约束条件为：Agent jN的侯选伙伴满足1≤Agent iN≤2，且ST≤S。其中：TY0为Agent iN执行违约行为；TN0为Agent jN执行等待，不参与协商；TY为Agent iN出让资源，不做违约行为；TN为Agent jN接受Agent iN出让的除冰资源，不执行等待；α1为调节系数；S为计划起飞时间；ST为实际起飞时间。

4 仿真结果与分析

对于此合作组织，用除冰费用分摊的合理性来评价其公平性。费用分摊定义为某航空公司因为航班延误而浪费掉已经申请的除冰资源所需要支付的费用。采用基于Agent效用的协商算法结合Shapley值[8]解方法解决除冰费用如何公平分摊的问题，根据各局中人给组织的增值，把组织的总支付分配给各局中人。然后，与几种常见费用分摊方案做比较，对比出所给分摊方案的合理性。

分析中采用的数据为首都国际机场2010年1月某日00：00—24：00时国内 3家大型航空公司（分别记为a、b、c）航班出港情况。输出分配图形由Matlab软件绘出。考虑到只有规模接近的、占市场份额较大的航空公司之间才有较大的形成组织的可能，故在此也只以3家航空公司的组织作为研究对象。

为使计算模型简化，假设所有飞机浪费掉申请到的除冰资源所需要的支出均为1。3家航空公司申请除冰资源成功的概率和之后违约的概率依次分别为50%和40%、30%和50%、30%和60%。此日，3家航空公司所需支出的违约费用分别为f（a）=48，f（b）=13.5，f（c）=18。

通过首都机场当日航班时刻表可知，在某些时刻，航空公司a的航班即将违约，而其他航空公司的航班正在等待除冰资源，此时，两个航空公司若同为合作组织成员即可转让除冰资源，以使整体收益最大化。事实上，若a、b、c两两单独合作，有f（a，b）=55，f（a，c）=50，f（b，c）=20。若a、b、c结盟，有f（a，b，c）=55。此组织的 Shapley值 φ =（40、7.7、7.4）。

如图2所示，3个航空公司按照Shapley值分配的违约费用分别为40、7.7、7.4。下面考虑传统分配方法：“按初始增量取费”。

“初始增量（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效用的协商算法结合Shapley值解分析的方法较公平地进行了除冰费用分配，保证了合作组织的稳定性；由于采用合作策略同时也降低了合作组织总体费用，使得总体和支付最大化。仿真实验证明了本方法的有效性和稳定性。

5 结语

本文运用博弈论中N人合作对策的思想，分析了存在合作协商的飞机地面除冰调度问题，将航空公司合作组织中各博弈方的资源转让策略作为研究的切入点，分析飞机除冰资源申请过程航空公司的博弈行为及其经济绩效，设计了各航空公司合作基础之上的协调算法并进行仿真分析，结论如下：

1）除冰资源申请过程中，各航空公司合作能实现共赢，给每个航空公司带来最大收益。然而，合作组织不能自发形成，航空公司作为自治主体具备私利性，且由于各博弈方地位关系的不对称而导致组织不断分化瓦解。本文对合作博弈解的稳定存在条件进行了分析，并采用违约惩罚机制，保证了合作组织存在的合理性，为下一步设计成员协商算法打下基础。

2）以多Agent协调协商相关理论为依据，对以Agent效用为基础的合作选择过程进行协商算法设计。

3）采用基于Agent效用的协商算法结合Shapley值解分析的方法对除冰费用分摊的合理性进行仿真。结果显示，此方法较公平地进行了除冰费用分配，保证了合作组织的稳定性，同时降低了合作组织总体费用，使得总体和支付最大化，对飞机除冰资源申请过程进行了进一步的优化。

[1]赵 青，冯香玲.飞机除冰程序与减少航班延误关系的分析[J].机场建设，2001（1）：3-9.

[2]邢志伟，李 轶.飞机地面除冰运行延误分析与调度方法[J].信息与控制，2010，39（6）：743-748.

[3]黄武军，刘天虎.N人合作博弈的Nash及演化均衡稳定策略分析[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]姚 韵，朱金福，柏明国.航班过站地面服务的优化调度算法[J].信息与控制，2007，36（4）：486-492.

[8]于晓辉，张 强.基于区间Shapley值的生产合作利益分配研究[J].北京理工大学学报，2008，28（7）：257-267.