An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers

Michel Gendreau, Gilbert Laporte and René Séguin
Additional contact information
Michel Gendreau: Centre de recherche sur les transports, Université de Montréal, Montréal, Québec, Canada H3C 3J7
Gilbert Laporte: Centre de recherche sur les transports, Université de Montréal, Montréal, Québec, Canada H3C 3J7
René Séguin: Centre de recherche sur les transports, Université de Montréal, Montréal, Québec, Canada H3C 3J7

Transportation Science, 1995, vol. 29, issue 2, 143-155

Abstract: In this article, 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.

Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (61)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.29.2.143 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:29:y:1995:i:2:p:143-155

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().