Versions of the “Onion Husk” Algorithm in the Pseudo-Geometric Traveling Salesman Problem with Small Variance

Abstract

We continue to consider the pseudo-geometric traveling salesman problem. Specifically, we are considering several auxiliary algorithms needed to implement different versions of the “onion husk” algorithm. We have not found in the literature an accurate description of specific versions of algorithms for the geometric version (however, this is not necessary, since it is necessary to implement the original versions for the pseudo-geometric version), so we start with the geometric version.

Random generation of data for computational experiments corresponded to the problem being solved.
For each of the some dimensional variants, some computational experiments were conducted with randomly generated input data.
The following characteristics were calculated:
the average number of resulting contours for the geometric variant; the ratio of the solution with contours to the optimal solution; the ratio of the solution of the pseudo-geometric version corresponding to the order of points of the geometric version to the geometric solution.
The obtained results of computational experiments in general approximately correspond to the expected values.