基于改进匈牙利算法的航班延误调度模型

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

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

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

中图分类号：F562

文献标识码：A

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

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

一、延误成本的定义

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

1.航空公司的经济损失

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

其中延误航班的运营成本和航班机型以及质量有关系，对于不同的机型，其延误成本为：C_fd=at，其中，a为飞机每小时延误的运营成本。……