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.