×

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.

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