考虑缓冲时间的受扰航班恢复问题建模与求解

Modeling and Solution for Disturbed Flights Recovery Problem with Buffer Time

在制定受扰航班恢复计划时,为航班设置缓冲时间,可有效减少航班实际执行时的延误传播。研究考虑缓冲时间的受扰航班恢复问题,以恢复成本最小化为目标建立混合整数规划模型和集合划分模型。采用改进分支定价算法求解,并应用两种加速策略加快算法的求解。小规模算例的求解与CPLEX优化软件进行对比,验证了模型和算法的有效性,大规模算例实验表明了改进分支定价算法的高效性。使用加速策略使得算法的平均求解时间由937.63 s降到185.22 s,平均效率提高80.25%。

Setting a buffer time can effectively reduce the delay propagation when making a recovery plan for disturbed flights.This paper studies the disturbed flight recovery problem with buffer time.To achieve the objective of minimizing the total recovery cost,this paper introduces a mixed integer programming model,and a set-partitioning model is proposed.The problem is tackled using an enhanced branch-and-price algorithm incorporating two acceleration strategies to improve efficiency and solution quality.The CPLEX is used to compare with the algorithm in small-scale experiments to verify the model's and the algorithm's effectiveness.The large-scale experiments show the efficiency of the algorithm.The comparison experiment of the acceleration strategy shows a remarkable effect:the average solution time is reduced from 937.63 s to 185.22 s,and the average efficiency is increased by 80.25%.