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

سال انتشار: 1391
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 1,605

فایل این مقاله در 5 صفحه با فرمت PDF قابل دریافت می باشد

این مقاله در بخشهای موضوعی زیر دسته بندی شده است:

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

LNCSE02_097

تاریخ نمایه سازی: 6 اسفند 1391

چکیده مقاله:

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

کلیدواژه ها:

Traveling salesman problem (TSP) – Artificial Intelligence- Finding optimum sub paths - Matrix segmentation algorithm(MSA) - optimal path - Algorithms

نویسندگان

Yaghoob Azizi

Electrical Engineering Department, Amirkabir University

Mohammad Bagher Menhaj

Electrical Engineering Department, Amirkabir University