飞机地面除冰运行的短进程优化调度方法综述

李连成?乔迪

摘 要 在除冰资源有限的条件下，飞机全面有效的除冰对飞机减少延误与事故有着很大的影响。因小型机的除冰时间短，除冰效率高，且后面分析的得到在总延误时间中小型机的权重比例最大，所以將各航空公司的小型机进行优先调度即为短进程优先调度。考虑到航空公司，机场运控中心，地面服务公司三者之间的利益平衡问题，在优先对小型机进行调度的前提下，使用了短进程优化调度的合作博弈算法与非合作博弈算法，并于先到先服务的算法进行仿真分析，最终得到短进程优先调度的合作博弈与非合作博弈算法既能减小总延误时间又能达到三者的利益平衡。

关键词 资源有限;短进程合作博弈;短进程非合作博弈;调度模型

Abstract Under the condition of limited de icing resources， the comprehensive and effective De icing of aircraft has a great impact on the reduction of aircraft delay and accidents. Due to the short deicing time and high deicing efficiency of minicomputer， and the weight proportion of minicomputer is the largest in the total delay time， so the priority scheduling of Minicomputer in each airline is short process priority scheduling. Considering the balance of interests among airlines， airport operation control center and ground service company， the cooperative game algorithm and non cooperative game algorithm of short process optimal scheduling are used on the premise of giving priority to the scheduling of small-sized aircrafts， and the simulation analysis of the algorithm of first come first serve is carried out， finally the cooperative game and non cooperative game algorithm of short process priority scheduling are obtained. It can not only reduce the total delay time， but also achieve the balance of interests of the three party.

Key words Limited resources; Short Process Cooperative Game; Short-process non-cooperative game; Scheduling model

引言

随着我国的民航事业迅速发展，航班的起飞降落数量在各大机场都有了大幅度的增长，那么在入冬之后如若遇到除冰坪数量不够或除冰所需设备紧缺的情况下，对有限资源的合理调度成为影响飞机航班延误，乘客滞留的关键问题。目前我国大部分机场依然使用着先到先服务的除冰调度方案。该方案虽然可实施性最高，但是存在着除冰效率较低，飞机延误情况出现较多的问题。所以一些更为优化的方案急需被引用。

利用遗传算法设计的除冰设备的调度模型，以及基于博弈论的相关知识，是对单除冰坪和多除冰坪资源分配问题做了系统的研究，并且取得很好的效果，但需要进一步完善。也有队列模型、非合作博弈、合作博弈等一些算法考虑资源的调度，主要考虑多方的利益均衡，将机场除冰设备默认为资源充足[1]。那么在考虑到资源短缺，并且满足利益均衡的条件下，提出了短进程优先调度的合作博弈算法以及非博弈算法。短进程优先调度的方法是以进程的运行时间长度作为优先级，进程运行时间越短，优先级越高。那么在机场的除冰调度运行中首先应该考虑到飞机中占大多数的飞机仍然是中小型客机，它们的除冰时间更短，那么短进程优先调度可用在机场除冰运行调度中[2]。

将短进程优先调度的合作博弈算法以及非博弈算法与先到先服务的调度方法三者之间进行相比，短进程优先调度具有更小的延误时间，且实现了利益均衡。

1除冰建模

飞机除冰主要是由以下环节来完成，首先由机场根据各航空公司的信誉度以及航班数量等条件进行了除冰排序，各航空公司根据已知的除冰排序提出除冰申请，申请通过后，乘客进行登机，飞机进入除冰坪，除冰完毕后，飞机进入轨道起飞，分步流程如图1所示：

表示的飞机刚进入停机坪的那一时刻，表示的飞机除冰完成的那一时刻，表示的飞机的除冰时间。

在飞机的除冰过程中，机场本身希望越多的飞机起飞，这样可以减少航班的总延误时间，而航空公司本身则希望自家公司飞机起飞越多越好，希望自己优先使用资源而不会考虑其他公司。第三节所提到的合作博弈和非合作博弈将解决利益的平衡问题。在利益平衡的前提下，达到最小的延误总时间。最终得到目标方程：

此时还应该考虑到飞机除冰液的时效问题，如果除冰在预计起飞时间前完成，则飞机能够起飞，否则超过了除冰液的时效会存在飞机二次结冰的问题，如若遇到这种问题则需要再次除冰，此种情况出现时，会对资源造成浪费，所以需要在除冰模型中需加入约束条件。国内普遍使用的除冰液时效为15分钟。那么该限制条件为：

在此目的模型的约束下，来分析短进程优先调度的合作博弈算法以及非博弈算法。

2短进程优先调度模型

2.1 短进程优先调度的合作博弈算法

