Dimitris Bertsimas1, Philippe Chervi2, Michael D. Peterson3
1Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
2Service Technique des Systèmes Navals, 75015 Paris, France
3School of Public and Environmental Affairs, Indiana University, Bloomington, Indiana, 47405
Tóm tắt
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.
