Clustering as a precursor to efficient and near-optimal solution of small instances of the Traveling Salesperson Problem (TSP)

AbstractHumans efficiently find near-optimal (i.e., near-minimum-length) tours when solving small instances of the Traveling Salesperson Problem (TSP), a problem hard for computers. We hypothesize that this is possible because they use the following strategy: cluster the points, solve the smaller TSPs for each cluster, and then solve the TSP defined by the clusters. This study focused on the antecedent process of human clustering. 42 participants clustered 56 sets of 15 to 40 points on two occasions. We found that human clustering is generally reliable (M Fowlkes-Mallows Index = 0.75) for all problem sizes. Reliability was higher for problems that showed statistical evidence of cluster structure versus no such structure, and was not affected when the problem was flipped for the second presentation. Thus, humans are sensitive to cluster structure, and clustering is a stable foundation for solving TSP instances. This sets the stage for future research on clustering-based TSP strategies.

Return to previous page