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

سال انتشار: 1391
محل انتشار: دومین کنفرانس ملی مهندسی نرم افزار دانشگاه آزاد لاهیجان
کد COI اختصاصی: LNCSE02_097
زبان مقاله: انگلیسی
تعداد مشاهده: 1618

نویسندگان

Electrical Engineering Department, Amirkabir University

چکیده

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

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.