Mir Mohammad Alipour

Traveling salesman problem is an NP-hard problem, and the problem to find a good approximate solution has been discussed among researchers. It is considered to evaluate the performance of the proposed algorithms to solve such a hard problem. The arc cost parameters satisfy the triangle inequality and the forward cost value equals to the backward cost, so it is known as the symmetric traveling salesman problem. The triangle inequality is an essential assumption to find an approximate solution by a polynomial time algorithm, while in the general form it is APX-hard. So, with respect to the 2-Opt algorithm there is not any cross arcs in the optimal solution, then we consider some nested borders of the nodes surrounding all the nodes, and they are iteratively located in the obtained approximate tour. A greedy algorithm is applied to locate the nodes with minimum increase in the current tour length in every iteration. The numerical results show the proposed method could produce a good approximate solution as nearby as optimal solution.