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