Airline yield management with overbooking, cancellations and no-shows

We formulate and analyze a Markov decision process (dynamic programming) model for airline seat allocation (yield management) on a single-leg flight with multiple fare classes. Unlike previous models, we allow cancellation, no-shows, and overbooking. Additionally, we make no assumptions on the arrival patterns for the various fare classes. Our model is also applicable to other problems of revenue management with perishable commodities, such as arise in the hotel and cruise industries. We show how to solve the problem exactly using dynamic program-ming. Under realistic conditions, we demonstrate that an optimal booking policy is character-ized by state- and time-dependent booking limits for each fare class. Our approach exploits the equivalence to a problem in the optimal control of admission to a queueing system, which has been well studied in the queueing-control literature. Techniques for efficient implementation of the optimal policy and numerical examples are also given. In contrast to previous models, we show that 1) the booking limits need not be monotonic in the time remaining until departure; 2) it may be optimal to accept a lower-fare class and simultaneously reject a higher-fare class because of differing cancellation refunds, so that the optimal booking limits may not always be nested according to fare class; and 3) with the possibility of cancellations, an optimal polic