مشخصات پژوهش

عنوان	A New Approximation Algorithm for the Symmetric Traveling Salesman Problem
نوع پژوهش	مقاله ارائه شده کنفرانسی
کلیدواژه‌ها	Traveling Salesman Problem, Approximation Algorithm, Approximate Solution, Greedy Algorithm, 2-Opt Algorithm, Network Optimization
چکیده	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.
پژوهشگران	محسن عبدالحسین زاده (نفر اول)، میرمحمد علیپور (Mir Mohammad Alipour) (نفر دوم)، مهدی جهانگیری (نفر سوم)