The Underlying Markov Decision Process in the Single-Leg Airline Yield-Management Problem

TLDR

The single‑leg airline yield‑management problem is traditionally approached either dynamically, allowing simultaneous booking of multiple fare classes, or statically, assuming fare‑class demands arrive in a predetermined order.

Abstract

We introduce the terms dynamic and static, respectively, to identify the prevailing approaches to the single-leg airline yield-management problem: those allowing customers of different fare classes to book concomitantly (dynamic), and those assuming that the demands for the different fare classes arrive separately in a predetermined order (static). We present a coherent frame-work linking these seemingly disparate models through the underlying dynamic program common to both. We develop a discrete-time Markov decision process formulation mirroring that of Janakiram et al. Transp. Sci. 33, 147–167 (1999) to solve the single-leg problem without cancellations, overbooking, or discounting. Borrowing a result from the queueing-control literature, we prove the concavity of the associated optimal value functions and, subsequently, the optimality of a booking limit policy. We then apply this same technique to the more influential papers from the single-leg literature, at once unifying the static and dynamic models and establishing the connection between the yield-management and queueing-control problems. Finally, we propose an omnibus formulation that yields the static and dynamic models as special cases.