Approximate Dynamic Programming and Stochastic Approximation Methods for Inventory Control and Revenue Management

摘要

In this thesis, we develop approximate dynamic programming and stochastic approximation methods for problems in inventory control and revenue management. A unifying feature of the methods we develop is that they exploit the underlying problem structure. By doing so, we are able toestablish certain theoretical properties of our methods, make them more computationally efficient and obtain a faster rate ofconvergence.In the stochastic approximation framework, we develop an algorithm for the monotone estimation problem that uses a projection operator with respect to the max norm onto the order simplex. We show the almost sure convergence of this algorithm and present applications to the Q-learning algorithm and the newsvendor problem with censored demands. Next, we consider a number of inventory control problems for which the so-called base-stock policies are known to beoptimal. We propose stochastic approximation methods to compute the optimal base-stock levels. Existing methods in the literature have only local convergence guarantees. In contrast, we show that the iterates of our methods converge to base-stock levels that are globally optimal. Finally, we consider the revenue managementproblem of optimally allocating seats on a single flight leg todemands from multiple fare classes that arrive sequentially. Wepropose a stochastic approximation algorithm to compute the optimalprotection levels. The novel aspect of our method is that it workswith the nonsmooth version of the problem where capacity can only beallocated in integer quantities. We show that the iterates of ouralgorithm converge to the globally optimal protection levels.In the approximate dynamic programming framework, we use aLagrangian relaxation strategy to make the inventory controldecisions in a distribution system consisting of multiple retailersthat face random demand and a warehouse that supplies the retailers.Our method is based on relaxing the constraints that ensure thenonnegativity of the shipments to the retailers by associatingLagrange multipliers to them. We show that our method naturallyprovides a lower bound on the optimal objective value. Furthermore,a good set of Lagrange multipliers can be obtained bysolving a convex optimization problem.