A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility

Abstract

We consider the aircraft recovery problem (ARP) with airport capacity constraints and maintenance flexibility. The problem is to re-schedule flights and re-assign aircraft in real time with minimized recovery cost for airlines after disruptions occur. In most published studies, airport capacity and flexible maintenance are not considered simultaneously via an optimization approach. To bridge this gap, we propose a column generation heuristic to solve the problem. The framework consists of a master problem for selecting routes for aircraft and subproblems for generating routes. Airport capacity is explicitly considered in the master problem and swappable planned maintenances can be incorporated in the subproblem. Instead of discrete delay models which are widely adopted in much of the existing literature, in this work flight delays are continuous and optimized accurately in the subproblems. The continuous-delay model can improve the accuracy of the optimized recovery cost by up to 37.74%. The computational study based on real-world problems shows that the master problem gives very tight linear relaxation with small, often zero, optimality gaps. Large-scale problems can be solved within 6 min and the run time can be further shortened by parallelizing subproblems on more powerful hardware. In addition, from a managerial point of view, computational experiments reveal that swapping planned maintenances may bring a considerable reduction in recovery cost by about 20% and 60%, depending on specific problem instances. Furthermore, the decreasing marginal value of airport slot quota is found by computational experiments.