Laporte, Gilbert; Louveaux, François V.; Mercure, Hélène A priori optimization of the probabilistic traveling salesman problem. (English) Zbl 0810.90124 Oper. Res. 42, No. 3, 543-549 (1994). 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. Cited in 41 Documents MSC: 90C35 Programming involving graphs or networks 90C15 Stochastic programming 90C10 Integer programming Keywords:probabilistic traveling salesman; integer linear stochastic program; branch-and-cut PDFBibTeX XMLCite \textit{G. Laporte} et al., Oper. Res. 42, No. 3, 543--549 (1994; Zbl 0810.90124) Full Text: DOI