Well-Separation Heuristics for the Metric Traveling Salesman Problem

Abstract

Well-separated pair decompositions (WSPDs) are a fundamental tool in computational geometry and underlie many geometric approximation algorithms. Despite their widespread use, comparatively little is known about how well-separation constrains the structure of tours in the metric Traveling Salesman Problem (TSP). In this work, we investigate the relationship between WSPDs and TSP tours, providing new insights into how well-separation can be leveraged to design efficient heuristics for the metric TSP. Our main result shows that if a point set can be partitioned into two well-separated pairs, then any optimal TSP tour must visit the points in each set consecutively. We then extend this result to the case of the multiple Traveling Salesman Problem where we prove that similar results hold for each configuration of endpoints. Furthermore, we develop efficient algorithms for testing whether a given point set can be partitioned into well-separated sets, and how to leverage such a partitioning to efficiently compute optimal TSP tours. Finally, we develop a heuristic which can iteratively improve a solution by checking for faults in the tour over each pair in a WSPD.