為了方便计算，假设飞机的除冰时刻是从0时刻开始的，这样就大大简化了计算的过程。我们假设是飞机进行到第个进程的时候要除冰的时间。是个进程的完成瞬间。对上一节的除冰模型进行短进程处理：

不难得到，对总延误时间的影响最大，拥有最大的权重系数。然后依次是，具有次权重系数，以此类推，最后一个进程为最小的权重系数。在飞机的除冰过程中，小型与中型飞机占飞机总数的大部分，所以优先对小型与中型飞机进行除冰，即小型中型飞机的在除冰进程的前面，权重系数影响较大，对总延误时间的影响最小[3]。

我们选取类似波音737的飞机，假定为A型机为小型机。类似波音747的飞机，假定为B型机为中型机。类似空客A—380的飞机，假定为C型机为大型机。因为除冰坪的大小有限，选取大部分机场所使用的除冰坪大小，可以同时处理两架A型机或一架B型，C型机。机场数据反应，A型机的除冰时间7分钟，B型机的除冰时间10分钟，C型机的除冰时间15分钟。一般机场的除冰坪数量保持不变，以航班的起飞确定，实际起飞前5分钟已经完成所有工作为前提。根据之前已经得到0时刻开始的飞机除冰总延误时间，当规定为个进程飞机原定起飞时间，得到更具有实际意义的短进程优先调度的总延误时间：

综上，要想总延误时间最短，当资源有限的时候，对小型机的优先除冰，可以得到很好的效果。

在对小型机进行优先调度的同时，还应该考虑到航空公司，机场调度中心，地面服务公司三者之间的利益平衡问题，我们首先使用合作博弈的方法解决这个问题。在合作博弈中，是以小型机优先调度为前提，合作利益大于单个利益之和，同时在合作方之间的利益分配公平。

我们以合作博弈中的基本问题“二人合作博弈”进行研究。两个除冰主体任何一个都不能对整体做出策略要求，而是双方进行合理的分配的方案。那么在两者之间就会存在着一些诸如利益转让、分割等问题。所以要考虑双方的风险态度和主观效用评价。但是，任何合作都是不牢靠的，当博弈双方的合作关系破裂时，双方依然能够得到一些利益，这种谈判破裂时双方的利益称为“谈判破裂点”，通常用表示，其中是博弈方在谈判破裂时可以得到的利益[4]。

我们假设，为除冰的资源的分配集合，可以得到，m是最大的可分配期望支付。，每个除冰的主体自身利益的函数。那么，，为两个除冰主体各自的利益函数。我们就可以得到合作博弈三元数组：

2.2 短进程优先调度的非合作博弈算法

短进程优先算法与上一节一样。分析非合作博弈算法，非合作博弈与合作博弈相反，在此算法中没有合作存在，统一对资源进行争夺。此时必须进行好合理的资源调度方案。把航空公司，机场调度中心，地面服务公司三者看成非合作博弈的三个博弈方，三者之间是相互联系的，与合作博弈不同，非合作博弈每个博弈方都有自己的决策函数[5]。

假设是航空公司，是机场调度中心，是地面服务公司。是航空公司的申请策略集合，是机场调度中心分配的优先级，是机场调度中心的决策集合。是决策时的资源效用[6]。最终得到非合作博弈算法：

3仿真结果与分析

以北京首都国际机场的某天的航班数据为仿真数据，使用python进行仿真。在各大机场中一般除冰坪的数量是小于等于4的，我们来计算短进程优先调度的合作博弈算法和非合作博算法以及先到先服务的算法，三者之间进行比较。最终得到仿真结果如下折线图：

最终总结如下表1。

4结束语

使用了短进程优化调度下的合作博弈算法和非合作博弈算法，发现短进程优先调度的方法利用了小型机优先调度的时间少的除冰优势，最大限度地将有限资源利用减少总延误时间，与先到先服务的方法比较有很大优势。而且在三方利益平衡方面，短进程下的合作博弈算法更有优势，所以可以使用小型机优先除冰调度的方法下的合作博弈算法，将会使延误时间最小化，利益最均匀化。

参考文献

[1] 石旭东，王立文，刘胜飞.飞机集中除冰车辆优化调度方法研究[J].计算机工程与应用，2009，45（4）：218-220.

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

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

[4] XingZhiwei，LiJunhui.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.

[5] Voulgarellis P G，Christodoulou M A，Boutalis Y S. A MATLAB Based Simulation Language for Aircraft Ground Handling Operations at Hub Airports （SLAGOM）[C].Intelligent Control，2005. Proceedings of the 2005 IEEE International Symposium on，Mediterrean Conference on Control and Automation. IEEE，2005：334-339.

[6] MAO XY，MORS AT，ROOS N，et al. Agent-Based Scheduling for Aircraft Deicing[C]. Proceedings of the 18th Belgium-Netherlands Conference on Artificial Intelligence，2007：229-236.