论文部分内容阅读
飞机路径恢复是航班调整中保证航班能够运行的必要条件之一，而传统目标下的飞机路径优化问题是NP—hard的。本文针对单架飞机受到干扰后，基于最小最大目标的同机型飞机路径最优化问题，给出了一个新的多项式时间算法。首先基于航空公司调整航班的常用原则，提出把最大航班延误时间最小化作为问题的目标。然后根据问题的一些特点和目标形式，设计出解构造算法，得到飞机路径恢复问题的最优解，并分析出算法的复杂度为O（n3log（n））。相对于一般的最小最大二分图匹配算法（复杂度为O（n3log（n）），该算法具有较小的时间复杂度