Abstract
In this paper, we develop a revenue management model to jointly make the capacity allocation and overbooking decisions over an airline network. The crucial observation behind our model is that if the penalty cost of denying boarding to the reservations were given by a separable function, then the optimality equation for the joint capacity allocation and overbooking problem would decompose by the itineraries. We exploit this observation by building an approximation to the penalty cost that is separable by the numbers of reservations for different itineraries. In this case, we can obtain an approximate solution to the optimality equation by plugging the separable approximation into the boundary condition of the optimality equation. Our computational experiments compare our approach with a standard deterministic linear programming formulation, as well as a recent joint capacity allocation and overbooking model. When compared with the standard deterministic linear programming formulation, our approach can provide significant profit improvements. On the other hand, when compared with the recent joint capacity allocation and overbooking model, our approach can provide similar profit performance with substantially shorter runtimes.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Beckmann MJ (1958) Decision and team problems in airline reservations. Econometrica 26(1): 134–145
Bertsimas D, Popescu I (2003) Revenue management in a dynamic network environment. Transport Sci 37: 257–277
Chatwin RE (1992) Multiperiod airline overbooking with a single fare class. Oper Res 46(6):805–819
Chatwin RE (1999) Continuous-time airline overbooking with time-dependent fares and refunds. Transport Sci 33(2):182–191
Cooper WL, Homem de Mello T (2007) Some decomposition methods for revenue management. Transport Sci 41(3):332–353
Coughlan J (1999) Airline overbooking in the multi-class case. J Oper Res Soc 50(11): 1098–1103
Erdelyi A, Topaloglu H (2008) A dynamic programming decomposition method for making overbooking decisions over an airline network, Technical report, Cornell University, School of Operations Research and Information Engineering. Available at http://legacy.orie.cornell.edu/∼huseyin/publications/publications.html
Erdelyi A, Topaloglu H (2009) Separable approximations for joint capacity control and overbooking decisions in network revenue management. J Revenue Pricing Manag 8(1): 3–20
Gallego G, van Ryzin G (1997) A multiproduct dynamic pricing problem and its applications to yield management. Oper Res 45(1): 24–41
Karaesmen I, van Ryzin G (2004a) Coordinating overbooking and capacity control decisions on a network. Technical report, Columbia Business School
Karaesmen I, van Ryzin G (2004) Overbooking with substitutable inventory classes. Oper Res 52(1):83–104
Kleywegt AJ (2001) An optimal control problem of dynamic pricing. Technical report, School of Industrial and Systems Engineering, Georgia Institute of Technology
Law AL, Kelton WD (2000) Simulation modeling and analysis. McGraw-Hill, Boston
Powell WB (2007) Approximate dynamic programming: solving the curses of dimensionality. Wiley, Hoboken
Rothstein M (1971) An airline overbooking model. Transport Sci 5(2): 180–192
Rothstein M (1974) Hotel overbooking as a Markovian sequential decision process. Decis Sci 5(3): 389–404
Subramanian J, Stidham S, Lautenbacher CJ (1999) Airline yield management with overbooking, cancellations and no-shows. Transport Sci 33(2): 147–167
Talluri K, van Ryzin G (1998) An analysis of bid-price controls for network revenue management. Manag Sci 44(11): 1577–1593
Talluri KT, van Ryzin GJ (2004) The theory and practice of revenue management. Kluwer, Dordrecht
Thompson HR (1961) Statistical problems in airline reservation control. J Oper Res Soc 12(3): 167–185
Williamson EL (1992) Airline network seat control. PhD thesis, Massachusetts Institute of Technology, Cambridge
Acknowledgments
We thank the two anonymous referees and the editor for their suggestions that substantially improved the paper. Both authors gratefully acknowledge the financial support of Indian School of Business. The work of the second author was supported in part by National Science Foundation grants CMMI-0758441 and CMMI-0825004.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kunnumkal, S., Topaloglu, H. A tractable revenue management model for capacity allocation and overbooking over an airline network. Flex Serv Manuf J 20, 125 (2008). https://doi.org/10.1007/s10696-009-9057-0
Published:
DOI: https://doi.org/10.1007/s10696-009-9057-0