Publisher of Iranian Journals and Conference Proceedings

Please waite ..
Publisher of Iranian Journals and Conference Proceedings
Login |Register |Help |عضویت کتابخانه ها
Paper
Title

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

Year: 1391
COI: LNCSE02_097
Language: EnglishView: 1,467
This Paper With 5 Page And PDF Format Ready To Download

Buy and Download

با استفاده از پرداخت اینترنتی بسیار سریع و ساده می توانید اصل این Paper را که دارای 5 صفحه است به صورت فایل PDF در اختیار داشته باشید.
آدرس ایمیل خود را در کادر زیر وارد نمایید:

Authors

Yaghoob Azizi - Electrical Engineering Department, Amirkabir University
Mohammad Bagher Menhaj - Electrical Engineering Department, Amirkabir University

Abstract:

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

Keywords:

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

Paper COI Code

This Paper COI Code is LNCSE02_097. Also You can use the following address to link to this article. This link is permanent and is used as an article registration confirmation in the Civilica reference:

https://civilica.com/doc/184856/

How to Cite to This Paper:

If you want to refer to this Paper in your research work, you can simply use the following phrase in the resources section:
Azizi, Yaghoob and Menhaj, Mohammad Bagher,1391,A new approach for solving travelling salesman problem by finding optimum sub paths based on matrix segmentation,2nd Lahijan National Conference on Software Engeering,Lahijan,https://civilica.com/doc/184856

Research Info Management

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

اطلاعات استنادی این Paper را به نرم افزارهای مدیریت اطلاعات علمی و استنادی ارسال نمایید و در تحقیقات خود از آن استفاده نمایید.

Scientometrics

The specifications of the publisher center of this Paper are as follows:
Type of center: دانشگاه دولتی
Paper count: 22,653
In the scientometrics section of CIVILICA, you can see the scientific ranking of the Iranian academic and research centers based on the statistics of indexed articles.

New Papers

New Researchs

Share this page

More information about COI

COI stands for "CIVILICA Object Identifier". COI is the unique code assigned to articles of Iranian conferences and journals when indexing on the CIVILICA citation database.

The COI is the national code of documents indexed in CIVILICA and is a unique and permanent code. it can always be cited and tracked and assumed as registration confirmation ID.

Support