Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition

Fleet assignment models (FAM) are used by many airlines to assign aircraft to flights in a schedule to maximize profit. Major airlines report that the use of FAM increases annual profits by more than $100 million. The results of FAM affect subsequent planning, marketing, and operational processes within the airline. Anticipating these processes and developing solutions favorable to them can further increase the benefits of FAM. We develop fleet assignment solutions that increase planning flexibility and reduce cost by imposing station purity, limiting the number of fleet types allowed to serve each airport in the schedule. We demonstrate that imposing station purity on the FAM can limit aircraft dispersion in the network and make solutions more robust relative to crew planning, maintenance planning, and operations. Because station purity can significantly degrade computational efficiency, we develop a solution approach, station decomposition, which takes advantage of airline network structure. Station decomposition uses a column generation approach to solving the fleet assignment problem; we further improve the performance of station decomposition by developing a primal-dual method that increases solution quality and model efficiency. Station decomposition solutions can be highly fractional; we develop a “fix-and-price” heuristic to efficiently find integer solutions to the fleet assignment problem. We estimate that the annual net benefit of station purity because of reduced maintenance and crew scheduling costs is greater than $100 million for a major U.S. domestic airline.