A Partitioning Algorithm Based on Exact Resolution to Solve Big Data PTSP

The majority of the applications related to the Probabilistic Traveling Salesman Problem (PTSP) bring us big data. It is a probabilistic version of the classical Traveling Salesman Problem TSP where the number of customers to be served is unknown in advance. Today we are confronted with a big number of data in particular in applications of wireless sensor network. It was noted from the results obtained and also in the literature for the PTSP resolution, that the computation time remains high, especially when the number of data becomes significant. In this context we implemented our versions of the Karp partitioning algorithm. First, we designed and implemented a hybrid algorithm, using both an exact algorithm and Karp partitioning for the resolution of the sub-problems resulting from the partitioning algorithm. Then we combined the latter with Tabu Search. The experiment results obtained have shown that the proposed algorithm is a powerful tool for finding good solutions in real time.