A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited

Consider a problem of routing through a set of n points. On any given instance of the problem, only a subset consisting of k out of n points (0 ≤ k ≤ n) has to be visited, with the number k random with known probability distribution. We wish to find a priori a tour through all n points. On any given instance, the k points present will then be visited in the same order as they appear in the a priori tour. The problem of finding such a tour of minimum length in the expected value sense is defined as a Probabilistic Traveling Salesman Problem (PTSP). What distinguishes one PTSP from another is the probability distribution (or more generally, the probability “law”) that specifies the number k and the identity of the points that need to be visited on any given instance of the problem. After motivating the problem by applications, we first derive closed form expressions for computing efficiently the expected length of any given tour under very general probabilistic assumptions. We then provide, in a unified way, an analysis of these expressions and derive several interesting properties of the problem.