基于改进人工蜂群算法的航班延误调度研究

许环球

摘 要：航班延误是航空公司经济损失的重要组成部分，分析航空公司经济损失的主要构成，构建出以航班延误的经济损失为基础的航班延误恢复调度模型，是降低经济损失的重要方法。针对调度方案的离散性，采用改进的人工蜂群算法，得出最优调度方案。通过实例分析，改进的人工蜂群算法可以有效、准确地选择调度方案，且此算法的收敛速度优于传统的人工蜂群算法。

关键词：航班延误；经济损失；改进人工蜂群算法；调度方案

中图分类号：V355 文献标志码：A 文章编号：2095-2945（2018）33-0015-03

Abstract： Flight delay is an important part of airline economic loss. This paper analyzes the main components of airline economic loss and constructs a flight delay recovery scheduling model based on the economic loss of flight delay， and it is an important way to reduce economic losses. According to the discreteness of the scheduling scheme， the improved artificial bee colony algorithm is used to obtain the optimal scheduling scheme. Through the example analysis， the improved artificial bee colony algorithm can effectively and accurately select the scheduling scheme， and the convergence speed of this algorithm is better than the traditional artificial bee colony algorithm.

Keywords： flight delay； economic loss； improved artificial bee colony algorithm； scheduling scheme

引言

人工蜂群算法是由土耳其学者Karaboga于2005年提出，其思想是启发于蜂群通过个体分工和信息交流，相互协作完成采蜜任务[1]。与经典的优化方法如遗传算法、差分进化算法和粒子群优化算法相比较，人工蜂群算法的求解质量相对较好。针对延误航班的重新调度恢复这一情况的离散特点，利用改进的人工蜂群算法，能够避免传统人工算法求解离散问题时的冗余[2]。

马正平崔德光针对空中交通日益严重的航班延误，给出了一种机场航班延误优化模型。模型将机场的到达和出发视为密切相关的两个过程，考虑了具有连续航程的航班；赵秀丽，朱金福，郭梅构建了以延误成本最小或延误时间最短为目标函数的航班恢复模型，航空公司可以根据需要选择不同的目标函数；李雄，刘光才，颜明池提出了适用于我国的航班延误经济损失计算方法，考虑了延误航班的正常盈利损失，并对我国民航旅客的时闻价值进行了研究； 贺国光针对空运系统日益严重的航班延误，尝试将贝叶斯方法应用于航班数据分析，重点考虑同一飞机飞行连续航班的情况，借助Netica软件包，建立贝叶斯网络模型。

航班延误造成的损失主要包括：直接损失和间接损失。直接损失是指航班延误造成的经济损失，包括航空公司和旅客两部分。间接损失是指延误航班延误造成的航空公司形象信誉方面的损失[3]。本文不考虑这类具有不确定性的间接损失。

1 直接损失

1.1 航空公司经济损失的构成

1.1.1 延误航班的运营成本

航班的运营成本包括停场费、起降费、旅客服务费及相应的地面等待成本，它随着飞机起飞质量增大而增高。根据国际民航组织的标准，可将飞机运营成本按照尾流强弱分为3类。以波音737为例，其每年的固定费用为2500万元，平均到每天约为7万元[3][4]。因此，各机型每小时延误运营成本，如表1。

则飞机航班延误运营成本为：Cfd=at，a为飞机每小时延误的运营成本。

1.1.2 取消航班的损失

取消延误航班会造成航空公司的直接经济损失。取消航班的损失与最大载客数、客座率和平均票价正相关，其关系如下：

Cf=最大载客数×客座率×平均票价

1.1.3 调机成本

调机是指飞机由一个机场调往另一机场，因此其成本由两机场间的距离决定。

1.2 旅客经济损失

针对旅客乘坐的航班类型分类，可以分为国内航班旅客和国际航班旅客，其中每名国内航班旅客平均的延误经济损失约为50元/小时，而每名国际航班旅客平均的经济损失约为100元/小时[5]，可表达为：

Cm=50t，t为航班延误的总时间。

2 航班调度模型

调度恢复是当机场发生较大规模延误后，对已停驻在该机场的飞机和已延误但后期可到达该机场的飞机重新调度，从而使得延误的经济损失最低[6]。调度问题是指派问题的一种，其标准形式如下：设有n个航班和n架飞机，已知第i个单位完成第j项任务的成本为Cij，要求一架飞机和航班之间一一对应的调度方案，使完成这些任务的总成本最小[6][7]。

的成本矩阵，第i行各元素表示第j个单位完成各任務所需成本，第j列各元素表示第J项任务由各单位完成所需成本[8]。这样，问题的数学模型是：

3 改进的人工蜂群算法

改进人工蜂群算法是在人工蜂群算法基本原理的基础上，在食物源编码时采用的离散型编码，同时在工作蜂和跟随蜂生成候选食物源时，为了保持食物源对应的解的可行性提出了一种邻域移动方法。

3.1 蜜源位置编码

根据问题离散型进行编码，设一个n维问题，任一食物源的位置xi，是一个n维向量，向量的维数对应任务数。食物源的位置编码为xi=（xi1，xi2，...，xij，...，xin），它代表一种任务指派的方案，每一个xi是1～n自然数的一个排列。其中，xij表示第i个解的第j项任务由xij去完成。

3.2 候选蜜源的生成

本文蜜源的位置xi是离散的表达形式，采用邻域移动方法来生成候选蜜源。如图1所示，蜜源i是当前食物源，蜜源k是随机选取的相邻蜜源，它们移动前编码如图1（a）。随机选择的位置d，这里是第二位，箭头①指向食物源k的第二位“1”箭头②指向蜜源：的第二位“5”，邻域移动的过程为：食物源的第二位“5”被蜜源k的第二位，“1”替换，然后再寻找原蜜源中“1”的位置，这里是第五位，箭头③表示蜜源第五位的“1”为“5”所替换，流程如箭头①②③的流向所示。

4 算例分析

根据表2航班数据，确定延误损失矩阵：

分别采用传统人工蜂群算法和改进人工蜂群算法进行20次仿真，其最优解为5-4、4-7、7-11、9-9，造成的经济损失是29070元，全局最优解的收敛过程如图2、图3所示。

5 结束语

本文针对机场出现较大规模延误后，为使得经济损失最低进行调度恢复，并建立航班调度数学模型。在充分考虑到调度问题离散性特点，给出了适当的蜜源编码方法，利用邻域移动法生成候选蜜源。通过算例分析，改进的人工蜂群算法具有更好的收敛性，在解决航班调度等离散指派问题时具有很强的使用价值。

参考文献：

[1]秦全德，程适，李丽，等.人工蜂群算法研究综述[J].智能系统学报，2014，9（2）：127-135.

[2]孙晓雅，林焰.改进的人工蜂群算法求解任务指派问题[J].微电子学与计算机，2012，29（1）：23-26.

[3]中国民用航空局.2015年民航行业发展统计公报[M].北京：中国民航出版社，2015.

[4]朱志禹.论航空公司运营中的服务接触及关键事件管理[J].西南交通大学学报（社会科学版），2008，10：17-21.

[5]李雄，刘光才，颜明池.航班延误引发的航空公司及旅客经济损失[J].系统工程，2007，12：20-23.

[6]马正平，崔德光.机场航班延误优化模型[J].清华大学学报（自然科学版），2004，44（4）：474-477.

[7]赵秀丽，朱金福，郭梅.不正常航班延误调度模型及算法[J].系统工程理论与实践，2008，4：129-134.

[8]董钰.大规模航班延误恢复调度模型及管理研究[D].大連海事大学，2009.