利用强化学习改进列生成算法快速求解大规模不正常航班恢复问题

不正常航班恢复问题是一类难以求解的大规模组合优化问题。在出现恶劣天气、飞机故障、流量控制等突发情况下，航空公司需要快速决策调整航班计划，减少因航班延误和取消造成的社会经济损失。现有的研究大多集中于单一的运筹优化算法，对于大规模问题，计算时间仍显过长尚不能适应动态变化的航班运行环境，且在数学模型中难以同时考虑关键业务要素。对此，本项目拟从算法角度在三个层面进一步提高求解效率，缩短计算时间至分钟级并获得最优误差小于10%的高质量解：①针对航空公司的现实需求，构建完整刻画问题核心特点与关键矛盾的数学模型。②使用混合启发式的列生成算法及增强策略，在保证列生成算法收敛性和最优性的前提下提升算法的迭代效率；③利用数据驱动的强化学习对列生成算法建模、分析与优化，根据算例自适应指导列生成算法的寻优机制。本项目不仅有助于解决现实中我国民航业的运营痛点问题，也为学习型优化算法的研究提供必要科学依据。

Aircraft recovery problem is one of the NP-hard combinatorial optimization problems which are difficult to solve. When disruptions such as bad weather, mechanical failure, or traffic flow control happen, airlines need to modify its original flight plan to reduce the social and economic costs due to flight delays and cancellations. Previous researches mainly focus on optimization algorithms and it is difficult to consider critical business factors simultaneously in the mathematical model. For large scale problems the computational time is still too long given the ever-changing environment in which the airlines operate. To further enhance the computational efficiency and reduce the computational time to several minutes with optimality gap less than 10%, this research proposes to tackle the problem in three aspects. First, the mathematical model will be built to capture the core characteristics and critical conflicts within the problem according to the real needs of airlines. Second, heuristics and other improving techniques are to be embedded in the column generation process to enhance its iteration efficiency. The column generation process is still ensured to converge to the optimal. Third, reinforcement learning will be utilized to model, analyze, and optimize the column generation process, so the algorithm is adaptive to specific problem instances. This research is not only aiming to solve the critical operation problem faced by the civil aviation industry of the country, but also providing scientific guidance for the research on developing optimization methods with learning ability.