The authors 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 heuritics are termed a priori because they design vehicle routes prior to realization of demands. The present tests compare the quality of such solutions to sample averages of a posteriori solutions of the deterministic realizations-the underlying TSPs and VRPs. The results indicate that the simplest implementations show a gap of only about 1%. Since running times are modest, the authors 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.
