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