无初始解的大规模机组排班问题建模与求解优化

发布时间：2017-09-21 23:38

  本文关键词：无初始解的大规模机组排班问题建模与求解优化

  更多相关文章： 大规模 飞行员排班 列生成算法 日任务

【摘要】：航空任务排班是航空企业运营管理的重要部分，直接决定了企业的管理水平高低。飞行员排班是航空任务排班中的重要组成部分，好的飞行员排班计划能够合理的应用企业资源，降低成本，使飞行员这一重要人力资源得到高效率使用。探索不同的求解优化方法对获得更快的求解速度、更高的求解质量有重要意义。 本文对大规模的飞行员排班任务复杂性进行了分析，对无初始解情况的求解方法进行了设计与优化。首先对问题的输入输出信息与约束条件进行了阐述，并将其建模为集合分割问题。进而对求解特殊矩阵的列生成算法进行了详尽的剖析，展示了算法原理，给出了列生成法获得的松弛问题解的最优性证明。本文用罚函数法解决了无初始解的情况，探索出高质量的初始列并用启发式搜索输入给列生成法，实现了对算法求解质量的优化，并对子问题设计了加快收敛的列生成策略。针对求解松弛问题的数学规划方法，根据多种方法收敛特性，找到一种综合使用牛顿障碍法与对偶单纯形法的最优求解组合方法。随后设计了基于日任务的求解架构，对问题进行了新的建模，应用启发式搜索法与罚因子法构造初始可行解，子问题转化为两个含有负权与时间约束的最短路问题。通过大量计算实验探索了这种方法的求解性能，找到了平衡计算资源的方法。随后应用D-W分解对基于日任务的方法进行了变换，尝试对求解方法进行优化设计，对问题的求解进行了拆解后，研究了在大量可行日任务的基础上如何更好获得最优排班解的方法。通过添加机场节点流约束能够使日任务集合被排班覆盖，实现了优化。在计算实验中本文使用了来自国内一家航空公司的一周运营的实际数据，航班多达1190架次，并且没有已知的可行解。分析中通过调节计算参数对以上不同求解方法的各类性质进行了对比分析，最终的计算结果证实这种求解方法在一定意义上具有可行性，，其求解速度、质量均在可接受的范围内。最后给出了这种求解方法中存在的不足以及可能的改进方向。
【关键词】：大规模 飞行员排班 列生成算法 日任务
【学位授予单位】：清华大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：F561
【目录】：

• 摘要3-4
• Abstract4-7
• 第1章 绪论7-14
• 1.1 选题背景7-8
• 1.2 文献综述8-12
• 1.3 研究内容与研究方法12-13
• 1.3.1 研究内容12-13
• 1.3.2 研究方法13
• 1.4 求解的软、硬件环境13-14
• 第2章 排班问题及其模型分析14-25
• 2.1 问题分析14-16
• 2.1.1 飞行员排班问题的任务14-16
• 2.1.2 飞行员排班问题的复杂性16
• 2.2 优化目标与成本结构16-17
• 2.3 CPP求解约束条件17
• 2.4 CPP求解的数学模型与网络图模型17-20
• 2.5 列生成算法20-23
• 2.5.1 算法优点20
• 2.5.2 算法思想与原理20-22
• 2.5.3 列生成算法松弛解的最优性证明22
• 2.5.4 列生成算法的求解质量的一些实验观测22-23
• 2.6 最短路子问题（ColumnGenerator：PricingProblem）23-25
• 第3章 无初始解排班问题的算法设计与优化25-39
• 3.1 无初始解大规模飞行员排班问题的建模25-27
• 3.1.1 求解机组排班问题的列生成算法流程25-26
• 3.1.2 求解策略26
• 3.1.3 基于罚因子法的数学模型26-27
• 3.2 子问题建模及其生成策略27-30
• 3.2.1 子问题有向图建模27-29
• 3.2.2 带有负权与时间约束的最短路问题29-30
• 3.3 提高求解质量与求解速度的优化设计30-39
• 3.3.1 无初始输入列的求解30-31
• 3.3.2 探索提高求解质量的初始列31-35
• 3.3.3 一种新的求解松弛主问题的优化方法35-38
• 3.3.4 优化方法的相关结论38-39
• 第4章 基于duty-period的无初始解求解方法设计39-50
• 4.1 基于罚因子法的主问题数学模型39-41
• 4.2 两个最短路子问题与其迭代逻辑41-45
• 4.2.1 Duty生成原理41-42
• 4.2.2 排班路线（pairing）生成原理42-45
• 4.3 求解策略45-47
• 4.3.1 协调两个生成子问题的方法45
• 4.3.2 探索提高求解质量的初始列与行45-47
• 4.4 计算结果与计算性能分析47-50
• 第5章 基于duty-period求解方法的优化50-56
• 5.1 基于duty-period方法的矩阵分解50-51
• 5.2 一种Best-Duty-Set求解方法51-54
• 5.3 Pairing列生成问题54
• 5.4 计算结果与分析54-56
• 第6章 总结与展望56-58
• 6.1 研究主要成果56
• 6.2 研究主要不足56-57
• 6.3 研究展望57-58
• 参考文献58-61
• 致谢61-63
• 个人简历63

【共引文献】

中国期刊全文数据库 前3条

1 方磊,何建敏;城市应急系统优化选址决策模型和算法[J];管理科学学报;2005年01期

2 石俊刚;史宏杰;徐瑞华;;城市轨道交通乘务任务划分模型及算法研究[J];铁道学报;2014年05期

3 石俊刚;周峰;徐瑞华;;城轨交通乘务任务配对的集合分割模型及算法[J];同济大学学报(自然科学版);2015年02期

中国博士学位论文全文数据库 前2条

1 杨阳;钢铁企业轧线批调度问题的建模与最优化方法的研究[D];东北大学;2010年

2 狄浩;虚拟网络的高效和可靠映射算法研究[D];电子科技大学;2013年

中国硕士学位论文全文数据库 前6条

1 王宏建;分院飞行训练排班系统研究[D];电子科技大学;2010年

2 鲁红珍;航空公司机组航班任务串优化方法研究[D];中国民用航空飞行学院;2012年

3 张硕;航空公司飞行机组指派问题研究[D];中国民用航空飞行学院;2013年

4 陈海平;高速铁路乘务组织理论与优化研究[D];北京交通大学;2013年

5 张余;随机能力提升下知识型员工调度问题研究[D];西安电子科技大学;2012年

6 董雪遥;深圳航空机组管理系统的设计与实现[D];哈尔滨工业大学;2014年

本文编号：897556