A Parallel Branch and Bound Algorithm for the Probabilistic TSP

The paper presents parallelization of exact algorithm of resolution for the Probabilistic Traveling Salesman Problem (PTSP). This algorithm allows us, first, to verify the stability of well-solvable special cases and also to optimally solve useful instances of PTSP. It again allows to perform our version of Karp partitioning algorithm, where real problems are very large-sized. The implementation of the algorithm of Karp consists in subdividing the square plan, into sub-plans. So we transform the resolution of a large size problem to the resolution of many small size sub-problems which can be exactly solved. This application can be gridified and these different sub-problems would be processed in parallel by different nodes since they are totally independent. In each sub-plan the Branch and Bound algorithm is used. In this paper we propose two parallelizations of the Branch and Bound algorithm for the resolution of the PTSP. On the one hand, the parallelization of the branches used in the exploration of the tree, on the other hand the parallelization of the algorithm associated with the notion of partitioning introduced by Karp. We perform an experimental study conducted in a multi-core environment to evaluate the performance of the proposed approach.