A Dynamic Model for Airline Fleeting and Scheduling

Abstract

COVID-19 has reshaped the global airline industry. Travel demands are volatile, and passengers have more flexibility in bookings and cancellations. More than ever, airlines have to be agile and adaptive while making operational decisions. We introduce a dynamic model to help airlines make adaptive fleeting and scheduling decisions based on stochastically evolving bookings and contextual signals. The model incorporates both arrivals (new bookings) and departures (cancellations), and the contextual information affecting future demand. This significantly generalizes and strengthens previous modeling attempts. We develop a Lagrangian relaxation framework that decomposes the dynamic program defined on a large time-space network into separable flight-level problems. Owing to the complexities of this network, our Lagrangian dual problem is not straightforward to solve. We therefore develop a tailored and simple projected subgradient algorithm that exploits the structure of this network for efficient solutions. We establish the correctness and convergence properties of this procedure. Our analysis yields new theoretical, algorithmic, and managerial insights into the dynamic fleeting and scheduling problem. We present computational experiments based on real-world airline data to demonstrate the potential benefits of this approach.