zbMATH — the first resource for mathematics

Computational approaches to stochastic vehicle routing problems. (English) Zbl 0853.90037
Summary: We report computational test results for several graph-based a priori heuristics for the Euclidean plane versions of true 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.

90B06 Transportation, logistics and supply chain management
90C15 Stochastic programming
90C90 Applications of mathematical programming
Full Text: DOI