An Exact Resolution for the Probabilistic Traveling Salesman Problem under the A Priori Strategy

The Probabilistic Traveling Salesman Problem (PTSP) is an extension of the classical Traveling Salesman Problem (TSP). The main difference is the stochastic presence of the customers, that is, the number of them to be visited each time is a random variable, where each customer associates with a given probability of occurrence. The resolution of problem consists in finding an a priori tour visiting all customers which minimizes the expected length over all possibilities. In this paper, we propose an exact algorithm for the solution of the PTSP. In this context, we derive new expressions for the lower bound and transitional, permanent evaluations as well as the mechanism of separation. The numerical results demonstrate the advantage of the proposed evaluations. (C) 2017 The Authors. Published by Elsevier B.V. Peer-review under responsibility of the scientific committee of the International Conference on Computational Science