Back to the program.
The Probabilistic Traveling Salesman Problem, an ant colony approach
Leonora Bianchi
IDSIA;; Lugano, Switzerland
On 2002-04-23 at 15:00:00 (Brussels Time)

Abstract

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 function.

Keywords

traveling salesman problem, stochastic optimization problems, ant colony optimization.

References

  1. D. Bertsimas, P. Chervi, and M. Peterson. (1995) Computational Approaches to Stochastic Vehicle Routing Problems, Transportation Sciences, 29(4):342-352.
  2. D. Bertsimas, P. Jaillet, and A. Odoni. (1990) A priori optimization, Operation Research, 38:1019-1033.
  3. M. Gendreau, G. Laporte, and R. Séguin. (1996) Stochastic Vehicle Routing, European Journal of Operation Research, 88:3-12.
  4. D. Bertsimas and L. Howell. (1993) Further results on the probabilistic traveling salesman problem, European Journal of Operation Research, 65:68-95.