This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Erdelyi, A. Articles by Topaloglu, H.

A Dynamic Programming Decomposition Method for Making Overbooking Decisions Over an Airline Network

School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
alex{at}orie.cornell.edu
topaloglu{at}orie.cornell.edu

In this paper, we develop a revenue management model to jointly make the capacity allocation and overbooking decisions over an airline network. Our approach begins with the dynamic programming formulation of the capacity allocation and overbooking problem and uses an approximation strategy to decompose the dynamic programming formulation by the flight legs. This decomposition idea opens up the possibility of obtaining approximate solutions by concentrating on one flight leg at a time, but the capacity allocation and overbooking problem that takes place over a single flight leg still turns out to be intractable. We use a state aggregation approach to obtain high-quality solutions to the single-leg problem. Overall, our model constructs separable approximations to the value functions, which can be used to make the capacity allocation and overbooking decisions for the whole airline network. Computational experiments indicate that our model performs significantly better than a variety of benchmark strategies from the literature.

Key words: network revenue management; overbooking; approximate dynamic programming
History: received September 2008; revised June 2009; accepted July 2009.