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 that greatly influences airline profits. As passenger demand is often substitutable among available fare products (defined as a combination of an itinerary and a fare class) between the same origin–destination pair, we present an optimization approach that includes 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 dependencies in network structure. The decomposition relies on a series of approximation analyses and a novel fare split problem to allocate optimally the fares of products that are shared by flights in different subnetworks. We present several reformulations that represent fleet assignment and schedule decisions and formally characterize their relative strengths. This gives rise to a new reformulation that is able to trade off strength and size flexibly. 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 all benchmark implementations and previous models in the literature.