A heuristic method for the travelling salesman problem

Abstract

In this paper we describe a heuristic procedure for solving the travelling salesman problem in the symmetric case without using the triangle inequality c _ij  ≤ c _ik  + c _kj . A complete proof of the correctness of the algorithm and example of the presentation how the method works are given. There is estimated computational complexity, which is at most O(m²), where m is a number of the edges of the complete graph with n vertices -K _n . There is shown also, it is possible obtain the following bound that $\frac{\mathit{HEURISTIC}\mathit{SOLUTION}}{\mathit{OPTIMAL}\mathit{SOLUTION}}<3$ , if some specific inequality considering weights (costs) of edges is satisfied.