A Large-scale TSP Algorithm Based on Divide-and-Conquer Method and Branch-bounding Method

The determination of large scale TSP problem has long become a headache in the field of mathematics. The divide-and-conquer method, though capable of handling large-scale problems, yet is criticized for its poor accuracy; branch-bounding method, although reliable in obtaining exact solution, yet is blamed for its high time complexity. By integrating the advantages of the two, a new effective method for solving large-scale TSP is designed through combination of the two methods. The newly designed algorithm, using clustering and convex hull technology to divide the large-scale problem layer by layer effectively, can eventually work out the optimal size fitting for the determination of solution through branch-bounding method and then obtain the optimal solution of each sub-problem and each layer’s sub-problems by branch-bounding method, and by merging these results, thus to get the solution of the whole problem. A comparative experiment reveals that: the new algorithm boasts its quality , stability and time efficiency in the determination of solutions.