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