ADMM-based augmented Lagrangian methods for robust aircraft recovery problem considering connection time, resource capacity and maintenance flexibility

Disruptions are inevitable and can lead to great economic and reputation losses to airlines. Aircraft recovery problem (ARP), which provides aircraft recovery plans for airlines, is one of the most important problems in airline disruption management. This paper develops a robust aircraft recovery model (RARM) with considering slot resource, airport capacity and maintenance flexibility. To increase the robustness of recovery plans, we reduce the number of critical and loose connections. When the number of flights involved is large, there are too many variables and constraints in the RARM, making it difficult to solve. Then we propose alternating direction methods of multipliers (ADMM) combined with column generation method (CG) to solve RARM. Specifically, some complex constraints are relaxed by augmented Lagrangian method (ALM) and the relaxed problem is decomposed into multiple subproblems under the ADMM framework. Since the ADMM subproblems are nonlinear integer programs, we utilize the binary variable property and linearization technique to linearize them so that their computational difficulty is mitigated. We prove that the best extreme points of their linear relaxations are optimal to the subproblems, and then CG is used to solve the equivalent linear relaxations of subproblems. In our numerical experiments, the proposed model and algorithms are tested on real-world data. Computational results show that our methods can find robust aircraft recovery plans in reasonable time. For all instances, the total delay time caused by a new disruption is decreased with a maximum reduction of 37.46%. Besides, through comparisons with the commercial solver CPLEX, the large neighborhood search (LNS), and a state-of-the-art proactive recovery approach, we demonstrate the superior performance of our model and algorithms, especially for large-scale instances.