Choice-Based Airline Schedule Design and Fleet Assignment : A Decomposition Approach

We study an integrated airline schedule design and fleet assignment model for constructing schedules by simultaneously selecting from a pool of optional flights and assigning fleet types to these scheduled flights. This is a crucial tactical decision which greatly influences airline profit. As passenger demand is often substitutable among available fare products between the same origin-destination pair, we study an optimization model that integrates within it a passenger choice model for fare product selections. To tackle the formidable computational challenge of solving this large-scale network design problem, we propose a decomposition approach based on partitioning the flight network into smaller subnetworks by exploiting weak dependency in the network structure. The decomposition relies on a series of approximation analyses and a novel fare split problem to reliably measure the approximation quality introduced by the partition by optimally allocating fares of products shared by flights in different subnetworks. We present several reformulations by representing fleet assignment and schedule decisions using composite variables and formally characterize the relationship of their strengths. This gives rise to a new reformulation that is able to flexibly trade off strength and size. We conduct detailed computational experiments using two realistically sized airline instances to demonstrate the effectiveness of our approach. Under a simulated passenger booking environment with both perfect and imperfect forecasts, we show that the fleeting and scheduling decisions informed by our approach deliver significant and robust profit improvement over benchmark implementations and previous models in the literature