Applying Integer Linear Programming to the Fleet Assignment Problem.

This article formulates and solves the airline fleet assignment problem as an integer linear programming model, permitting the assignment of two or more fleets to a flight schedule simultaneously. The objective function can take a variety of forms including profit maximization, cost minimization, and the optimal utilization of a particular fleet type. The model can handle both the case where all flights are to be served and the case where some may be dropped. Of the five main groups of constraints, four are intrinsic to the model while the fifth is optional and includes all user-specified rules. The four intrinsic constraints are flight coverage, continuity of equipment, schedule balance, and aircraft. Each flight's contribution to the objective function is the value associated with its benefit of interest, profit, aircraft utilization, and so forth. The model described in this paper has evolved over the past six years to become a very useful tool for one-time decision support projects and has affected decision making at American Airlines in a very significant way.