AN EXACT ALGORITHM FOR THE VEHICLE-ROUTING PROBLEM WITH STOCHASTIC DEMANDS AND CUSTOMERS

In this article, the following stochastic vehicle routing problem is c onsidered. Each customer has a known probability of presence and a ran dom demand. This problem arises in several contexts, e.g., in the desi gn of less-than-truckload collection, routes. Because of uncertainty, it may not be possible to follow vehicle routes as planned. Using a st ochastic programming framework, the problem is solved in two stages. I n a first stage, planned collection routes are designed. In a second s tage, when the set of present customers is known, these routes are fol lowed as planned by skipping the absent customers. Whenever the vehicl e capacity is attained or exceeded the vehicle returns to the depot an d resumes its collections along the planned route. This generates a pe nalty. The problem is to design a first stage solution in order to min imize the expected total cost of the second state solution. This is fo rmulated as a stochastic integer program, and solved for the first tim e to optimality by means of an integer L-shaped method.