691 / 2024-05-10 22:49:00

Aircraft Recovery with Pre-cancellation

Column generation,Aircraft Recovery,Lagrangian dual decomposition

Airlines often adopt a wait-and-see attitude to disruptions, resulting in cancelling flight at the last moment. This not only incur extra compensation costs but also significantly affects passengers’ travel experiences. To mitigate these losses, we introduce the concept of flight pre-cancellation, defined as canceling flights one to several days before departure. To make pre-cancellation decisions with regards to the stochastic weather condition, we develop a two-stage stochastic model aimed at minimizing the overall recovery cost. To solve this model, we design a Lagrangian Dual Decomposition (LDD) algorithm, which efficiently decomposes the model into scenario-independent sub-models. These sub-models are then solved by column generation framework. Additionally, we propose a dual-based variable selection strategy (DVS) to accelerate the solving process of LDD, based on the dual information obtained from the model with perfect information. We evaluate the effectiveness and efficiency of our model and algorithms through simulated scenarios based on real operational data from three airlines. The computational results demonstrate that compared to solving by column generation alone, the solution time of LDD and DVS is reduced by 31.02% and 34.32%, respectively. Furthermore, incorporating pre-cancellation decisions leads to an average profit gain of 3.04% compared to solutions that do not consider pre-cancellation.