A Benders and Column Generation Method to Integrated Aircraft and Passenger Recovery with Cruise Speed Control Under Slot Capacity Restriction

Disruptions are common and inevitable in the airline industry. Since aircraft rerouting and passenger reallocation directly affect the whole recovery performance, they attract great attention in airline disruption management. In this paper, we consider the integrated aircraft and passenger recovery (IAPR) so as to preserve the interdependence between aircraft rerouting and passenger reallocation. To improve the performance of recovery plans, cruise speed control is also applied as a recovery option. However, few studies consider slot capacity restriction when controlling cruise speeds, although this restriction is quite critical in airline operations. To fill this gap, we propose a mathematical model to describe the IAPR with cruise speed control under slot capacity restriction. Then, we reformulate it as a conic quadratic mixed integer programming (CQMIP) problem by rewriting the nonlinear fuel burn function, nonlinear constraints, and logical constraints. To solve the CQMIP problem efficiently while keeping the solution quality, we develop a Benders and column generation (BCG) method by exploiting the structure of the integrated model. Computational experiments show the necessity of considering slot capacity restriction and the benefit of controlling cruise speeds. Furthermore, a high-quality solution can be obtained by the BCG method within a reasonable runtime.