飞机排班问题模型及算法研究

摘要

飞机排班问题一直是航空公司日常运营工作的重要组成部分，也是航空调度领域中的研究热点。随着航空交通运输的日益发展，航空公司的业务量不断增大，航班网络的复杂性也逐渐增加，飞机排班问题依然存在具有挑战性的研究点。一个快速、智能、合理的飞机排班计划，不但能够节省人力、物力、财力，减少航空公司的运营代价，而且能够进一步提高航空公司的市场竞争力。
　　针对飞机排班问题，本文基于流网络的思想建立了航班衔接网络图，并在此基础上做了如下工作:
　　第一，提出了两个飞机排班模型，第一个是基于最少使用飞机和最小剩余飞行时间的飞机排班模型。该模型能够在为飞机安排航班执行任务的同时为飞机安排维修定检任务，目标函数是最小化飞机的使用数量和最小化飞机的累积剩余飞行时间。然后，考虑到第一个飞机排班模型的排班方案没有考虑鲁棒性因素，为了构建一个鲁棒性的飞机调度计划，提出了第二个基于航班延误概率的鲁棒性飞机排班模型。这里的鲁棒性是指飞机排班方案本身具有一定的抗干扰能力。在日常的飞机调度中，较小的干扰可能会导致调度计划较大的改变。本文通过调整接续航班之间的衔接时间，为飞机调度计划增加了部分缓冲时间，来提高飞机排班方案的抗干扰能力。
　　第二，提出了基于图约减和强化约束的模型优化算法和基于变邻域搜索的求解算法。在飞机排班模型的求解过程中，首先运用基于图约减和强化约束的模型优化算法对模型进行约减，提高模型的可求解性。然后，提出了一种基于变邻域搜索的求解算法对模型进行求解。该算法通过迭代的方式求解原模型的子模型的最优解，达到优化原模型的目标函数的目的。
　　为了验证算法的有效性，本文利用某航空公司提供的真实的航班和飞机信息数据在两个飞机排班模型上进行了实验，并与商业求解器CPLEX对比。实验结果表明，提出的基于变邻域搜索的求解算法，在解的质量和求解时间上，均优于CPLEX，尤其是在大规模的测试用例上，基于变邻域搜索的求解算法的性能更好，求解时间更稳定。

目录

声明

致谢

摘要

1 引言

1．1 研究背景

1．2 研究现状

1．3 研究目的及意义

1．4 主要研究内容

1．5 论文组织结构

2 相关约束及理论技术

2．1 约束条件

2．2 流网络模型

2．2．1 流网络定义

2．2．2 流网络在飞机排班上的应用

2．3 CPLEX相关介绍

2．4 本章小结

3 基于最少使用飞机和最小剩余飞行时间的飞机排班模型

3．1 航班衔接网络

3．2 模型构建

3．3 飞机排班优化算法

3．3．1 基于图约减和强化约束的模型优化算法

3．3．2 基于变邻域搜索的求解算法

3．4 实验结果

3．4．1 实验数据

3．4．2 实验环境

3．4．3 实验结果分析

3．5 本章小结

4 基于延误概率的鲁棒性飞机排班模型

4．1 背景介绍

4．2 模型构建

4．3 实验结果

4．3．1 实验数据及环境

4．3．2 实验结果

4．4 本章小结

5 总结与展望

5．1 总结

5．2 展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集