جلد 35، شماره 1 - ( 1-1403 )                   جلد 35 شماره 1 صفحات 13-1 | برگشت به فهرست نسخه ها


XML English Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Masoumi M, Behnamian J. A new heuristic algorithm based on minimum spanning tree for solving metric traveling salesman problem. IJIEPR 2024; 35 (1) :1-13
URL: http://ijiepr.iust.ac.ir/article-1-1843-fa.html
A new heuristic algorithm based on minimum spanning tree for solving metric traveling salesman problem. نشریه بین المللی مهندسی صنایع و تحقیقات تولید. 1403; 35 (1) :1-13

URL: http://ijiepr.iust.ac.ir/article-1-1843-fa.html


چکیده:   (695 مشاهده)
Due to the many applications of the travelling salesman problem, solving this problem has been considered by many researchers. One of the subsets of the travelling salesman problem is the metric travelling salesman problem in which a triangular inequality is observed. This is a crucial problem in combinatorial optimization as it is used as a standard problem as a basis for proving complexity or providing solutions to other problems in this class. The solution is used usually in logistics, manufacturing and other areas for cost minimization. Since this is an NP-hard problem, heuristic and meta-heuristic algorithms seek near-optimal solutions in polynomial time as numerical solutions. For this purpose, in this paper, a heuristic algorithm based on the minimum spanning tree is presented to solve this problem. Then, by generating 20 instances, the efficiency of the proposed algorithm was compared with one of the most famous algorithms for solving the travelling salesman problem, namely the nearest neighbour algorithm and the ant colony optimization algorithm. The results show that the proposed algorithm has good convergence to the optimal solution. In general, the proposed algorithm has a balance between runtime and the solution found compared to the other two algorithms. So the nearest neighbour algorithm has a very good runtime to reach the solution but did not have the necessary convergence to the optimal solution, and vice versa, the ant colony algorithm converges very well to the optimal solution, but, its runtime solution is very longer than the proposed algorithm.
 
     
نوع مطالعه: پژوهشي | موضوع مقاله: زنجیره تامین و لجستیک
دریافت: 1402/4/7 | پذیرش: 1402/10/17 | انتشار: 1402/12/21

ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
CAPTCHA

بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.

کلیه حقوق این وب سایت متعلق به نشریه بین المللی مهندسی صنایع و تحقیقات تولید می باشد.

طراحی و برنامه نویسی : یکتاوب افزار شرق

© 2024 CC BY-NC 4.0 | International Journal of Industrial Engineering & Production Research

Designed & Developed by : Yektaweb