ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Travelling Salesman Problem Based on Area Division and Connection Method

Journal: The Journal of the Institute of Internet, Broadcasting and Communication (Vol.15, No. 3)

Publication Date:

Authors : ;

Page : 211-218

Keywords : Travelling salesman problem; Exhaustive search method; Edge exchange method; Divide-and-conquer method; Data reduction;

Source : Downloadexternal Find it from : Google Scholarexternal


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 .

Last modified: 2015-11-20 17:50:47