This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Karaesmen, I. Articles by van Ryzin, G. Search for Related Content

Overbooking with Substitutable Inventory Classes

Robert H. Smith School of Business, 4357 Van Munching Hall, University of Maryland, College Park, Maryland 20742
412 Uris Hall, Columbia University, New York, New York 10027
itir{at}umd.edu
gjv1{at}columbia.edu

This paper considers an overbooking problem with multiple reservation and inventory classes, in which the multiple inventory classes may be used as substitutes to satisfy the demand of a given reservation class (perhaps at a cost). The problem is to jointly determine overbooking levels for the reservation classes, taking into account the substitution options. Such problems arise in a variety of revenue management contexts, including multicabin aircraft, back-to-back scheduled flights on the same leg, hotels with multiple room types, and mixed-vehicle car rental fleets. We model this problem as a two-period optimization problem. In the first period, reservations are accepted given only probabilistic knowledge of cancellations. In the second period, cancellations are realized and surviving customers are assigned to the various inventory classes to maximize the net benefit of assignments (e.g., minimize penalties). For this formulation, we show that the expected revenue function is submodular in the overbooking levels, which implies the natural property that the optimal overbooking level in one reservation class decreases with the number of reservations held in the other reservation classes. We then propose a stochastic gradient algorithm to find the joint optimal overbooking levels. We compare the decisions of the model to those produced by more naive heuristics on some examples motivated by airline applications. The results show that accounting for substitution when setting overbooking levels has a small, but still significant, impact on revenues and costs.

Subject classifications: Transportation: overbooking, yield management; Inventory/production: perishable inventory, stochastic; Probability: stochastic optimization.
History: Received October 1998; revision received January 2001; accepted December 2002.

This article has been cited by other articles:

				W. H. Wong, A. Zhang, Y. Van Hui, and L. C. Leung Optimal Baggage-Limit Policy: Airline Passenger and Cargo Allocation Transportation Science, August 1, 2009; 43(3): 355 - 369. [Abstract] [PDF]

				R. A. Shumsky and F. Zhang Dynamic Capacity Management with Substitution Operations Research, May 1, 2009; 57(3): 671 - 684. [Abstract] [PDF]

				H. Topaloglu A Stochastic Approximation Method to Compute Bid Prices in Network Revenue Management Problems INFORMS Journal on Computing, September 1, 2008; 20(4): 596 - 610. [Abstract] [PDF]

				G. van Ryzin and G. Vulcano Simulation-Based Optimization of Virtual Nesting Controls for Network Revenue Management Operations Research, July 1, 2008; 56(4): 865 - 880. [Abstract] [PDF]

				S. Kunnumkal and H. Topaloglu Using Stochastic Approximation Methods to Compute Optimal Base-Stock Levels in Inventory Control Problems Operations Research, May 1, 2008; 56(3): 646 - 664. [Abstract] [PDF]

				K. Amaruchkul, W. L. Cooper, and D. Gupta Single-Leg Air-Cargo Revenue Management Transportation Science, November 1, 2007; 41(4): 457 - 469. [Abstract] [PDF]

				H. Topaloglu and W. Powell Incorporating Pricing Decisions into the Stochastic Dynamic Fleet Management Problem Transportation Science, August 1, 2007; 41(3): 281 - 301. [Abstract] [PDF]

				W. L. Cooper and T. Homem-de-Mello Some Decomposition Methods for Revenue Management Transportation Science, August 1, 2007; 41(3): 332 - 353. [Abstract] [PDF]

				S. Choi Group Revenue Management: A Model for Evaluating Group Profitability Cornell Hospitality Quarterly, August 1, 2006; 47(3): 260 - 271. [Abstract] [PDF]

				W. L. Cooper and D. Gupta Stochastic Comparisons in Airline Revenue Management MSOM, January 1, 2006; 8(3): 221 - 234. [Abstract] [PDF]

				D. Zhang and W. L. Cooper Revenue Management for Parallel Flights with Customer-Choice Behavior Operations Research, May 1, 2005; 53(3): 415 - 431. [Abstract] [PDF]