论文部分内容阅读
本文研究了航空调度中机场任务指派问题和受扰航班恢复问题。其中,机场任务指派问题是指将具有特殊属性的任务指派给有限数量的班次,而任务的完成会产生相应的效益。由于机场任务和班次属性的多样性,约束条件的特殊性,使得此问题是一个复杂的组合优化问题,属于NP-Hard问题。而受扰航班恢复问题是指由于恶劣天气、飞机故障、机场关闭等外界条件的不确定性常常造成部分航班延误甚至取消,出现原航班计划不可行的情况,这就需要运营中心对原航班计划进行重新排列恢复飞机航线。受扰航班恢复问题属于大规模的整数规划问题,有实时性要求,其变量和约束条件复杂,目前能够满足航空公司实践需要的研究成果很少。基于以上问题的复杂性,本文分别从问题特性、模型建立、算法求解的角度进行深入研究。本文研究成果呈现如下:(1)基于问题的特征以产生效益最大化为目标,满足任务与班次之间各种约束建立了整数规划模型。并用CPLEX优化软件对此模型进行求解。基于Dantzig-Wolfe分解原理把原问题分解为集合分割模型的主问题和求最短路的子问题。采用分支定价算法(列生成算法和分支定界算法的结合)对分解后的问题精确求解。另外,为了加速列生成算法中子问题的求解速度,提出了先用启发式算法对子问题求解,获得一些高质量的列将其加入到主问题中,当启发式算法求解失败时,再采用Label Setting Algorithm对子问题精确求解并根据最优性判别定理判断当前解是否为最优解。在实验部分,结合实际数据对本文建立的模型和提出的算法进行验证分析;同时对影响目标函数值的四个因素:任务数量、班次数量、任务属性和班次工作时长分别进行测试,并对测试结果进行分析总结。(2)受扰航班恢复问题以恢复费用最小化为目标函数,采用一种改进的时空网络算法,给出占优准则,有效减少航班路线的组合数量,实现在时间上和空间上对飞机航线跟踪的同时还尽量考虑多种调度策略,包括航班延误、航班取消、维修取消、飞机交换以及最终机场飞机数量不平衡等惩罚措施。在改进的时空网络算法基础上建立数学优化模型并应用CPLEX优化软件进行求解,通过测试航空公司实际算例,表明本文提出的“ITSN”(Improved Time Space Network)算法可以迅速缩减解空间,CPLEX优化软件可以在较短时间求得问题的解。(3)基于Dantzig-Wolfe分解原理,针对受扰航班恢复问题建立集合分割模型的受限制主问题(Restricted Linear Master Problem,RLMP)和最短路的子问题(Sub-Problem,SP),采用列生成算法进行求解,为了减少主问题与子问题之间的迭代次数,提高算法的求解效率,通过分析问题的特征,针对该问题的特征构造好的初始解,基于该初始解调用CPLEX优化软件对主问题进行求解,获得主问题约束条件的对偶变量,这些对偶变量作为简约成本的系数传到子问题的目标函数中。其次,子问题的目标是求解最短路,即“带有负权、有附加约束的最短路”,由于问题的复杂性,采用一般的动态规划算法求解具有一定难度,本文采用Multi-Label-Setting Algorithm求解子问题。最后通过对多种规模算例的测试验证所提出算法的正确性及效果,也验证了该算法求解此问题的良好表现及优势。