×

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.

MSC:

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