Swapping Applications in a Daily Airline Fleet Assignment

An airline's schedule consists of a set of flight legs that it is scheduled to fly. A fleet assignment is an assignment of equipment types (such as a 757, 767, F100 etc.) to each of the flight legs. The fleet assignment is called a daily fleet assignment if the same assignment of equipment types is used every day of the week. The daily fleet assignment has to satisfy certain coverage, balance, and equipment availability constraints. Given a daily fleet assignment, we consider the problem of changing the assignment of a specified flight leg to a different equipment type while still satisfying all the constraints. We give a simple algorithm for making this swap that will not affect the equipment type composition of aircraft overnighting at the various stations. We describe two further applications of our swapping procedure in the airline schedule development process.