Travelling Salesman Problem Based on Area Division and Connection Method

This paper introduces a ‘divide-and-conquer’ algorithm to the travelling salesman problem (TSP). Top are selected beforehand from a pool of data which are sorted in the ascending order of each vertex’s distance. The proposed algorithm then firstly selects partial paths that are interconnected with the shortest distance of each vertex and assigns them as individual regions. For , it connects all inter-vertex edges within the region and inter-region edges are connected in accordance with the connection rule. Finally for , it connects only inter-region edges until one whole Hamiltonian cycle is constructed. When tested on TSP-1() and TSP-2() of real cities and on a randomly constructed TSP-3() of the Euclidean plane, the algorithm has obtained optimal solutions for the first two and an improved one from that of Valenzuela and Jones for the third. In contrast to the brute-force search algorithm which runs in , the proposed algorithm runs at most times, with the time complexity of .