A New Approximation Algorithm for the Symmetric Traveling Salesman Problem

Traveling salesman problem is an NP-hard problem, and theproblem to find a good approximate solution has beendiscussed among researchers. It is considered to evaluate theperformance of the proposed algorithms to solve such a hardproblem. The arc cost parameters satisfy the triangleinequality and the forward cost value equals to the backwardcost, so it is known as the symmetric traveling salesmanproblem. The triangle inequality is an essential assumptionto find an approximate solution by a polynomial timealgorithm, while in the general form it is APX-hard. So, withrespect to the ۲-Opt algorithm there is not any cross arcs inthe optimal solution, then we consider some nested bordersof the nodes surrounding all the nodes, and they areiteratively located in the obtained approximate tour. A greedyalgorithm is applied to locate the nodes with minimumincrease in the current tour length in every iteration. Thenumerical results show the proposed method could producea good approximate solution as nearby as optimal solution.

کلیدواژه ها:

Traveling Salesman Problem ، Approximation Algorithm ، Approximate Solution ، Greedy Algorithm ، ۲-Opt Algorithm ، Network Optimization.