Airplane Fleet Assignment and Extensions: A New Model and Solution Approach

Professor Cynthia Barnhart

Co-Director, Operations Research Center

Massachusetts Institute of Technology

The fleet assignment problem addresses the question of how to best assign a given fleet of aircraft to a given airline flight schedule. Finding a feasible fleet assignment, let alone an optimal one, is a non-trivial task given the scale of operation of major airlines. Each flight must be assigned an aircraft, the assigned aircraft must be available at the right airport and the right time, and only available aircraft of each particular fleet type can be assigned. Optimization models are now routinely employed by major airlines to determine their fleet assignments, and significant cost savings have been reported. These models, however, use an approximate objective function, potentially leading to sub-optimal solutions. Researchers have proposed various new models and solution approaches to overcome these shortcomings but these models suffer from tractability issues. Motivated by the need to provide accurate yet tractable fleet assignment models, we present in this paper a new model and solution approach for fleet assignment. Our approach focuses on: 1) providing improved LP bounds to enhance model tractability for large-scale problems and to allow solution of extended fleet assignment problems incorporating schedule design decisions; and 2)allowing a trade-off between solution quality and solution time. Using data provided by a large U.S. airline, we evaluate the performance of our approach and find that improved solutions for large-scale fleet assignment problems can be achieved with reduced solution times.