The traveling salesman problem: approximate algorithm by branch-and-bound method with guaranteed precision | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 45. DOI: 10.17223/20710410/45/12

To solve the traveling salesman problem with distance matrix of order n, we propose an approximate algorithm based on the branch-and-border method. For clipping, an increased least estimate of the current partial solution is used. This guarantees a predetermined value ε of the whole solution error. A computational experiment for distance matrices of four kinds of distributions was carried out. A uniform random (asymmetric) distribution as well as matrices of Euclidean distances between random points (a symmetric distribution) were used. In the latter case, a local search was additionally applied. Estimates for the power p in the polynomial computational complexity O(n^p ) of the algorithm for various kinds of distributions and various values of error ε are obtained. For a uniform random distribution and n ≤ 1000, the obtained estimate of the power p turned out to be close to 2.8 and of an average value of error to be 1 %.