Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane

TLDR

Partitioning algorithms are investigated as a means to approximate large planar traveling‑salesman problem instances. The method divides the cities into small groups, optimally tours each group, patches the subtours into a global tour, and can be combined with existing heuristics to improve results. When cities are randomly distributed, the relative error is O(t^−½), and hybrid schemes can produce near‑optimal solutions for problems with thousands of cities.

Abstract

We consider partitioning algorithms for the approximate solution of large instances of the traveling-salesman problem in the plane. These algorithms subdivide the set of cities into small groups, construct an optimum tour through each group, and then patch the subtours together to form a tour through all the cities. If the number of cities in the problem is n, and the number of cities in each group is t, then the worst-case error is [Formula: see text]. If the cities are randomly distributed, then the relative error is O(t −1/2 ) (with probability one). Hybrid schemes are suggested, in which partitioning is used in conjunction with existing heuristic algorithms. These hybrid schemes may be expected to give near-optimum solutions to problems with thousands of cities.