飞机地面除冰运行调度模型研究

张 伟，李 彪

（1.北京首都国际机场股份有限公司，北京 100000；2.中国民航大学电子信息与自动化学院，天津 300300）

飞机地面除冰运行调度模型研究

张 伟1，李 彪2

（1.北京首都国际机场股份有限公司，北京 100000；2.中国民航大学电子信息与自动化学院，天津 300300）

为保证机场冬季航班的正常运行，避免因除冰不及时造成大面积延误和事故，需对除冰资源进行合理分配使其效用最大化。根据除冰资源条件限制和各参与方的约束条件，提出一种基于博弈分配方案的启发式调度模型。博弈分配方案能够实现资源效率最高，结合启发式算法得到整个调度模型的最优解。使用北京首都国际机场冬季实际运行数据进行模拟仿真验证，表明比单一的博弈模型效果更好。

除冰资源；博弈分配方案；启发式算法；调度模型；最优解

?

对飞机进行全面、有效、准时的除冰成为冬季保证机场正常运行的关键。但是机场配备的除冰设备资源有限，如何在机场现有设备条件下发挥出最大效用，一直是业界研究的问题。

机场设备的调度和运行保障问题，一直都是民航领域的研究热点。Voulgarellis等[1]利用Matlab及其他计算机语言对机场各个重要环节进行模块化和系统化的建模，并在平台对各环节进行仿真，探索各个环节之间的相互关系；Makhloof等[2]介绍了中转航班流程的数学模型，设计了实时保障设备的算法，并在实际条件下得到了应用；Sanya等[3]分析了单航班的一系列过站保障服务作业特性，并使用计算机模拟航班保障服务作业时的多发性干扰，分析其对飞机过站的影响能力，从而建立应急保障计划来应对突发状况；徐瑞时[4]提出了一种新的保障评估模型，并将其应用到人员设备的动态实时调度中。对于除冰雪装备的调度算法设计和构建，民航领域专家已经做了许多研究：Mao、Mors等[5-7]提出了以飞机为系统主体的Multi-Agent模型，并研究了机场除冰运行调度过程，建立了优化算法，但动态响应不佳；石旭东等[8]利用遗传算法设计了除冰设备的调度模型，但没有考虑环境和资源的限制情况；邢志伟等[9-10]基于博弈论的相关知识，对单除冰坪和多除冰坪资源分配问题做了系统的研究，并取得很好的效果，但需进一步完善。

基于以上分析，结合排队论和博弈论的相关知识，本文提出一种在动态博弈资源配置方案基础上的启发式调度算法，利用多航空公司之间的博弈关系，针对有限资源条件下如何实现除冰设备的合理调度和分配，建立了除冰资源的实时调度模型，并与单一的博弈模型进行对比分析。

1 飞机地面除冰流程分析

1.1 飞机除冰调度动态过程分析

飞机除冰调度问题是一个动态、耦合性强、实时性的流程控制和资源分配问题[11]。飞机除冰运行流程如图1所示。

图1 飞机地面除冰运行图Fig.1 Aircraftground deicing operation figure

基本过程描述如下：

在航空公司申请除冰到完成所有地面保障服务的期间，存在许多不确定性事件，例如航班延误出现连锁反应、由于天气原因出现的流量控制等，都会造成航班无法照常运行。所以，在除冰资源信息不对称的情况下如何进行资源的分配，保证航班在除冰资源有限情况下的正常运行，是一个比较重要的问题。对于可控范围博弈的资源分配模式，在某种程度上还是值得鼓励和研究的。

1.2 除冰非合作博弈模式分析

飞机除冰资源的分配方案和实时调度问题一直都是比较典型的带有强约束条件的参数解优化过程。在资源紧张且无法满足全部供应的情况下，航空公司、地服公司、机场除冰指挥3个相对独立的利益方为实现各自的利益而选择的一些策略，符合非合作博弈模式的情况。非合作博弈中，基本主体是希望在除冰过程中以最小支付方式得到最大效用和收益的航空公司和期望除冰资源效率达到最大和获益最大化的机场除冰公司。实际博弈过程就是选择各自博弈方的决策变量和优化目标函数的过程。

非合作博弈过程可视作调度中心、航空公司和地服公司3个参与博弈过程的组织，每个组织都会从自己的角度考虑问题，有其策略和目标，但三者又存在一定的联系，其关系如下

其中：Agta为争夺除冰资源的航空公司集合；AgtDMC为调度中心；AgtGSC为地面服务公司；R为组织中Agent之间的二元关系的集合；Si为申请除冰航班策略集合；Priorityai为分配除冰资源时航空公司的优先级；Sk为决策时的策略集；UDMC为决策时的资源效用。

1.3 除冰合作博弈模式分析

飞机除冰调度合作博弈中，假设该除冰资源分配问题的基本前提成立：即存在一些强有力的约束条件，必须保证其能够强制执行，合作要比对抗得到的结果收益大，同时联盟内部应存在公平有效的分配规则。

