An Efficient Multicore based Parallel Computing Approach for TSP Problems

TSP (Travelling Salesman Problem) is a typical problem in the scientific and business computing applications such as social network analysis, VLSI chip design, etc. However TSP is regarded as not only a combinatorial optimization problem but also a typical NP-hard problem, and becomes an important method of verifying the correctness and feasibility of new algorithms. Branch and bound algorithm is used to solve TSP because of accuracy results and efficient cutting branch strategy, which has great room for development. However, branch and bound algorithm has its own shortcomings, e. g. acceleration effect is not obvious or even failure for large-scale TSP on single core (In experiment, when the node number is greater than 13, we cannot get the result.); algorithm is more complex and has a bad effect on implementation and practical application. In this paper parallel branch and bound algorithm based on multicore has been improved and proposed to solve classic TSP for the two shortcomings. It estimates the bound by limit method according to greedy algorithm and minimum of distance matrix. The parallel algorithm draws on the implicit parallelism of branch and bound algorithm to propose a multi-branch parallel mechanism to improve the optimization efficiency. And on each core the algorithm eliminates the sub-loop to avoid repetitive calculations. Multicore solves problems of load balancing and task scheduling by collaboration of static and dynamic, integration of master core and slave core. This paper uses the Beehive 6.0 as multi-core platform to verify TSP by improved algorithm. Simulation results show that our algorithm is efficient and useful, which not only avoids the bottleneck of scale increasing on single core computer, but also improves the speed of cutting branch on multicore computer.