摘 要: | 主要根据2017年中国研究生数学建模竞赛中的航班恢复问题,探讨航班遇到突发情况时,如:机场在某时间段关闭,如何按照不同要求重新规划航班,使得旅客总延误时间或航班总延误时间尽可能短.航班恢复是一个NP-Hard问题,根据竞赛所涉航班恢复的4个子问题,分别根据其特有的约束条件和飞机间调整所需额外成本的计算办法,建立了相应的混合整数规划模型.通过先检测不正常航班的相关信息如延误扩散情况,再选择航班恢复计划使延误尽可能小,给出了启发式算法求解上述规划模型.进一步,对航班恢复问题所涉及的前3个子问题,分析了其延误时间下界,并与算法所得的延误时间进行比较,发现算法所得延误时间等于或者非常接近估计下界,这说明算法所得新航班计划是最优的或者非常接近最优航班恢复计划.
|