TITLE:
On the “Onion Husk” Algorithm for Approximate Solution of the Traveling Salesman Problem
AUTHORS:
Mikhail E. Abramyan, Nikolai I. Krainiukov, Boris F. Melnikov
KEYWORDS:
Branch and Bound Method, Contour Algorithm, “Onion Husk” Algorithm, Simulated Annealing Method, Traveling Salesman Problem
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.12 No.4,
April
30,
2024
ABSTRACT: The paper describes some implementation aspects of an algorithm for approximate solution of the traveling salesman problem based on the construction of convex closed contours on the initial set of points (“cities”) and their subsequent combination into a closed path (the so-called contour algorithm or “onion husk” algorithm). A number of heuristics related to the different stages of the algorithm are considered, and various variants of the algorithm based on these heuristics are analyzed. Sets of randomly generated points of different sizes (from 4 to 90 and from 500 to 10,000) were used to test the algorithms. The numerical results obtained are compared with the results of two well-known combinatorial optimization algorithms, namely the algorithm based on the branch and bound method and the simulated annealing algorithm.