不正常航班恢复模型和算法研究  

Research on Modeling and Algorithm for Irregular Flight Recovery

作　　者：张静[1] 徐明华[1] 曹伟建[1] 江楠 ZHANG Jing;XU Ming-hua;CAO Wei-jian;JIANG Nan(School of Information and Mathematical Sciences,Changzhou University,Changzhou 213164,China)

机构地区：[1]常州大学信息数理学院

出　　处：《数学的实践与认识》2018年第15期145-152,共8页Mathematics in Practice and Theory

基　　金：江苏省教育科学“十二五”规划课题(D/2015/01/35);常州大学院级教育数学研究课题(2017XSJY03)

摘　　要：主要根据2017年中国研究生数学建模竞赛中的航班恢复问题，探讨航班遇到突发情况时，如：机场在某时间段关闭，如何按照不同要求重新规划航班，使得旅客总延误时间或航班总延误时间尽可能短．航班恢复是一个NP—Hard问题，根据竞赛所涉航班恢复的4个子问题，分别根据其特有的约束条件和飞机间调整所需额外成本的计算办法，建立了相应的混合整数规划模型．通过先检测不正常航班的相关信息如延误扩散情况，再选择航班恢复计划使延误尽可能小，给出了启发式算法求解上述规划模型．进一步，对航班恢复问题所涉及的前3个子问题，分析了其延误时间下界，并与算法所得的延误时间进行比较，发现算法所得延误时间等于或者非常接近估计下界，这说明算法所得新航班计划是最优的或者非常接近最优航班恢复计划．Based on the problem of irregular flight recovery in 2017 China Postgraduate Mathematical Contest in Modeling, how to rearrange flights and minimize the total delay time of passengers or flights for different cases is discussed in this paper when an airport is temporarily closed. The irregular flight recovery is an NP-Hard problem. Focusing on each of the 4 sub-problems of the irregular flight recovery problem considered in this paper, a mixed integer programming model is established according to its specific constraints and extra cost needed for aircrafts adjustments. Heuristic algorithm is proposed for each model based on the technique of analyzing the information, such as the diffusion of the delay time, of the irregular flights, and then selecting the new flight plan by making the total delay time as small as possible. Furthermore, the lower bound of the delay time of the first three sub-problems is estimated. After comparing it with the delay time obtained by the algorithm, it is found that they are equal or almost equal, which indicating that the new flight plan obtained by the algorithm is the best or very close to the optimal flight recovery plan.

关 键 词：航班恢复 混合整数规划 启发式算法 

分 类 号：V35[航空宇航科学与技术—人机与环境工程]