Abstract: Aircraft recovery is one of necessary conditions to promise normal operation of airline production during flight rescheduling. Aircraft recovery problem based on traditional objectives, however, is NP-hard. In this paper, we propose a new polynomial-time algorithm for the aircraft rerouting problem based on min-max objective after the disruption to a single aircraft in a fleet. Based on the common operation of airlines when facing the flight rescheduling problem, we define the objective of the problem as the minimization of the maximal flight delay time firstly. After analyzing several characteristics of the problem and the objective function, a solution construction algorithm is proposed to solve the problem, the time complexity of which is analyzed to be O(n²). The new algorithm has ess time complexity than general min-max bipartite graph matching algorithms, time complexity of which is O(n³log(n)). A case study also illustrates the effectiveness of the solution construction algorithm. The outcome of this research could provide theoretical and practical supports for airlines to reduce flight delays.

Key words: aircraft rerouting, bipartite graph, min-max matching problem, polynomial-time algorithm

摘要： 飞机路径恢复是航班调整中保证航班能够运行的必要条件之一,而传统目标下的飞机路径优化问题是NP-hard的。本文针对单架飞机受到干扰后,基于最小最大目标的同机型飞机路径最优化问题,给出了一个新的多项式时间算法。首先基于航空公司调整航班的常用原则,提出把最大航班延误时间最小化作为问题的目标。然后根据问题的一些特点和目标形式,设计出解构造算法,得到飞机路径恢复问题的最优解,并分析出算法的复杂度为O(n²)。相对于一般的最小最大二分图匹配算法(复杂度为O(n³log(n))),该算法具有较小的时间复杂度。最后用实例验证了解构造算法的有效性。该研究结果将为航空公司减少航班延误提供理论和方法支持。

关键词: 飞机路径恢复, 二分图, 最小最大匹配问题, 多项式时间算法