About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the Operations Research Society of Japan
Paper
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.