THE USE OF WELZL’S ALGORITHM FOR SOLVING THE TRAVELING SALESMAN PROBLEM

Abstract

This article is devoted to solving one of the NP-hard problems, namely finding the optimal traveling salesman route for visiting each of the n given cities. Efficient algorithms for solving this problem make it possible to find optimal routeseven for large sets of cities, which reduces time, fuel, and resource costs. Combining high accuracy with low computational complexity makes such methods suitable for real-world systems where decisions must be made quickly.The purpose of this work is to improve the branch-and-bound method for solving the traveling salesman problem by applying Welzl’s algorithm and using the Minimum Enclosing Circle (MEC) as a heuristic to enhance the pruning rules in the branch-and-bound method.Methodology. Welzl’s algorithm is a classical example of an efficient geometric method with pruning and heuristics, whichcan be easily integrated into more complex algorithms, including the branch-and-bound method. In problems of placement, packing, collision detection, clustering, and others, Welzl’s algorithm can be used as part of an evaluation or pruning function: compute the minimum circle that contains a subset of city objects to estimate the space/volume, and if the circle with a new point goes beyond the allowed limits, prune the branch.Scientific novelty. The author proposes using Welzl’s algorithm to speed up the exact solution of the traveling salesmanproblem. The benefit of finding the minimum circle covering a set of city points on the plane lies in obtaining a tighter lower boundfor a branch in the branch-and-bound method, increasing the number of branches in the search tree that are pruned earlier, and consequently making the branch-and-bound method faster. MEC prunes branches in which the unvisited cities lie far apart, and even the most optimal extended route would be too costly. This reduces the search space and accelerates the algorithm.Conclusions. The branch-and-bound method with the use of the Minimum Enclosing Circle has a wide range of practical applications in problems where it is necessary to quickly obtain a high-quality route with minimal computational cost, even if a slight deviation from the optimal solution is acceptable. Thus, using MEC in combination with the branch-and-bound method is a universal approach that combines the precision of mathematical optimization with the speed of heuristic methods and canbe implemented in any field where routing has significant practical importance.