An adaptive dynamic programming algorithm for a stochastic multiproduct batch dispatch problem

Katerina P. Papadaki, Warren Buckler Powell

Research output: Contribution to journalArticle

30 Scopus citations

Abstract

We address the problem of dispatching a vehicle with different product classes. There is a common dispatch cost, but holding costs that vary by product class. The problem exhibits multidimensional state, outcome and action spaces, and as a result is computationally intractable using either discrete dynamic programming methods, or even as a deterministic integer program. We prove a key structural property for the decision function, and exploit this property in the development of continuous value function approximations that form the basis of an approximate dispatch rule. Comparisons on single product-class problems, where optimal solutions are available, demonstrate solutions that are within a few percent of optimal. The algorithm is then applied to a problem with 100 product classes, and comparisons against a carefully tuned myopic heuristic demonstrate significant improvements.

Original languageEnglish (US)
Pages (from-to)742-769
Number of pages28
JournalNaval Research Logistics
Volume50
Issue number7
DOIs
StatePublished - Oct 1 2003

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'An adaptive dynamic programming algorithm for a stochastic multiproduct batch dispatch problem'. Together they form a unique fingerprint.

  • Cite this