zbMATH — the first resource for mathematics

A priori optimization of the probabilistic traveling salesman problem. (English) Zbl 0810.90124
Summary: 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.

90C35 Programming involving graphs or networks
90C15 Stochastic programming
90C10 Integer programming
Full Text: DOI