两个除冰资源申请方所构成的合作博弈是合作博弈的学者们较早研究的一个基本问题。实际上问题研究的本质并不是选择自己的策略，而是要确定所有的资源分配方案。分配本身就意味着必须对相关利益进行分割和再分配，也是一种相对的除冰资源利益补偿机制。在实际处理过程中必须考虑本身是无法达到最终期望目标的，因此要考虑在除冰资源的博弈过程中对于风险的规避策略和对效用的期望。从另一个角度讲，任何协商都会存在破裂的可能性，在破裂后各方也可能得到的利益称之为“谈判破裂点”，通常用d=（d1，d2）表示，其中 di是博弈方 i在谈判破裂时可以得到的利益[11]。

定义1两个除冰资源申请方的合作博弈。

两个除冰资源申请方的合作博弈问题可表示为一个三元数组，即

其中：S′为除冰资源可行分配集，S′={s1，s2|0≤si≤m}，i=1，2，m 是最大可分配期望支付；u1、u2为两除冰主体各自的效用函数；ui为除冰主体的期望效用（expected utility），ui∶S′→R，ui=ui（s）=ui（si），即效用是除冰主体自身利益的函数；d为两个除冰主体的谈判破裂点，d=（d1，d2）。

基于对飞机地面除冰流程的分析以及非合作博弈和合作博弈两种模式的分析，可得出在除冰流程中，既存在合作博弈，又存在非合作博弈，且参与除冰博弈各方追求的目标和策略并不统一，实际上在单一除冰调度模型下的最优解由于各种原因并不存在。因此除冰资源的运行调度建模过程中必须考虑到以上两种博弈模式，这样才能得出合理的调度模型。

2 除冰运行调度模型

对于飞机地面除冰的实时调度模型，许多研究学者都是基于单一的调度模型来进行优化，取得一定的成果，但并不完善[12]。本文提出基于除冰资源博弈方案的运行调度模型，将两种博弈方案得出的最优解进行合并处理，利用启发式算法进行再优化处理，能够进一步保证解的优化性，实现资源的最优配置。

2.1 飞机除冰合作博弈方案

两个航空公司进行合作博弈实际上是一个约束问题求最优解的过程，即

Nash解是解决实际中存在的非线性优化过程最优解的重要方法之一，其最终目标函数被称为“Nash积”。由于它是一个比较明显的凹函数，但最终生成的集合也是一个凸紧集，所以在除冰方案配置中可能存在最优的情况。

假定某机场有100单位的除冰资源，这些资源对两个航空公司开放使用。第1个航空公司对于风险的规避是风险定常的，即u1=u1（s1）=s1；而第2个航空公司对于风险的态度则是以风险递减为目标，，两个航空公司最终的谈判破裂点在（0，0）。

则该问题用Nash解法转化为求解下列Nash积的约束优化问题，即

根据约束条件可得 u2=（100-u1）a，带入 Nash积转化为单变量最优化问题，即一阶条件为两边乘（100-u1*）a得

从以上分析能够得出，两个航空公司在进行合作博弈时对于风险规避的特性会对谈判的最终结果产生较大的作用。资源分配结果的不同主要由反映风险偏好大小的系数a所决定，风险规避的程度越高，资源分配的倾向和结果就可能越差，效用越低。Nash解法是二人合作博弈问题的最重要解法。Nash解法不仅要满足优化目标效用函数的最大解，而且必须满足各方对于博弈过程中公平和效率的要求。

2.2 飞机除冰非合作博弈方案

非合作博弈是在航空公司没有达成联盟而形成的一种对资源争夺的分配方案，对于这种情况，除冰资源的调度中必须建立好合理的调度规则，保证资源发挥最大的效用，减少航班由于除冰不及时而造成的大面积延误。

具体的资源配置方案如下：首先航空公司进入等待除冰集合，向调度中心发出申请，等待其回复；调度中心根据航空公司的申请情况和历史数据，给出每个航空公司的优先权，然后根据优先权进行排序；根据优先权的顺序，航空公司确定自己的策略集合，决定其除冰上投入的资源；除冰调度中心根据各航空公司的最终策略，确定除冰服务的先后顺序，并将信息传送给地面保障服务公司。具体流程如图2所示。

图2 非合作博弈调度方案生成流程图Fig.2 Non-cooperative game scheduling scheme

2.3 启发式调度优化算法

除冰资源的合理调度是一个求动态最优解的过程，而面对合作博弈和非合作博弈方案的解集，需要寻找一个最优解。启发式算法的主要作用是得出最优解，并对当前最优解的状态进行评价。

本文选择比较传统的贪婪算法作为除冰设备资源运行调度的算法，其采用局部搜索技术快速获取满意解，算法简单且易实现。选择合作博弈和非合作博弈产生的策略方案作为整个除冰资源的调度方案集，以除冰资源设备的效用最大化作为最终目标，且保证场面的航班延误达到最小，具体的算法流程如图3所示。

图3 贪婪算法流程图Fig.3 Flowchartof greedy algorithm

3 算例分析

3.1 数据仿真

