A-PRIORI OPTIMIZATION OF THE PROBABILISTIC TRAVELING SALESMAN PROBLEM

The probabilistic traveling salesman problem (PTSP) is defined on a graph G = (V, E), where V is the vertex set and E is the edge set. Each vertex v(i) has a probability p(i) of being present. With each edge (v(i), v(j)) is associated a distance or cost c(ij). In a first stage, an a priori Hamiltonian tour on G is designed. The list of present vertices is then revealed. In a second stage, the a priori tour is followed by skipping the absent vertices. The PTSP consists of determining a first-stage solution that minimizes the expected cost of the second-stage tour. The problem is formulated as an integer linear stochastic program, and solved by means of a branch-and-cut approach which relaxes some of the constraints and uses lower bounding functionals on the objective function. Problems involving up to 50 vertices are solved to optimality.