A new approach for solving travelling salesman problem by finding optimum sub paths based on matrix segmentation

This paper describes a novel algorithm (MSA) that finds many optimum links belonging the main optimum path in a travelling salesman problem, in a short period of time. This procedurereceives travelling salesman problem in a square matrix form with n nodes. In the first step, this matrix is segmented into 4*4 submatrices. Each of these 4*4 sub matrices is considered as a large node and the problem is changed to a network with n/4 largernodes. Using a mathematical-probabilistic procedure, the shortest link in any sub matrix is found and then the minimum one betweenthem is selected. This selected link is viewed as a part of the mainoptimal path and it could not be selected anymore. This algorithm will run until all links of the main optimum path are found, and it repeats so as to find a specified number of Hamiltonian paths. This procedure is capable of solving symmetric and asymmetric TSPs.Experiments have shown that this procedure can find almost %65.9 of the optimum links as an average, just in the preliminary iterations. This procedure (MSA) has applied more than 40 times to bays29, fri26, gr24, gr48, p43, eli51, br17 and many optimum links hasextracted from them. In average, any changes in the dimension of sub matrices not only haven't improved the results but alsoworsened them. The better results appeared only in one case. More than 5 iterations haven't made any improvements in the results. Using this algorithm, several optimum parts of the main optimum path can be found without solving the problem completely