A Vehicle Routing Problem with Stochastic Demand

Dimitris J. Bertsimas
Additional contact information
Dimitris J. Bertsimas: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1992, vol. 40, issue 3, 574-585

Abstract: We consider a natural probabilistic variation of the classical vehicle routing problem (VRP), in which demands are stochastic. Given only a probabilistic description of the demand we need to design routes for the VRP. Motivated by applications in strategic planning and distribution systems, rather than resolving the problem when the demand becomes known, we propose to construct an a priori sequence among all customers of minimal expected total length. We analyze the problem using a variety of theoretical approaches. We find closed-form expressions and algorithms to compute the expected length of an a priori sequence under general probabilistic assumptions. Based on these expressions we find upper and lower bounds for the probabilistic VRP and the VRP re-optimization strategy, in which we find the optimal route at every instance. We propose heuristics and analyze their worst case performance as well as their average behavior using techniques from probabilistic analysis. Our results suggest that our approach is a strong and useful alternative to the strategy of re-optimization in capacitated routing problems.

Keywords: networks/graphs: stochastic applications; probability: stochastic model applications; transportation; vehicle routing: stochastic vehicle routing (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (77)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.3.574 (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:oropre:v:40:y:1992:i:3:p:574-585

Access Statistics for this article

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