Meissner, Joern, Strauss, Arne and Talluri, Kalyan T.. (2013) An enhanced concave program relaxation for choice network revenue management. Production and Operations Management, 22 (1). pp. 71-87. ISSN 1059-1478

Preview

PDF WRAP_Strauss_PubDocView.asp.pdf - Submitted Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (289Kb)

Abstract

The network choice revenue management problem models customers as choosing from an offer set, and the firm decides the best subset to offer at any given moment to maximize expected revenue. The resulting dynamic program for the firm is intractable and approximated by a deterministic linear program called the CDLP which has an exponential number of columns. However, under the choice-set paradigm when the segment consideration sets overlap, the CDLP is difficult to solve. Column generation has been proposed but finding an entering column has been shown to be NP-hard. In this paper, starting with a concave program formulation called SDCP that is based on segment-level consideration sets, we add a class of constraints called product constraints (σPC), that project onto subsets of intersections. In addition we propose a natural direct tightening of the SDCP called ESDCPκ, and compare the performance of both methods on the benchmark data sets in the literature. In our computational testing on the benchmark data sets in the literature, 2PC achieves the CDLP value at a fraction of the CPU time taken by column generation. For a large network our 2PC procedure runs under 70 seconds to come within 0.02% of the CDLP value, while column generation takes around 1 hour; for an even larger network with 68 legs, column generation does not converge even in 10 hours for most of the scenarios while 2PC runs under 9 minutes. Thus we believe our approach is very promising for quickly approximating CDLP when segment consideration sets overlap and the consideration sets themselves are relatively small.

Item Type:	Journal Article
Subjects:	H Social Sciences > HB Economic Theory Q Science > QA Mathematics
Divisions:	Faculty of Social Sciences > Warwick Business School
Library of Congress Subject Headings (LCSH):	Revenue management -- Mathematical models
Journal or Publication Title:	Production and Operations Management
Publisher:	Wiley-Blackwell Publishing Ltd.
ISSN:	1059-1478
Date:	January 2013
Volume:	22
Number:	1
Page Range:	pp. 71-87
Identification Number:	10.1111/j.1937-5956.2012.01345.x
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
References:	Bodea, T., M. Ferguson, L. Garrow. 2009. Choice-based revenue management: Data from a major hotel chain. Manufacturing and Service Operations Management 11 356–361. Bront, J. J. M., I. M´endez-D´ıaz, G. Vulcano. 2009. A column generation algorithm for choice-based network revenue management. Operations Research 57(3) 769–784. Gallego, G., G. Iyengar, R. Phillips, A. Dubey. 2004. Managing flexible products on a network. Tech. Rep. TR-2004-01, Dept of Industrial Engineering, Columbia University, NY, NY. Gallego, G., R. Ratliff, S. Shebalov. 2010. A general attraction model and an efficient formulation for the network revenue management problem. Tech. rep., Department of IEOR, Columbia University, available at http://www.columbia.edu/~gmg2/. Hauser, J.R., B. Wernerfelt. 1990. An evaluation cost model of consideration sets. Journal of Consumer Research 16 393–408. K¨ok, G., M. L. Fisher, R. Vaidyanathan. 2009. Retail supply chain management: Quantitative models and empirical studies, chap. Assortment planning: Review of literature and industry practice. Springer, NY,NY, USA, 99–154. Kunnumkal, S. 2011. Randomization approaches for the network revenue management with customer choice behavior. Tech. rep., Indian School of Business, Hyderabad, India. Kunnumkal, S., H. Topaloglu. 2010. A new dynamic programming decomposition method for the network revenue management problem with customer choice behavior. Production and Operations Management 19(5) 575–590. Liu, Q., G. van Ryzin. 2008. On the choice-based linear programming model for network revenue management. Manufacturing and Service Operations Management 10(2) 288–310. Lussier, D. A., R. W. Olshavsky. 1979. Task complexity and contingent processing in brand choice. Journal of Consumer Research 6(2) 154–165. Meissner, J., A. K. Strauss. 2012. Network revenue management with inventory-sensitive bid prices and customer choice. European Journal of Operational Research 216(2) 459–468. M´endez-D´ıaz, I., J. Miranda Bront, G. Vulcano, P. Zabala. 2012. A branch-and-cut algorithm for the latentclass logit assortment problem. Discrete Applied Mathematics (forthcoming). Payne, J. W. 1976. Task complexity and contingent processing in decision-making: An information search and protocol analysis. Organizational Behavior and Human Performance 16(2) 366–387. Rusmevichientong, P., D. Shmoys, H. Topaloglu. 2010. Assortment optimization with mixtures of logits. Tech. rep., School of IEOR, Cornell University. Talluri, K. T. 2001. Airline revenue management with passenger routing control: A new model with solution approaches. International Journal of Services Technology and Management 2 102–115. Talluri, K. T. 2010. A randomized concave programming method for choice network revenue management. Tech. rep., Working Paper 1215, Department of Economics, Universitat Pompeu Fabra, Barcelona, Spain. Talluri, K. T., G. J. van Ryzin. 2004a. Revenue management under a general discrete choice model of consumer behavior. Management Science 50(1) 15–33. Talluri, K. T., G. J. van Ryzin. 2004b. The Theory and Practice of Revenue Management . Kluwer, New York, NY. Wright, P., F. Barbour. 1977. Multiple Criteria Decision Making, chap. Phased decision strategies: Sequels to intial screening. TIMS: Studies in the Management Sciences, North-Holland, Amsterdam, Holland, 91–109. Zhang, D., D. Adelman. 2009. An approximate dynamic programming approach to network revenue management with customer choice. Transportation Science 43(3) 381–394.
URI:	http://wrap.warwick.ac.uk/id/eprint/40122

Request changes to a record

Actions (login required)

View Item