The Price-Directed Approach to Approximate Dynamic Programming: Application to Inventory Routing

Friday, September 27, 2002 - 1:30pm - 2:20pm
Keller 3-180
Dan Adelman (University of Chicago)
In recent years there has been growing interest in approximate dynamic programming techniques for solving operational problems in the supply chain that are not amenable to traditional lines of analysis. Attention thus far has focused on devising rigorous simulation-based methods for adaptively computing value function approximations.

We will present a different, complementary approach to approximate dynamic programming, which we call price-directed control, that computes value function approximations directly using optimal dual prices of math programming models. These models are tractable relaxations of the underlying control problem. The resulting approximations are not subject to randomness and simulation error, and thus have more stable convergence properties. They also yield a bound against which the performance of any policy, including the price-directed policy, can be compared to obtain a guarantee relative to an optimal policy. Furthermore, duality theory can be exploited to discover economic and structural properties potentially useful to managers. However, the resulting models still can be challenging to solve, so there is opportunity for researchers to devise new computational techniques and paradigms in conjunction with new applications of the technique.

This talk will be a detailed case study on how to apply this approach in the context of inventory routing, which remains one of the most important unsolved problems in the supply chain.