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

Mika Sumida () and Huseyin Topaloglu ()
Additional contact information
Mika Sumida: School of Operations Research and Information Engineering, Cornell Tech, New York, New York 10044
Huseyin Topaloglu: School of Operations Research and Information Engineering, Cornell Tech, New York, New York 10044

INFORMS Journal on Computing, 2019, vol. 31, issue 1, 83-99

Abstract: 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.

Keywords: revenue management; airlines; dynamic programming (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0816 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:1:p:83-99

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().