以北京首都国际机场冬季某天上午1小时内的航班计划为例，假设此时段有国航、南航和东航3个航空公司，对除冰资源实时调度进行仿真模拟。

首先得到合作博弈和非合作博弈配置方案的策略集，其中需要确定航空公司的优先权以及他们为除冰付出的利益。确定策略集之后以最大效用和除冰资源效益最大化为目标，利用贪婪算法在策略集中寻找最优解。根据实际数据利用Matlab进行模拟，结果如图4所示。

3.2 对比分析

选取相同条件，利用单一合作联盟博弈模型和非合作博弈模型运行后发现，基于资源博弈配置方案的启发式调度模型在控制延误率和资源效用最大化方面表现出不俗的效果，如表1所示。且最大程度上避免了单一启发式算法进行调度时出现的违约事件。实现机场在冬季冰雪条件下的安全和高效运行。

图4 模拟仿真实验结果图Fig.4 Simulation results

表1 模型表现对比分析表Tab.1 Performance comparison and analyses between models

4 结语

基于飞机地面除冰的基本流程，分析了合作博弈和非合作博弈下的资源配置方案，根据构成的调度策略集，利用启发式算法进行最优解的搜索，以实现除冰资源效用和效益的最大化为目标，建立了飞机地面除冰实时调度模型。根据实际数据模拟运行仿真发现，该方案能在最大程度上满足航班的需求，减少航班延误。通过与单一博弈模型进行对比发现，无论是从延误率、资源利用率和效率方面，还是从违约情况和机场效益方面均得到了可接受的结果。

[1]VOULGARELLISPG,CHRISTODOULOU M A,BOUTALISY S.A MATLAB Based Simulation Language for Aircraft Ground Handling Operations at Hub Airports(SLAGOM)[C]//Proceedings of the 2005 IEEE International Symposium on,Mediterrean Conference on Control and Automation,IEEE,2005:334-339.

[2]MAKHLOOFM A A,WAHEEDM E,BADAWIE R,et al.Real-time aircraft turnaround operations manager[J].Production Planning&Control, 2014,25(1):2-25.

[3]SANYA A,CHRISTOPHER C.A simulation based approach for contingency planning for aircraft turnaround operation system activities in airlinehubs[J].Journalof Air Transportation,2006,11(1):140-155.

[4]徐瑞时.繁忙机场地面保障容量评估与优化[D].南京:南京航空航天大学,2014.

[5]MAO X Y,MORSA T,ROOSN,et al.Agent-Based Scheduling for Aircraft Deicing[C]//Proceedings of the 18th Belgium-Netherlands Conference on Artificial Intelligence,Brussels,2007:229-236.

[6]MAO X Y,MORS A T,ROOS N,et al.Using Neuro-Evolution in Aircraft Deicing Scheduling[C]//ALAMAS 2007 Adaptive and Learning Agents and Multi-Agent Systems,Berlin,2007:138-145.

[7]MORSA T,MAOX Y,ROOSN,et al.Multi-Agent Sycstem Support for Scheduling Aircraft De-icing[C]//Proceeding of ISCRAM 2007-Intelligent Human Computer Systems for Crisis Response and Management,Delft,2007:467-478.

[8]石旭东,王立文,刘胜飞．飞机集中除冰车辆优化调度方法研究[J]．计算机工程与应用,2009,45(4):218-220.

[9]邢志伟,唐广群,任 准.多除冰坪排队飞机除冰过程调度非合作博弈[J].信息与控制,2013,42(4):511-515.

[10]邢志伟,乔晓辉.飞机地面除冰运行的非合作博弈研究[J].系统仿真学报,2011,23(3):433-437.

[11]XING Zhiwei,LI Junhui．Research of Game-Theoretic Approach for Aircraft Ground Deicing Operation Scheduling[C]//The 2nd International Conference on Mechanic Automation and Control Engineering(MACE 2011),2011:570-574．

[12]李俊辉.飞机地面除冰调度合作博弈研究[D].天津:中国民航大学,2012.

Research on dispatching model of aircraft ground deicing

ZHANG Wei1,LI Biao2
（1.Beijing Capital International Airport,Beijing 100000,China;2.College of Electronic Information and Automation,CAUC,Tianjin 300300,China）

In order to ensure the normal operation of airport’s winter flights,ovoiding large-scale delays and accidents by deicing in time,a reasonable allocation of de-icing resource is required to maximize its utility.According to the deicing resource conditions and constraints of each participant,a heuristic scheduling model based on game allocation scheme is proposed,Which is able to achieve the highest resource efficiency,getting optimal solution of the whole scheduling model combined with the heuristic algorithm.Simulation with real operation data of Beijing Capital International Airport shows that the current model is better than single game model.

deicing resource;game allocation scheme;heuristic algorithm;scheduling model;optimal solution

张伟（1965—），男，北京人，工程师，硕士，研究方向为机场经营管理.

V351.392；O225

A

1674－5590（2017）05－0022－04

2017-08-06；

2017-08-31

?

刘智勇）