Deliveries in an Inventory/Routing Problem Using Stochastic Dynamic Programming

Dick Larson
Professor of Electrical Engineering
Director, Center for Advanced Educational Services
MIT

Motivated by an implemented industrial gases application, n customers are visited on a tour, with a possible n+1st customer added at the end. The amount of needed product at each customer is a known random process, typically a Wiener process. The objective is to adjust dynamically the amount of product provided on scene to each customer so as to minimize total expected costs, comprising costs of "earliness," lateness, product shortfall and returning to the depot non-empty. Earliness costs are computed by invocation of an annualized incremental cost argument. Amounts of product delivered to each customer are not known until the driver is on scene at the customer location, at which point the customer is either restocked to capacity or left with some residual empty capacity, the policy determined by stochastic dynamic programming. The methodology has applications beyond industrial gasses.