Clustering as a precursor to efficient and near-optimal solution of small instances of the Traveling Salesperson Problem (TSP)
- Vijay Marupudi, Educational Psychology, University of Minnesota-Twin Cities, Minneapolis, Minnesota, United States
- Vimal Rao, Educational Psychology, University of Minnesota-Twin Cities, Minneapolis, Minnesota, United States
- Jimin Park, Educational Psychology, University of Minnesota, Minneapolis, Minnesota, United States
- Rina Harsch, Educational Psychology, University of Minnesota, Minneapolis, Minnesota, United States
- Jeffrey Bye, Educational Psychology, University of Minnesota, Minneapolis, Minnesota, United States
- Sashank Varma, Educational Psychology, University of Minnesota, Minneapolis, Minnesota, United States
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.