Arman Baradaran¹, Jacob VanDrunen², Sébastien Hélie³, Zygmunt Pizlo¹; ¹University of California, Irvine, ²Westminster Seminary California, ³Purdue University

Human performance on classic traveling salesperson problems (TSPs) depends primarily on perceptual processes. Participants produce near-optimal tours by relying on hierarchical clustering followed by global-to-local tour refinement, though it is unclear to what extent analytical skills like forward planning are involved. We investigated this question using non-metric TSPs in which half of the cities were assigned one of two colors, and switching colors incurred a cost equal to twice the Euclidean distance between cities. Performance on 30 TSPs with 50 cities each was evaluated through two dependent variables: (a) error with respect to optimal tours and (b) number of color switches. Performance varied significantly more in non-metric TSPs than in Euclidean TSPs, with percent errors ranging from 3% to 32%. Several participants adopted a minimal-switch heuristic, producing tours that emphasized clustering of same-colored cities and making only 2 color switches. Others made deviations from color-based clustering that discounted the switching cost, with one participant even making 22 color switches on average. We then compared participants’ performance to two versions of a multiresolution graph pyramid model. The first version, which operated on spatial clustering and used cheapest insertion to consider switching costs, underperformed compared to most humans and overestimated the number of switches. The second version had a front-end that used a 3D Euclidean approximation produced by applying multidimensional scaling (MDS) to the non-metric pairwise distances. This latter version mimicked the behavior of the minimal-switch participants, and after parameter adjustments in the MDS process, it also replicated the performance of more analytically-inclined participants. These findings suggest that combining a multiresolution pyramid representation with 3D MDS can capture human behavior in non-metric TSPs. More broadly, non-metric TSPs may serve as a useful proxy for studying how humans integrate perceptual and analytical processes in complex problem solving domains such as chess.