Stochastic vehicle routing with modified savings algorithm

A stochastic vehicle routing problem (SVRP) differs from the well known vehicle routing problem (VRP) in that the actual customer demand is not known with certainty when the vehicle routes are designed. One aspect that differentiates between these problems is the notion of route failure. Route failure indicates a situation where a vehicle cannot complete all the deliveries on a designed route because its supply is exhausted at some point along the route, before the route's demand is fully satisfied. In this paper, we illustrate the effects of route failure on the expected cost of a route, as well as the impact the direction of a designed route can have on the expected cost. In addition, we present a straight-forward modification of the Clark and Wright savings algorithm to account more fully for all the costs inherent in many real routing problems, where the customers actual demands are uncertain.