A dynamic programming decomposition method for making overbooking decisions over an airline network

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.