Confidence intervals for the optimum of the Probabilistic Traveling Salesman Problem

The Probabilistic Traveling Salesman Problem (PTSP) is a generalization of the Traveling Salesman Problem. In the PTSP the structure of the graph is known, whereas which and how many nodes of the graph must be visited (active nodes) at each new exit of the traveling salesman are not known. The problem to be solved is finding and evaluating the hamiltonian route with the shortest expected length. Efficient algorithms to calcuate the optimum PTSP are not available, even if the number of the nodes is not so large. The existing heuristic algorithms are computationally complex and the degree of accuracy of their solutions is unknown. In the present work some probabilistic methods are treated and a procedure to determine confidence intervals and lower bounds to the optimum PTSP is proposed. This procedure is applied to an heuristic algorithm derived from Clarke-Wright’s one, in order to verify its degree of accuracy. Computational tests are performed in graphs with up to 100 nodes and show that the above mentioned heuristic algorithm is accurate.