基于混合模拟退火算法的航空公司勤务编排算法研究

论文摘要

本文以航班优化及航线经济效益分析系统(FORMAX)为应用背景,对机组排班中的勤务编排问题进行研究,通过优化勤务编排的算法得到正确、合理、高效的勤务。本文将勤务编排分成可行勤务的产生和勤务优化两个子问题进行研究。在分析了勤务编排规则的基础上,给出了分层次的勤务编排模型及各项优化指标。并为了得到最佳优化效果,综合平衡了各项目标函数的权重;然后总结分析了启发式算法和最优解算法的适用性,明确了启发式算法在解决大规模数据量问题时的优势。同时通过对遗传算法和模拟退火算法的仿真比较实验,论证了模拟退火算法较遗传算法具有更高的局部搜索能力;在算法设计阶段,将深度优先算法应用于可行勤务产生的过程中。本文重点研究勤务优化问题,在候选勤务集合中进行初步筛选得到初始勤务,并在初始解的基础上,分析模拟退火算法在解的邻域内寻找最优可行勤务的过程。针对模拟退火算法随机筛选过程中的不足,引入了一种启发式操作,保证了最优解的可行性。最后通过对算法的初步筛选效能、敏感度、时间复杂度、优化效果等角度的比较分析,验证了模拟退火算法产生勤务的高效性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景及目的
• 1.1.1 研究背景
• 1.1.2 研究目的
• 1.2 国内外研究现状
• 1.3 研究内容及章节安排
• 第二章 勤务编排问题的建模
• 2.1 勤务编排问题描述
• 2.2 勤务编排规则
• 2.3 勤务编排模型
• 2.3.1 基本模型
• 2.3.2 勤务产生模型
• 2.3.3 勤务优化模型
• 2.4 本章小节
• 第三章 模拟退火算法
• 3.1 模拟退火算法演算机制
• 3.2 模拟退火算法的局限性与改进
• 3.2.1 模拟退火算法的收敛性分析
• 3.2.2 模拟退火算法的局限性
• 3.2.3 模拟退火算法的改进
• 3.3 遗传算法基本原理
• 3.4 算法效果比较
• 3.5 本章小节
• 第四章 混合模拟退火算法设计
• 4.1 候选勤务的产生
• 4.2 勤务初步筛选
• 4.3 勤务最优解筛选
• 4.3.2 模拟退火算法设计
• 4.3.3 启发式操作
• 4.4 实证分析
• 4.4.1 初步筛选效能分析
• 4.4.2 敏感度分析
• 4.4.3 时间复杂度分析
• 4.4.4 优化效果的分析
• 第五章 总结与展望
• 参考文献
• 致谢
• 在学期间的研究成果及发表的学术论文