A Parallel Tsp Algorithm Based On Mapreduce Model

The TSP problem(Traveling Salesman Problem) is a famous mathematical problem in combinatorial optimization area. It has been widely studied because of their importance in academic research and actual production demand, and it has been widely applied in various areas such as physics, biology, computer science and so on in recent years. As one of the most challenging NP-hard problems, at present, most of TSP algorithms are sequential executed on a single physical machine to obtain approximate solutions, and there is also some research using MapReduce model to solve TSP problem on Hadoop platform, such as genetic algorithms and ant colony algorithms, while as the shortcomes, the quality and stability are unsured. These aspects can be carried out in-depth research and it’s meaningful to make some improvements. This thesis explores effective solutions to solve TSP problem through parallel MapReduce model.This thesis firstly proposes several parallel methods for solving TSP problem based on MapReduce model: Firstly, proposing a parallelized minimum spanning tree algorithm(PMST) based on the MapReduce model, which makes full use of MapReduce model that has the characteristic of making data sorted. So we can obtain a MST with parallelized Kruskal algorithm. Then the PMST is applied as inputs to Christofides algorithm, one of the best approximation algorithms with the approximate ratio of 1.5-opt, to obtain an initial solution of TSP tour. Afterwards, this thesis presents a K-OPT algorithm based on the MapReduce model in which the map function is used to read and analyze the tour distribution, and reduce function is used to solve the problem. The approach is to overview thoroughly multi-node cluster nodes to obtain the optimal solution, and the optimal solution will be used in the next iteration as input; In the next step, based on intensive statistical analysis and generation of probability distribution of TSP tours by MapReduce, we introduce a Truncated Generalized Beta distribution(TGB) as the probability density function of all tours in a TSP for the first time, and propose an iterative TGB approach to obtain quality-proved near optimal approximation.Finally, we validate proposed methods by intensive real data tests.