An Approximation Algorithm for Capacity Allocation Over a Single Flight Leg with Fare-Locking

摘要

In this paper, we study a revenue management model over a single flight leg, where the customers are allowed to lock an available fare. Each customer arrives into the system with an interest in purchasing a ticket for a particular fare class. If this fare class is available, the customer immediately purchases the ticket by paying the fare or locks the fare by paying a fee. If the customer locks the fare, then the airline reserves the capacity for the customer for a certain duration of time. At the end of this duration of time, the customer makes her ultimate purchase decision at the locked fare. The goal of the airline is to find a policy to decide which set of fare classes to make available at each time period to maximize the total expected revenue. Such fare locking options are commonly offered by airlines; the dynamic programming formulation of the revenue management problem with the option to lock an available fare has a high-dimensional state variable that keeps track of the locked fares. We develop an approximate policy that is guaranteed to obtain at least half of the optimal total expected revenue. Our approach is based on leveraging a linear programming approximation to decompose the problem by the seats on the flight and solving a dynamic program that separately controls the capacity on each seat. We also show that our results continue to hold when the airline makes pricing decisions instead of fare class availability decisions. Our numerical experiments show that the practical performance of our approximate policy is remarkably good compared to a tractable upper bound on the optimal total expected revenue.