Dynamic two-leg airline seat inventory control with overbooking, cancellations and no-shows

This paper formulates a discrete time, finite horizon Markov decision process (dynamic programming), for the two–leg airline seat inventory control problem. The dynamics of the passenger reservation process together with realistic elements of customer behaviour such as cancellations, no–shows and overbooking are explicitly considered. Mirroring the dynamic seat inventory control models for the single–leg flight, it solves the two–leg seat allocation problem with multiple fare classes, and generalises the formulation to the multileg airline seat inventory control problem. A computationally efficient model is developed and is shown to provide solutions that are within a few percentage points of the optimal solution.