林楠通 王泳欣 吴国涛 赖建蓉 叶雪琪

摘 要：文章构建了以延误成本最小或延误时间最短为目标函数的航班恢复模型，航空公司可以根据需要选择不同的目标函数；细分了延误成本，并且对匈牙利算法进行改进，加入了遗传算法对模型进行求解，给出了算法的运行步骤，并以实例说明了模型和算法的可行性。

关键词：匈牙利算法；延误成本；延误时间

中图分类号：F562

文献标识码：A

在对航班延误进行调度时，航空公司总是把所有处于延误之后的备用飞机或者是已经完成飞行任务的飞机都作为调度对象，将这些飞机重新指派给航班。在本文中，我们以航班延误时间最短或延误成本最低作为主要目标，得出的两种最优解是相对的，其中以延误成本最低为目标得出的方案延误时间不是最短，因此得出来的方案需要由运控人员根据现实情况选择。

在本文中，我们针对航空公司的需要，按原计划出发时间对延误的航班进行排序，改进匈牙利算法，求出飞机调整的最优解。

一、延误成本的定义

在航班延误发生之时，旅客和航空公司无疑是航班延误的受害者，因此延误成本在定义时需要分开计算。

1.航空公司的经济损失

经过查询文献，我们可以发现航空公司的经济损失分为延误航班的运营成本、取消航班的盈利损失和调运飞机成本。

其中延误航班的运营成本和航班机型以及质量有关系，对于不同的机型，其延误成本为：C_fd=at，其中，a为飞机每小时延误的运营成本。延误航班的盈利损失与航班航班客座率s、航空公司的平均票价a和最大载客人数m密切相关。则延误航班的经济损失：C_f=msa。而调运飞机成本由航油价格和两机场之间的距离决定。

2.乘客的经济损失

查询文献可得航班延误造成的乘客损失为：C_m=α_psmt。其中α_p为航班单位时间每名旅客的平均延误经济损失，t由航班计划起飞时刻T和航班恢复时间R决定。

二、延误航班调度问题的数学模型建立

由于飛机指派问题的约束条件很多，还有一部分是柔性约束，决策人员不希望算法仅能给出一个解，而是希望得到多个备选方案，由签派人员决定最终执行方案。

根据上述对航班延误经济损失的理解，查询文献可得针对航班延误经济损失降到最低的目标函数为：

三、模型的求解

我们根据上述模型，采用某航空公司航班的基本数据，利用经典的匈牙利指派步骤，对航班延误恢复调度模型进行了拟合，用MATLAB分别得出两个目标函数下的求解结果，其中以延误时间最小化为目标函数的延误成本为86710元，以延误成本最小化为目标函数的延误成本为69171元。

以上两种方案的成本差是17539元，这里也证明了匈牙利算法在不同目标情况下得到的解并非最优，航空公司可以根据自身的需要选择相应的目标函数，在实际发生的航班延误基础上，得出相应的优化解决方案。

由于遗传算法能寻找到一种合适的解，因此在求解上述模型时，为了提高求解的效率和直观地得出解决方案，本文在经典的匈牙利算法上加入了遗传算法，得到以下的算法步骤：

步骤2：处理约束条件；

步骤3：判断飞机数和航班数是否平衡，并进行匈牙利指派，平衡输出最优指派序列；非平衡输出最优指派序列和取消航班序列；

步骤4：设置W=x₁，x₂，...，x_n对最优指派序列进行编码；

步骤5：遗传算法的初始输入为随机交换某邻域编码的次序；

步骤6：首先轮盘赌方法进行选择操作，接着使用均匀交叉方法进行交叉操作，最后使用随机扰动法进行变异操作；

步骤7：复杂性分析，检验分析混合优化算法的复杂度不超过经典匈牙利算法的时间复杂度。

构建以上遗传算法与匈牙利算法的混合优化算法后，我们需通过实例进行验证。本文我们选取了某航空公司在某一天的航班延误调度，初始飞机编号为1～10号，进行匈牙利指派后，飞机的编码顺序为2，3，1，5，7，9，10，4，8，6；接着我们按照上述的算法步骤，随机交换初始飞机编号邻域编码的次序，即以2，1，3，5，7，9，10，4，8，6作为遗传算法的初始输入，最终得到的染色体编码依旧为2，3，1，5，7，9，10，4，8，6。我们可以得出该算法收敛于匈牙利算法的指派。

四、结语

在本文中，我们对经典的匈牙利算法进行了改进，由于篇幅受限，经典的匈牙利算法的步骤并未给出，但数据真实可靠；但在调度的过程中当我们随机交换初始飞机编号次序时仍然能够输出指派结果。因此，我们采取了遗传算法和匈牙利算法进行混合优化，得出的调度模型会更加高效。

参考文献：

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

[2]赵秀丽.航空公司不正常航班恢复模型及算法研究[D].南京：南京航空航天大学，2010.

[3]杨秀云，王全良，何建宝.航班延误问题的研究动态、演化趋势及启示[J].经济经纬，2013（4）.

[4]邢有洪，李晓津.航空公司航班延误损失分析[J].会计之友（中旬刊），2010（2）.

[5]吕宗平，胡 欣，丁建立.航班延误预警指标体系与预警量级构建[J].航空计算技术，2010（1）.

[6]荣 耀，王建东.基于关键飞行资源的航班延误波及DAG模型的研究[J].小型微型计算机系统，2009（11）.

[7]吕晓杰，王 红.大型枢纽机场大面积航班延误预警方法研究[J].计算机工程与设计，2009（19）.

[8]刘艳红，高 林，李耀华.基于经济损失的航班延误恢复模型研究[J].中国民航大学学报，2011（1）.