单架飞机受干扰后飞机路径恢复多项式算法研究  

Polynomial-time Algorithms for Aircraft Rerouting under the Disruption of a Single Aircraft

作　　者：胡玉真 宋艳[1] 许保光[2] 

机构地区：[1]哈尔滨工程大学经济管理学院,黑龙江哈尔滨150001 [2]中国科学院科技政策与管理科学研究所,北京100190

出　　处：《运筹与管理》2017年第8期11-18,共8页Operations Research and Management Science

基　　金：中国博士后资助项目(2016M590276);黑龙江省博士后基金项目(LBH-Z15047);黑龙江省自然科学基金项目(QC2016095);黑龙江省应用技术研究与开发计划软科学项目(GC16D104);中央高校基本科研业务费基金项目(HEUCFW170903;HEUCF170906)

摘　　要：飞机路径恢复是航班调整中保证航班能够运行的必要条件之一,而传统目标下的飞机路径优化问题是NPhard的。本文针对单架飞机受到干扰后,基于最小最大目标的同机型飞机路径最优化问题,给出了一个新的多项式时间算法。首先基于航空公司调整航班的常用原则,提出把最大航班延误时间最小化作为问题的目标。然后根据问题的一些特点和目标形式,设计出解构造算法,得到飞机路径恢复问题的最优解,并分析出算法的复杂度为O(n^2)。相对于一般的最小最大二分图匹配算法(复杂度为O(n^3log(n))),该算法具有较小的时间复杂度。最后用实例验证了解构造算法的有效性。该研究结果将为航空公司减少航班延误提供理论和方法支持。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 （ n2） . The new algo- rithm has ess time complexity than general rain-max bipartite graph matching algorithms, time complexity of which is O（n3log（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.

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

分 类 号：O224[理学—运筹学与控制论]