Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 3

Position Papers of the 2014 Federated Conference on Computer Science and Information Systems

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)

Full text

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.