In 1985, Jaillet introduced the probabilistic traveling salesman problem (PTSP), a variant of the classical TSP in which only a subset of the nodes may be present in any given instance of the problem. The goal is to find an a priori tour of minimal expected length, with the strategy of visiting the present nodes in a particular instance in the same order as they appear in the a priori tour. In this paper the authors reexamine the PTSP using a variety of theoretical and computational approaches. They sharpen the best known bounds for the PTSP, derive several asymptotic relations, and compare from various viewpoints the PTSP with the re-optimization strategy, i.e., finding an optimal tour in every problem instance. When a Euclidean metric is used and the nodes are uniformly distributed in the unit square, a heuristic for the PTSP is shown to be very close to the re-optimization strategy. The authors examine some PTSP heuristics with provable worst-case performance, and address the question of finding constant-guarantee heuristics. Implementations of various heuristics, some based on sorting and some on local optimality, permit us to discuss the qualitative and quantitative properties of computational problems with up to 5000 nodes.
