A Priori Optimization of the Probabilistic Traveling Salesman Problem

Gilbert Laporte, François V. Louveaux and Hélène Mercure
Additional contact information
Gilbert Laporte: École des Houtes Etudes Commerciales, Montreal, Quebec, Canada
François V. Louveaux: Notre-Dame de la Paix, Namur, Belgium
Hélène Mercure: École des Hautes Études Commerciales, Montreal, Quebec, Canada

Operations Research, 1994, vol. 42, issue 3, 543-549

Abstract: 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.

Keywords: networks/graphs; stochastic stochastic traveling salesman problem; networks/graphs; traveling salesman: stochastic traveling salesman problem (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (35)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.3.543 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:3:p:543-549

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().