Computational Approaches to Stochastic Vehicle Routing Problems

We report computational test results for several graph-based a priori heuristics for the Euclidean plane versions of two well-known stochastic optimization problems, the probabilistic traveling salesman problem (PTSP) and the probabilistic (or stochastic) vehicle routing problem (PVRP). These heuristics are termed a priori because they design vehicle routes prior to realization of demands. Our tests compare the quality of such solutions to sample averages of a posteriori solutions of the deterministic realizations—the underlying TSPs and VRPs. Our results indicate that the simplest implementations give average cost performance within 5% of the latter, while the best implementations show a gap of only about 1%. Since running times are modest, we conclude that the a priori approaches offer a large potential benefit to the practitioner seeking to obtain good performance in a situation where solving repeated deterministic instances of the TSP or VRP is impractical or otherwise undesirable.