A Randomized Linear Programming Method for Network Revenue Management with Product-Specific No-Shows

Sumit Kunnumkal (), Kalyan Talluri () and Huseyin Topaloglu ()
Additional contact information
Sumit Kunnumkal: Indian School of Business, Gachibowli, Hyderabad 500032, India
Kalyan Talluri: ICREA and Universitat Pompeu Fabra, 08005 Barcelona, Spain
Huseyin Topaloglu: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853

Transportation Science, 2012, vol. 46, issue 1, 90-108

Abstract: Revenue management practices often include overbooking capacity to account for customers who make reservations but do not show up. In this paper, we consider the network revenue management problem with no-shows and overbooking, where the show-up probabilities are specific to each product. No-show rates differ significantly by product (for instance, each itinerary and fare combination for an airline) as sale restrictions and the demand characteristics vary by product. However, models that consider no-show rates by each individual product are difficult to handle because the state-space in dynamic programming formulations (or the variable space in approximations) increases significantly. In this paper, we propose a randomized linear program to jointly make the capacity control and overbooking decisions with product-specific no-shows. We establish that our formulation gives an upper bound on the optimal expected total profit, and our upper bound is tighter than a deterministic linear programming upper bound that appears in the existing literature. Furthermore, we show that our upper bound is asymptotically tight in a regime where the leg capacities and the expected demand is scaled linearly with the same rate. We also describe how the randomized linear program can be used to obtain a bid price control policy. Computational experiments indicate that our approach is quite fast, is able to scale to industrial problems, and can provide significant improvements over standard benchmarks.

Keywords: network revenue management; linear programming; simulation; overbooking; no-shows (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1110.0386 (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:ortrsc:v:46:y:2012:i:1:p:90-108

Access Statistics for this article

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