Abstract:
The traveling salesman problem is one of the most widely studied problems in the field of combinatorial optimization. However, the investigation of new approaches and the improvement of existing methods remain a significant area of research. This paper presents
an analysis of the quality of the cycle merging algorithm used to solve the minimum traveling salesman problem. The results of a computational experiment on five families of problems are provided, and the accuracy and time complexity of the algorithm are analysed. For symmetric instances, a regression model is constructed to describe the dependence of the relative error estimate on the number of vertices. It is shown that a polynomial model provides the best approximation of the obtained data and satisfies key statistical assumptions. The results allow us to evaluate the error growth patterns and to justify the applicability of algorithms to large scale instances of the traveling salesman problem.
Keywords:traveling salesman problem, heuristic algorithm, asymptotic accuracy of the algorithm, statistical study.
Presented by the member of Editorial Board:A. A. Lazarev
Fulltext:
PDF file (795 kB)
First page:
PDF file