Convergence Results for Vehicle Routing Problems with Stochastic Demands

DOI: 10.5176/2251-1938_ORS13.08

Authors: D. Weyland, R. Montemanni, L.M. Gambardella

Abstract:

In this work we investigate two variants of the Stochastic Vehicle Routing Problem: The Vehicle Routing Prob- lem with Stochastic Demands and the Vehicle Routing Problem with Stochastic Demands and Customers. We show that under some moderate conditions there is an asymptotic equivalence between the Vehicle Routing Problem with Stochastic Demands and the Traveling Salesman Problem, as well as between the Vehicle Routing Problem with Stochastic Demands and Cus- tomers and the Probabilistic Traveling Salesman Problem. Based on our results we give explanations for different observations in literature and we provide ideas for the development of new approximation algorithms and heuristics for these problems.

Keywords: stochastic combinatorial optimization, vehicle routing, stochastic demands, markov process, convergence