作者：胡玉真; 宋艳; 许保光飞机路径恢复二分图最小最大匹配问题多项式时间算法
摘要：飞机路径恢复是航班调整中保证航班能够运行的必要条件之一，而传统目标下的飞机路径优化问题是NP—hard的。本文针对单架飞机受到干扰后，基于最小最大目标的同机型飞机路径最优化问题，给出了一个新的多项式时间算法。首先基于航空公司调整航班的常用原则，提出把最大航班延误时间最小化作为问题的目标。然后根据问题的一些特点和目标形式，设计出解构造算法，得到飞机路径恢复问题的最优解，并分析出算法的复杂度为O（n3log（n））。相对于一般的最小最大二分图匹配算法（复杂度为O（n3log（n）），该算法具有较小的时间复杂度。最后用实例验证了解构造算法的有效性。该研究结果将为航空公司减少航班延误提供理论和方法支持。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
