# A probabilistic traveling salesman problem: a survey

## Abir Henchiri, Monia Bellalouna, Walid Khaznaji

DOI: http://dx.doi.org/10.15439/2014F381

Citation: Position Papers of the 2014 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 3, pages 55â€“60 (2014)

Abstract. €”The Probabilistic Traveling Salesman Problem (PTSP) is a variation of the classic Traveling Salesman Problem (TSP) in which only a subset of potential nodes needs to be visited on any given instance of the problem. The number of nodes to be visited each time is a random variable. The objective is to find an a priori tour which minimizes the expected length over all possible instances. In this paper, we survey a number of results obtained for PTSP and present the different approaches used for solving it.