A-PRIORI OPTIMIZATION OF THE PROBABILISTIC TRAVELING SALESMAN PROBLEM
成果类型：
Article
署名作者：
LAPORTE, G; LOUVEAUX, FV; MERCURE, H
署名单位：
Universite de Montreal; HEC Montreal
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.42.3.543
发表日期：
1994
页码：
543-549
关键词：
摘要：
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.