Network models for seat allocation on flights

This paper examines the problem of proper (optimal) control over the seat allocation on flights. Given a heterogeneous fleet of aircraft types, multi-leg flights, a number of different passenger categories, and cancelations, an airline's objective is to devise an effective system which aids in setting the seat allocation targets for each category of passengers on each flight. This issue is analyzed by a number of authors in the context of economic, simulation based, probabilistic, and mathematical programming studies. We present an attempt to address this problem from the systems prospective emphasizing characteristics such as: passenger cancelations, multi-leg flights, and rolling tactical planning time horizon. Starting from a very simple network flow models for a single flight with a number of intermediate stops, a number of progressively complex models are presented. The airline flights and the seat allocation system are represented as a generalized network flow model (with gains/losses on arcs) with the objective of flow maximization (profit maximization). This modelling approach does not claim to replace the seat allocation approaches presented in Alstrup et al. (1985), Mayer (1976), Richter (1982), Simpson (1985a), and Wang (1983), but rather construct seat allocations utilizing some of those referenced schemes in a parameter setting mode for a large network model. The objective of this paper is not to report on computational experiments, but to present a modeling approach which seems to be promising, if somewhat speculative.