Polyhedral Analysis and Algorithms for a Demand-Driven Refleeting Model for Aircraft Assignment

The current airline practice in conducting fleet assignments is to begin assigning aircraft capacity to scheduled flights well in advance of departures. However, the accuracy of the passenger demand forecast improves markedly over time, and revisions to the initial fleet assignment become naturally pertinent when the observed demand differs considerably from the assigned aircraft capacities. The demand-driven refleeting (DDR) approach proposed in this paper offers a dynamic reassignment of aircraft capacities to the flight network, when improved demand forecasts become available, so as to maximize the total revenue. Because of the need to preserve the initial crew schedule, this reassignment approach is limited within a single family of aircraft types and to the flights assigned to this particular family. This restriction makes it computationally tractable to include more relevant path-level demand information into the DDR model. Accordingly, we construct a mixed-integer programming model for this enhanced problem context and study its polyhedral structure to explore ways for tightening its representation and for deriving certain classes of valid inequalities. Various schemes for implementing such reformulation techniques are investigated and tested using a set of simulated and real instances obtained from United Airlines.