A Reinforcement Learning Approach for Initialization of Column Generation with Application to Aircraft Recovery Problem

Column Generation is a crucial technique for addressing large-scale combinatorial problems, particularly in logistics and transportation scenarios like the aircraft recovery problem. Yet, the initialization of columns within this framework remains an unexplored topic that significantly affects the efficiency of the solving process.

In this study, we propose a novel reinforcement learning approach to design initial columns for the aircraft recovery problem. This approach is conceptualized as a decision-making process led by an agent, leveraging a Graph Attention Network combined with Proximal Policy Optimization (PPO) to identify routes that minimize reduced costs within the aircraft’s flight connection network.

Preliminary computational results validate the effectiveness of our RL approach, demonstrating its capacity to enhance the overall speed of the column generation process. Notably, the trained policy exhibits robust generalization across different networks, rapidly producing high

Recommended citation: J. Lu and X. Qian, 'A Reinforcement Learning Approach for Initialization of Column Generation with Application to Aircraft Recovery Problem,' in LESCDT 2024.
Download Paper