This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Adelman, D. Search for Related Content

A Price-Directed Approach to Stochastic Inventory/Routing

Graduate School of Business, The University of Chicago, Chicago, Illinois 60637
dan.adelman{at}gsb.uchicago.edu

We consider a new approach to stochastic inventory/routing that approximates the future costs of current actions using optimal dual prices of a linear program. We obtain two such linear programs by formulating the control problem as a Markov decision process and then replacing the optimal value function with the sum of single-customer inventory value functions. The resulting approximation yields statewise lower bounds on optimal infinite-horizon discounted costs. We present a linear program that takes into account inventory dynamics and economics in allocating transportation costs for stochastic inventory routing. On test instances we find that these allocations do not introduce any error in the value function approximations relative to the best approximations that can be achieved without them. Also, unlike other approaches, we do not restrict the set of allowable vehicle itineraries in any way. Instead, we develop an efficient algorithm to both generate and eliminate itineraries during solution of the linear programs and control policy. In simulation experiments, the price-directed policy outperforms other policies from the literature.

Subject classifications: dynamic programming/optimal control; discounted infinite-horizon; separable functional approximations; transportation; inventory routing; stochastic; inventory/production; multi-item; stochastic.
History: Received November 2001; revision received August 2002; revision received July 2003; accepted July 2003.

This article has been cited by other articles:

				L. M. Hvattum, A. Lokketangen, and G. Laporte Scenario Tree-Based Heuristics for Stochastic Inventory-Routing Problems INFORMS Journal on Computing, April 1, 2009; 21(2): 268 - 285. [Abstract] [PDF]

				N. Secomandi and F. Margot Reoptimization Approaches for the Vehicle-Routing Problem with Stochastic Demands Operations Research, January 1, 2009; 57(1): 214 - 230. [Abstract] [PDF]

				J. Patrick, M. L. Puterman, and M. Queyranne Dynamic Multipriority Patient Scheduling for a Diagnostic Resource Operations Research, November 1, 2008; 56(6): 1507 - 1525. [Abstract] [PDF]

				J. W. Ohlmann, M. J. Fry, and B. W. Thomas Route Design for Lean Production Systems Transportation Science, August 1, 2008; 42(3): 352 - 370. [Abstract] [PDF]

				D. Adelman and A. J. Mersereau Relaxations of Weakly Coupled Stochastic Dynamic Programs Operations Research, May 1, 2008; 56(3): 712 - 727. [Abstract] [PDF]

				D. Adelman Price-Directed Control of a Closed Logistics Queueing Network Operations Research, November 1, 2007; 55(6): 1022 - 1038. [Abstract] [PDF]

				C. Archetti, L. Bertazzi, G. Laporte, and M. G. Speranza A Branch-and-Cut Algorithm for a Vendor-Managed Inventory-Routing Problem Transportation Science, August 1, 2007; 41(3): 382 - 391. [Abstract] [PDF]

				J.-H. Song and M. Savelsbergh Performance Measurement for Inventory Routing Transportation Science, February 1, 2007; 41(1): 44 - 54. [Abstract] [PDF]

				D. P. de Farias and B. Van Roy A Cost-Shaping Linear Program for Average-Cost Approximate Dynamic Programming with Performance Guarantees Mathematics of Operations Research, August 1, 2006; 31(3): 597 - 620. [Abstract] [PDF]

				S. Ichoua, M. Gendreau, and J.-Y. Potvin Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching Transportation Science, May 1, 2006; 40(2): 211 - 225. [Abstract] [PDF]