Human Performance on Visually Presented Traveling Salesperson Problems with Varying Numbers of Nodes

Abstract

We investigated the properties of the distribution of human solution times for Traveling Salesperson Problems (TSPs) with increasing numbers of nodes. New experimental data are presented that measure solution times for carefully chosen representative problems with 10, 20, . . . 120 nodes. We compared the solution times predicted by the convex hull procedure proposed by MacGregor and Ormerod (1996), the hierarchical approach of Graham, Joshi, and Pizlo (2000), and by five algorithms drawn from the artificial intelligence and operations research literature. The most likely polynomial model for describing the relationship between mean solution time and the size of a TSP is linear or near-linear over the range of problem sizes tested, supporting the earlier finding of Graham et al. (2000). We argue the properties of the solution time distributions place strong constraints on the development of detailed models of human performance for TSPs, and provide some evaluation of previously proposed models in light of our findings.