On One Algorithm for Approximate Solution of the Traveling Salesman Problem

Abstract

The paper describes the results of numerical investigation of the efficiency of the contour (“onion husk”) algorithm for approximate solution of the traveling salesman problem. The algorithm is based on the construction of convex closed contours on the initial set of nodes (“cities”) and their subsequent merging into a closed path. Several versions of the contour algorithm are considered. Sets of randomly generated nodes, the number of which varies from 4 to 90, are used to test these versions. The 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. The possibility of applying the contour algorithm to the pseudogeometric traveling salesman problem, for which an analog of the distance matrix rather than a set of nodes is given, is also discussed.