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.