Stochastic Vehicle Routing Problem with Restocking

In this paper, a stochastic vehicle routing problem is considered. In particular, customer demand is assumed to be uncertain, and actual demand is revealed only upon the visit to the customer. Instead of adopting the simple recourse action of returning to the depot whenever the vehicle runs out of stock, the points along the route at which restocking is to occur are designed into the route. The restocking points may be before a stockout actually occurs. Two heuristic algorithms are developed to construct both single and multiple routes that minimize total travel cost. The computational results show that the heuristic procedures produce quality solutions and are efficient.