Advances in the optimization of airline fleet assignment

Abstract

We present an advanced model for the formulation and solution of large scale fleet assignment problems that arise in the scheduling of air transportation. Fleet assignment determines the type of aircraft to operate each flight in a given schedule, subject to a variety of side constraints, due to marketing, operational, maintenance and crew restrictions. We model the problem as mixed-integer multicommodity flow on networks encoding activities linking flight departures. We focus on fully representing flight connection possibilities, while accurately capturing complex operational rules. We also provide a unified framework for the expression of resource constraints via piecewise linear penalties, which permits a profitability-based tradeoff between operational goals and revenue. Computational results on actual schedules show that high quality assignments for one-day problems can be obtained within an hour of computation. The use of the model at USAir results in an annual benefit of at least $15 million.