A stochastic inventory routing problem with stock-out

In this paper, we study an inventory routing problem in which a supplier has to serve a set of retailers. For each retailer, a maximum inventory level is defined and a stochastic demand has to be satisfied over a given time horizon. An order-up-to level policy is applied to each retailer, i.e. the quantity sent to each retailer is such that its inventory level reaches the maximum level whenever the retailer is served. An inventory cost is applied to any positive inventory level, while a penalty cost is charged and the excess demand is not back-logged whenever the inventory level is negative. The problem is to determine a shipping strategy that minimizes the expected total cost, given by the sum of the expected total inventory and penalty cost at the retailers and of the expected routing cost. A hybrid rollout algorithm is proposed for the solution of the problem and its performance is evaluated on a large set of randomly generated problem instances. (C) 2011 Elsevier Ltd. All rights reserved.