Using a set packing formulation to solve airline seat allocation/reallocation problems

Abstract

We report our experience in developing prototype solutions for two optimization problems faced by an airline company. Whereas previous work has focused on minimizing direct costs or maximizing direct profits, both problems in this case involve maximizing customer satisfaction. One is the seat allocation problem: given a set of groups of passengers, find the optimal assignment of passengers to seats in an aircraft so that each member of a group sits as near to the others as possible. The other is the seat reallocation problem, which arises when the aircraft is changed just before departure. It consists in finding the optimal reallocation of passengers in a new aircraft so that the original seat configuration is retained as far as possible. We formulate both as instances of the set packing problem and propose efficient methods for generating promising candidate subsets. We show through numerical experiments with real-life data that our approach is practical as regards both the computation time and the quality of solutions.