A vehicle routing problem with stochastic demand

A vehicle routing problem with stochastic demand

0.00 Avg rating0 Votes
Article ID: iaor1993267
Country: United States
Volume: 40
Issue: 3
Start Page Number: 574
End Page Number: 585
Publication Date: May 1992
Journal: Operations Research
Authors:
Keywords: networks: path, stochastic processes, vehicle routing & scheduling
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.

Reviews

Required fields are marked *. Your email address will not be published.