Divide and conquer strategies for parallel TSP heuristics

The aim of this paper is to study experimentally divide and conquer strategies, used to implement parallel heuristics for the geometric Traveling Salesman Problem (TSP). Starting from Karp’s results the paper subdivides the set of cities into smaller sets, and it computes an optimal subtour for each subset. These subtours are then combined to obtain the tour for the entire problem. The analysis is restricted to problem instances where points are uniformly distributed in the unit square. For relatively small sets of cities the paper studies the quality of the solution by comparing it with the optimal solution. In large problem-instances, statistical estimates of the optimal solutions are used for asymptotical analysis. The paper applies the same dissection strategy also to classical heuristics: the final solution, obtained by combining the approximate subsolutions, is compared with the average quality of the heuristic. The present main result is the estimate of the rate of convergence of the approximate solution to the optimal solution as a function of the number of dissection steps, of the criterion used for the plane division and of the quality of the subtours. The paper has implemented the programs on Mulit Signal process or system with Intelligent Communication a Single-Program-Multiple-Data parallel computer with distributed memory, which has been developed at the ETH Zurich.