The Probabilistic Traveling Salesman Problem (PTSP) is a TSP problem
where each customer has a given probability of requiring a visit. The
goal is to find an a-priori tour of minimal expected length over all
customers, with the strategy of visiting a random subset of customers in
the same order as they appear in the a-priori tour. The PTSP may be seen
as a "simple" version of a vehicle routing problem with stochastic
demands, where there is one vehicle and where the demand may either zero
(the customer does not require a visit) or one (the customer requires a
visit). An important question about this problem is whether and in which
context an a-priori tour found by a TSP heuristic can also be a good
solution for the PTSP. We investigate this issue by experimentally
testing the relative performance of two ant colony optimization
algorithms, Ant Colony System (ACS) which is a TSP heuristic, and a
variant of it (pACS) that aims to minimize the PTSP objective
traveling salesman problem, stochastic optimization problems,
ant colony optimization.
D. Bertsimas, P. Chervi, and M. Peterson. (1995)
Computational Approaches to Stochastic Vehicle Routing Problems,
Transportation Sciences, 29(4):342-352.
D. Bertsimas, P. Jaillet, and A. Odoni. (1990)
A priori optimization,
Operation Research, 38:1019-1033.
M. Gendreau, G. Laporte, and R. Séguin. (1996)
Stochastic Vehicle Routing,
European Journal of Operation Research, 88:3-12.
D. Bertsimas and L. Howell. (1993)
Further results on the probabilistic traveling salesman problem,
European Journal of Operation Research, 65:68-95.