论文部分内容阅读
机组排班是航空公司运营计划中的重要组成部分。利用运筹学方法优化机组排班过程,可以提高计划的科学性,降低机组费用,对提高航空公司运营效率、保证飞行安全都具有重要意义。然而,机组排班问题约束繁多,模型结构复杂,是典型的NP难问题。因此,研究可以快速求解复杂机组排班问题的模型与算法对工业界和学术界都有重要意义。机组排班问题本质上是机组和航班的匹配问题,以往机组排班计划的制定大都依靠手工方式完成,随着航空业的快速发展,航空公司规模迅速扩大,传统排班方法已很难满足航空公司的运营需求,能够求解大规模机组排班问题的智能优化系统将为航空公司提供更好的决策支持。本文首先分析了机组排班问题的研究进展,在此基础上,基于数学规划方法,构建了单基地的机组排班优化模型。该模型以最小化排班总成本为优化目标,并加入了对双机场和搭机的考虑,使模型更加贴近实际。基于对模型特点的分析,本文设计了可求解大规模机组排班问题的启发式列生成算法,并通过数值实验对算法的有效性进行了验证。以往对机组排班问题的研究大多不考虑航班延误,造成排班方案抗干扰性较差。为提升排班的鲁棒性,本文在深入分析航班延误产生和传导过程的基础上,构建了考虑延误的机组排班扩展模型。与传统确定性模型不同,该模型在生成新任务环时,同步计算航班延误沿路径的传导,可精确模拟延误的传导过程。加入对航班延误的考虑后,模型的复杂度进一步提升,求解更加困难,因此,本文设计了带有航班延误的启发式求解算法,实现了模型的有效求解。最后,本文通过仿真实验对传统确定性模型和考虑延误的扩展模型进行对比,证明扩展模型可显著减少因延误导致的航班取消,提升排班方案的抗干扰能力。在完成上述工作后,本文首次基于混合集合规划方法对机组排班问题进行了研究,构建了机组排班问题的混合集合规划模型,并将运筹学算法与问题业务逻辑相结合,设计了高效的求解策略。数值实验证明,该模型可求解达到实际应用规模的机组排班优化问题。之后,本文从多方面对机组排班问题的数学规划模型和混合集合规划模型进行了对比研究,并根据各模型特点对模型在实际中的应用给出了相应建议。