Exact Approach for the Vehicle Routing Problem with Stochastic Demands and Preventive Returns

This paper considers a vehicle routing problem where the customer demands are stochastic variables. Because of uncertainty along a route, the vehicle may be unable to load all planned customers? demand. Thus, the vehicle must return to the depot, unload, and then resume its trip. To avoid unplanned return trips to the depot, one may decide to make some preventive return: Even if it is not full, the vehicle returns to the depot, unloads, and resumes its trip at the next customer. These preventive returns avoid visiting the same customer twice at the expense of possibly making an unneeded return. In this paper, the authors propose an exact procedure for designing routes to minimize the total expected cost of the routes. It consists of a branch-and-cut algorithm based on the L-shaped method for stochastic programs with binary first-stage variables. The paper provides lower bounds and cuts on the expected costs, and describes the results of computational analysis of a computer implementation on benchmark instances. Instances involving up to 100 customers have been solved to optimality.

  • Record URL:
  • Availability:
  • Supplemental Notes:
    • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
  • Authors:
    • Louveaux, François V
    • Salazar-González, Juan-José
  • Publication Date: 2018-11


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01691440
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Dec 28 2018 10:48AM