×

zbMATH — the first resource for mathematics

A stochastic approximation method for the single-leg revenue management problem with discrete demand distributions. (English) Zbl 1177.93099
Summary: We consider the problem of optimally allocating the seats on a single flight leg to the demands from multiple fare classes that arrive sequentially. It is well-known that the optimal policy for this problem is characterized by a set of protection levels. In this paper, we develop a new stochastic approximation method to compute the optimal protection levels under the assumption that the demand distributions are not known and we only have access to the samples from the demand distributions. The novel aspect of our method is that it works with the nonsmooth version of the problem where the capacity can only be allocated in integer quantities. We show that the sequence of protection levels generated by our method converges to a set of optimal protection levels with probability one. We discuss applications to the case where the demand information is censored by the seat availability. Computational experiments indicate that our method is especially advantageous when the total expected demand exceeds the capacity by a significant margin and we do not have good a priori estimates of the optimal protection levels.

MSC:
93E20 Optimal stochastic control
49L20 Dynamic programming in optimal control and differential games
90B50 Management decision making, including multiple objectives
93E25 Computational methods in stochastic control (MSC2010)
91B70 Stochastic models in economics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bashyam S, Fu MC (1998) Optimizaton of (s,S) inventory systems with random lead times and a service level constraint. Manage Sci 44(12): 243–256 · Zbl 0989.90004 · doi:10.1287/mnsc.44.12.S243
[2] Bertsekas DP, Tsitsiklis JN (1996) Neuro-dynamic programming. Athena Scientific, Belmont
[3] Bertsimas D, de Boer S (2005) Simulation-based booking limits for airline revenue management. Oper Res 53(1): 90–106 · Zbl 1165.90557 · doi:10.1287/opre.1040.0164
[4] Brumelle SL, McGill JI (1993) Airline seat allocation with multiple nested fare classes. Oper Res 41: 127–137 · Zbl 0775.90148 · doi:10.1287/opre.41.1.127
[5] Curry RE (1990) Optimal airline seat allocation with fare classes nested by origins and destinations. Transp Sci 24: 193–204 · doi:10.1287/trsc.24.3.193
[6] Ermoliev Y (1988) Stochastic quasigradient methods. In: Ermoliev Y, Wets R(eds) Numerical techniques for stochastic optimization.. Springer, Berlin · Zbl 0666.90072
[7] Fu M (1994) Sample path derivatives for (s,S) inventory systems. Oper Res 42(2): 351–363 · Zbl 0805.90038 · doi:10.1287/opre.42.2.351
[8] Glasserman P, Tayur S (1995) Sensitivity analysis for base-stock levels in multiechelon production-inventory systems. Manage Sci 41(2): 263–281 · Zbl 0832.90051 · doi:10.1287/mnsc.41.2.263
[9] Huh WT, Rusmevichientong P (2006) Adaptive capacity allocation with censored demand data: application of concave umbrella functions, Technical report, Cornell University, School of Operations Research and Information Engineering
[10] Huh WT, Levi R, Rusmevichientong P, Orlin JB (2008) Adaptive data-driven inventory control policies based on Kaplan–Meier estimator, Technical report, School of Operations Research and Information Engineering, Cornell University
[11] Karaesmen I, van Ryzin G (2004) Overbooking with substitutable inventory classes. Oper Res 52(1): 83–104 · Zbl 1165.90323 · doi:10.1287/opre.1030.0079
[12] Kunnumkal S, Topaloglu H (2008) Using stochastic approximation algorithms to compute optimal base-stock levels in inventory control problems. Oper Res 56(3): 646–664 · Zbl 1167.90337 · doi:10.1287/opre.1070.0477
[13] Kushner HJ, Clark DS (1978) Stochastic approximation methods for constrained and unconstrained systems. Springer, Berlin
[14] Lautenbacher CJ, Stidham S (1999) The underlying markov decision process in the single-leg airline yield management problem. Transp Sci 33: 136–146 · Zbl 1003.90022 · doi:10.1287/trsc.33.2.136
[15] L’Ecuyer P, Glynn P (1994) Stochastic optimization by simulation: Convergence proofs for the GI/G/1 queue in steady state. Manage Sci 40: 1245–1261 · Zbl 0822.90066 · doi:10.1287/mnsc.40.10.1245
[16] Lee T, Hersh M (1993) A model for dynamic airline seat inventory control with multiple seat bookings. Transp Sci 27: 252–265 · doi:10.1287/trsc.27.3.252
[17] Littlewood K (1972) Forecasting and control of passengers. In: Proceedings of the 12th AGIFORS, New York, pp 95–117
[18] Mahajan S, van Ryzin G (2001) Stocking retail assortments under dynamic customer substitution. Oper Res 49(3): 334–351 · Zbl 1163.90339 · doi:10.1287/opre.49.3.334.11210
[19] Robinson L (1995) Optimal and approximate control policies for airline booking with sequential nonmonotonic fare classes. Oper Res 43: 252–263 · Zbl 0832.90072 · doi:10.1287/opre.43.2.252
[20] Talluri KT, van Ryzin GJ (2004) The theory and practice of revenue management. Kluwer, Dordrecht · Zbl 1083.90024
[21] Topaloglu H (2008) A stochastic approximation method to compute bid prices in network revenue management problems. INFORMS J Comput 20(4): 596–610 · Zbl 1243.90164 · doi:10.1287/ijoc.1080.0269
[22] van Ryzin G, McGill J (2000) Revenue management without forecasting or optimization: An adaptive algorithm for determining airline seat protection levels. Manage Sci 46(6): 760–775 · Zbl 1231.90414 · doi:10.1287/mnsc.46.6.760.11936
[23] van Ryzin G, Vulcano G (2008a) Computing virtual nesting controls for network revenue management under customer choice behavior. Manuf Serv Oper Manage 10(3): 448–467 · Zbl 1167.90357 · doi:10.1287/msom.1070.0210
[24] van Ryzin G, Vulcano G (2008b) Simulation-based optimization of virtual nesting controls for network revenue management. Oper Res 56(4): 865–880 · Zbl 1167.90357 · doi:10.1287/opre.1080.0550
[25] Wollmer RD (1992) An airline seat management model for a single leg route when lower fare classes book first. Oper Res 40: 26–37 · Zbl 0825.90664 · doi:10.1287/opre.40.1.26
[26] Zinkevich M (2003) Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003). Washington, DC
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.