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. We address the question of whether and in which context an a priori tour found by a TSP heuristic can also be a good solution for the PTSP. We answer this question by testing the relative performance of two ant colony optimization algorithms, Ant Colony System (ACS) introduced by Dorigo and Gambardella for the TSP, and a variant of it (pACS) which aims to minimize the PTSP objective function. We show in which probability configuration of customers pACS and ACS are promising algorithms for the PTSP.
Bianchi et al. REF introduced the ACO for a different version of the TSP, the probabilistic TSP, where each customer has a given probability of requiring a visit.
An ant colony optimization approach to the probabilistic traveling salesman problem
Proceedings of the 7th International Conference on Parallel Problem Solving from Nature (PPSN VII
Computer Science