Stochastic regret minimization for revenue management problems with nonstationary demands
dc.contributor.author | Zhang, Huanan | |
dc.contributor.author | Shi, Cong | |
dc.contributor.author | Qin, Chao | |
dc.contributor.author | Hua, Cheng | |
dc.date.accessioned | 2017-01-06T20:51:16Z | |
dc.date.available | 2017-11-01T15:31:29Z | en |
dc.date.issued | 2016-09 | |
dc.identifier.citation | Zhang, Huanan; Shi, Cong; Qin, Chao; Hua, Cheng (2016). "Stochastic regret minimization for revenue management problems with nonstationary demands." Naval Research Logistics (NRL) 63(6): 433-448. | |
dc.identifier.issn | 0894-069X | |
dc.identifier.issn | 1520-6750 | |
dc.identifier.uri | https://hdl.handle.net/2027.42/135128 | |
dc.description.abstract | We study an admission control model in revenue management with nonstationary and correlated demands over a finite discrete time horizon. The arrival probabilities are updated by current available information, that is, past customer arrivals and some other exogenous information. We develop a regret‐based framework, which measures the difference in revenue between a clairvoyant optimal policy that has access to all realizations of randomness a priori and a given feasible policy which does not have access to this future information. This regret minimization framework better spells out the trade‐offs of each accept/reject decision. We proceed using the lens of approximation algorithms to devise a conceptually simple regret‐parity policy. We show the proposed policy achieves 2‐approximation of the optimal policy in terms of total regret for a two‐class problem, and then extend our results to a multiclass problem with a fairness constraint. Our goal in this article is to make progress toward understanding the marriage between stochastic regret minimization and approximation algorithms in the realm of revenue management and dynamic resource allocation. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 433–448, 2016 | |
dc.publisher | Wiley Periodicals, Inc. | |
dc.publisher | Springer | |
dc.subject.other | worst‐case bounds | |
dc.subject.other | algorithms | |
dc.subject.other | admission control | |
dc.subject.other | revenue management | |
dc.subject.other | regret minimization | |
dc.subject.other | nonhomogeneous Poisson processes | |
dc.title | Stochastic regret minimization for revenue management problems with nonstationary demands | |
dc.type | Article | en_US |
dc.rights.robots | IndexNoFollow | |
dc.subject.hlbsecondlevel | Statistics (Mathematical) | |
dc.subject.hlbtoplevel | Science | |
dc.description.peerreviewed | Peer Reviewed | |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/135128/1/nav21704.pdf | |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/135128/2/nav21704_am.pdf | |
dc.identifier.doi | 10.1002/nav.21704 | |
dc.identifier.source | Naval Research Logistics (NRL) | |
dc.identifier.citedreference | G.S. Lueker, “ Average‐case analysis of off‐line and on‐line knapsack problems,” in: Proceedings of the Sixth Annual ACM‐SIAM symposium on discrete algorithms. SODA ‘95, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp. 179 – 188, 1995. | |
dc.identifier.citedreference | A.J. Kleywegt and J.D. Papastavrou, The dynamic and stochastic knapsack problem with random sized items, Oper Res 49 ( 2001 ), 26 – 41. | |
dc.identifier.citedreference | R. Kumar, M.E. Lewis, and H. Topaloglu, Dynamic service rate control for a single‐server queue with Markov‐modulated arrivals, Nav Res Logist 60 ( 2013 ), 661 – 677. | |
dc.identifier.citedreference | Y. Lan, M.O. Ball, and I.Z. Karaesmen, Regret in overbooking and fare‐class allocation for single leg, Manufact Serv Oper Manage 13 ( 2011 ), 194 – 208. | |
dc.identifier.citedreference | R. Levi, G. Janakiraman, and M. Nagarajan, A 2‐approximation algorithm for stochastic inventory control models with lost‐sales, Math Oper Res 33 ( 2008 ), 351 – 374. | |
dc.identifier.citedreference | R. Levi, M. Pál, R.O. Roundy, and D.B. Shmoys, Approximation algorithms for stochastic inventory control models, Math Oper Res 32 ( 2007 ), 284 – 302. | |
dc.identifier.citedreference | R. Levi and A. Radovanović, Technical note: Provably near‐optimal LP‐based policies for revenue management in systems with reusable resources. Oper Res 58 ( 2010 ), 503 – 507. | |
dc.identifier.citedreference | R. Levi, R.O. Roundy, D.B. Shmoys, and V.A. Truong, Approximation algorithms for capacitated stochastic inventory models, Oper Res 56 ( 2008 ), 1184 – 1199. | |
dc.identifier.citedreference | R. Levi and C. Shi, Approximation algorithms for the stochastic lot‐sizing problem with order lead times, Oper Res 61 ( 2013 ), 593 – 602. | |
dc.identifier.citedreference | W. Massey and W. Whitt, Peak congestion in multi‐server service systems with slowly varying arrival rates, Queueing Syst 25 ( 1997 ), 157 – 172. | |
dc.identifier.citedreference | T.C. Mills, Time series techniques for economists. Cambridge University Press, Cambridge, UK, 1991 | |
dc.identifier.citedreference | S. Netessine, Dynamic pricing of inventory/capacity with infrequent price changes, Eur J Oper Res 174 ( 2006 ), 553 – 580. | |
dc.identifier.citedreference | J.D. Papastavrou, S. Rajagopalan, and A.J. Kleywegt, The dynamic and stochastic knapsack problem with deadlines, Manage Sci 42 ( 1996 ), 1706 – 1718. | |
dc.identifier.citedreference | G. Perakis and G. Roels, Robust controls for network revenue management, Manufact Serv Oper Manage 12 ( 2010 ), 56 – 76. | |
dc.identifier.citedreference | W.B. Powell, Approximate dynamic programming solving the curse of dimensionality, 2nd ed. Wiley, Hoboken, NJ, 2011. | |
dc.identifier.citedreference | N.U. Prabhu and Y. Zhu, Markov‐modulated queueing systems, Queueing Syst 5 ( 1989 ), 215 – 245. | |
dc.identifier.citedreference | P. Rusmevichientong and H. Topaloglu, Robust assortment optimization in revenue management under the multinomial logit choice model, Oper Res 60 ( 2012 ), 865 – 882. | |
dc.identifier.citedreference | C. Shi, H. Zhang, X. Chao, and R. Levi, Approximation algorithms for capacitated stochastic inventory systems with setup costs, Nav Res Logist 61 ( 2014 ), 304 – 319. | |
dc.identifier.citedreference | K.T. Talluri and G. van Ryzin, The theory and practice of revenue management, Springer, New York, 2004. | |
dc.identifier.citedreference | TugBBS, Timeshare users group online discussion forums, 2016, http://tugbbs.com/forums/, last accessed August 1, 2016. | |
dc.identifier.citedreference | P. Van Hentenryck, R. Bent, L. Mercier, and Y. Vergados, Online stochastic reservation systems, Ann Oper Res 171 ( 2009 ), 101 – 126. | |
dc.identifier.citedreference | Z. Wang, S. Deng, and Y. Ye, Close the gaps: A learning‐while‐doing algorithm for single‐product revenue management problems, Oper Res 62 ( 2014 ), 318 – 331. | |
dc.identifier.citedreference | S. Yoon and M. Lewis, Optimal pricing and admission control in a queueing system with periodically varying parameters, Queueing Syst 47 ( 2004 ), 177 – 199. | |
dc.identifier.citedreference | H. Zhang, C. Shi, and X. Chao, Approximation algorithms for perishable inventory systems with setup costs. Oper Res 64 ( 2016 ), 432 – 440. | |
dc.identifier.citedreference | W. Zhao and Y. Zheng, Optimal dynamic pricing for perishable assets with nonhomogeneous demand, Manage Sci 46 ( 2000 ), 375 – 388. | |
dc.identifier.citedreference | M. Ball and M. Queyranne, Towards robust revenue management: Competitive analysis of online booking. Oper Res 57 ( 2009 ), 950 – 963. | |
dc.identifier.citedreference | A. Ben‐Tal and A. Nemirovski, Robust solutions of uncertain linear programs, Oper Res Lett 25 ( 1999 ), 1 – 13. | |
dc.identifier.citedreference | D. Bertsimas and M. Sim, The price of robustness, Oper Res 52 ( 2004 ), 35 – 53. | |
dc.identifier.citedreference | S.I. Birbil, J.B.G. Frenk, J.A.S. Gromicho, S. Zhang, The role of robust optimization in single‐leg airline revenue management, Manage Sci 55 ( 2009 ), 148 – 163. | |
dc.identifier.citedreference | G. Bitran and R. Caldentey, An overview of pricing models for revenue management, Manufact Serv Oper Manage 5 ( 2003 ), 203 – 229. | |
dc.identifier.citedreference | J. Broder and P. Rusmevichientong, Dynamic pricing under a general parametric choice model, Oper Res 60 ( 2012 ), 965 – 980. | |
dc.identifier.citedreference | P. Cao, J. Li, H. Yan, Optimal dynamic pricing of inventories with stochastic demand and discounted criterion, Eur J Oper Res 217 ( 2012 ), 580 – 588. | |
dc.identifier.citedreference | C.W. Chan, V.F. Farias, Stochastic depletion problems: Effective myopic policies for a class of dynamic optimization problems, Math Oper Res 34 ( 2009 ), 333 – 350. | |
dc.identifier.citedreference | X. Chao, X. Gong, C. Shi, H. Zhang, Approximation algorithms for perishable inventory systems. Oper Res 63 ( 2015 ), 585 – 601. | |
dc.identifier.citedreference | Y. Chen, V.F. Farias, Simple policies for dynamic pricing with imperfect forecasts. Oper Res 61 ( 2013 ), 612 – 624. | |
dc.identifier.citedreference | Club, Hilton Grand Vacations, Hilton grand vacations club reservation options, 2016 http://www.hgvclubprogram.com/club-features/reservations/, last accessed August 1, 2016. | |
dc.identifier.citedreference | E.G., Coffman, Jr., J. Csirik, G. Galambos, S. Martello, and D. Vigo, “ Bin packing approximation algorithms: Survey and classification,” in: P.M. Pardalos, D.‐Z. Du, and R.L. Graham (Editors), Handbook of combinatorial optimization, Springer New York, 455 – 531, 2013. | |
dc.identifier.citedreference | B. C. Dean, M.X. Goemans, and J. Vondrák, Approximating the stochastic knapsack problem: The benefit of adaptivity, Math Oper Res 33 ( 2008 ), 945 – 964. | |
dc.identifier.citedreference | A.V. den Boer, B. Zwart, Simultaneously learning and optimizing using controlled variance pricing, Manage Sci 60 ( 2014 ), 770 – 783. | |
dc.identifier.citedreference | F.C. Dragos, and V.F. Farias, Model predictive control for dynamic resource allocation, Math Oper Res 37 ( 2012 ), 501 – 525. | |
dc.identifier.citedreference | A.N. Elmachtoub and R. Levi, From cost sharing mechanisms to online selection problems. Math Oper Res 40 ( 2014 ), 542 – 557. | |
dc.identifier.citedreference | A.N. Elmachtoub and R. Levi, Supply chain management with online customer selection, Oper Res 64 ( 2016 ), 458 – 473. | |
dc.identifier.citedreference | G. Gallego and Ö. Özer, Integrating replenishment decisions with advance demand information, Manage Sci 47 ( 2001 ), 1344 – 1360. | |
dc.identifier.citedreference | G. Gallego and G. van Ryzin, Optimal dynamic pricing of inventories with stochastic demand over finite horizons, Manage Sci 40 ( 1994 ), 999 – 1020. | |
dc.identifier.citedreference | G. Gallego, G. van Ryzin, A multiproduct dynamic pricing problem and its applications to network yield management, Oper Res 45 ( 1997 ), 24 – 41. | |
dc.identifier.citedreference | X. Geng, W.T. Huh, and M. Nagarajan, Sequential resource allocation with constraints: Two‐customer case, Oper Res Lett 42 ( 2014 ), 70 – 75. | |
dc.identifier.citedreference | J.M. George and J.M. Harrison, Dynamic control of a queue with adjustable service rate, Oper Res 49 ( 2001 ), 720 – 731. | |
dc.identifier.citedreference | S. Graves, H. Meal, S. Dasu, and Y. Qin, “ Two‐stage production planning in a dynamic environment,” S. Axsater, C. Schneeweiss, E. Silver, (Editors), Multi‐stage production planning and control. Lecture notes in economics and mathematical systems, Springer‐Verlag, Berlin, Germany, 1986, pp. 9 – 43. | |
dc.identifier.citedreference | L.V. Green and P.J. Kolesar, On the accuracy of the simple peak hour approximation for Markovian queues, Manage Sci 41 ( 1995 ), 1353 – 1370. | |
dc.identifier.citedreference | S. Guha and K. Munagala, “ Stochastic regret minimization via thompson sampling,” in: Proceedings of the 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13–15, 2014, pp. 317 – 338. | |
dc.identifier.citedreference | V. Gupta, M. Harchol‐Balter, A.S. Wolf, and U. Yechiali, Fundamental characteristics of queues with fluctuating load. SIGMETRICS Perf Eval Rev 34 ( 2006 ), 203 – 215. | |
dc.identifier.citedreference | J.M. Harrison, N.B. Keskin, and A. Zeevi, Bayesian dynamic pricing policies: Learning and earning under a binary prior distribution, Manage Sci 58 ( 2012 ), 570 – 586. | |
dc.identifier.citedreference | D.C., Heath and P.L. Jackson, Modeling the evolution of demand forecasts with application to safety stock analysis in production/distribution system, IIE Trans 26 ( 1994 ), 17 – 30. | |
dc.identifier.citedreference | G. Iyengar and K. Sigman, Exponential penalty function control of loss networks. Ann Appl Prob 14 ( 2004 ), 1698 – 1740. | |
dc.identifier.citedreference | F.P. Kelly, Effective bandwidths at multi‐class queues, Queueing Syst 9 ( 1991 ), 5 – 16. | |
dc.identifier.citedreference | P. Key, Optimal control and trunk reservation in loss networks. Prob Eng Inform Sci 4 ( 1990 ), 203 – 242. | |
dc.identifier.citedreference | A.J. Kleywegt and J.D. Papastavrou, The dynamic and stochastic knapsack problem, Oper Res 46 ( 1998 ), 17 – 35. | |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.