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

Abstract

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 to establish certain theoretical properties of our methods, make them more computationally efficient and obtain a faster rate of convergence.

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 be optimal. 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 management problem of optimally allocating seats on a single flight leg to demands from multiple fare classes that arrive sequentially. We propose a stochastic approximation algorithm to compute the optimal protection levels. The novel aspect of our method is that it works with the nonsmooth version of the problem where capacity can only be allocated in integer quantities. We show that the iterates of our algorithm converge to the globally optimal protection levels.

In the approximate dynamic programming framework, we use a Lagrangian relaxation strategy to make the inventory control decisions in a distribution system consisting of multiple retailers that face random demand and a warehouse that supplies the retailers. Our method is based on relaxing the constraints that ensure the nonnegativity of the shipments to the retailers by associating Lagrange multipliers to them. We show that our method naturally provides a lower bound on the optimal objective value. Furthermore, a good set of Lagrange multipliers can be obtained by solving a convex optimization problem.