An application and Parallel Tabu Search Algorithm for Solving the PTSP Under the OpenMP-MPI Environment

Abstract

<div>This paper reviews some real-world problems modeling</div><div>as Probabilistic Traveling Salesman Problem (PTSP), by</div><div>presenting the important results found in the literature. It</div><div>illustrates the usefulness of the inclusion of probabilistic elements in deterministic models. We propose a new modeling of the PTSP by the deviations of the routing of a robot in order to avoid obstacles which are not foreseen in its path. The Probabilistic Traveling Salesman Problem(PTSP) is a variation of the classic Traveling Salesman Problem (TSP) where each node i is present</div><div>with probability pi. The solution for the PTSP consists in finding an a priori tour that visits all the cities that minimizes the expected length of the tour. From the litterateur the PTSP is NP-Complete, therefore the execution time is a prime factor in its resolution. In the last of his paper we present a new parallel Tabu search heuristic for solving PTSP by using the Open MPI environment.</div>