Gendreau, Michel; Laporte, Gilbert; Séguin, René An exact algorithm for the vehicle routing problem with stochastic demands and customers. (English) Zbl 0860.90051 Transp. Sci. 29, No. 2, 143-155 (1995). Summary: The following stochastic vehicle routing problem is considered. Each customer has a known probability of presence and a random demand. This problem arises in several contexts, e.g., in the design of less-than-truckload collection routes. Because of uncertainty, it may not be possible to follow vehicle routes as planned. Using a stochastic programming framework, the problem is solved in two stages. In a first stage, planned collection routes are designed. In a second stage, when the set of present customers is known, these routes are followed as planned by skipping the absent customers. Whenever the vehicle capacity is attained or exceeded, the vehicle returns to the depot and resumes its collections along the planned route. This generates a penalty. The problem is to design a first stage solution in order to minimize the expected total cost of the second state solution. This is formulated as a stochastic integer program, and solved for the first time to optimality by means of an integer \(L\)-shaped method. Cited in 61 Documents MSC: 90B06 Transportation, logistics and supply chain management 90C15 Stochastic programming 93E03 Stochastic systems in control theory (general) 90C10 Integer programming Keywords:stochastic vehicle routing; less-than-truckload collection routes; stochastic integer program PDFBibTeX XMLCite \textit{M. Gendreau} et al., Transp. Sci. 29, No. 2, 143--155 (1995; Zbl 0860.90051) Full Text: DOI