Effects of cluster location and cluster distribution on performance on the traveling salesman problem

Sense of direction and conscientiousness as predictors of performance in the Euclidean travelling salesman problem

A salesperson wishes to visit a number of cities before returning home using the shortest possible route, whilst only visiting each city once. This optimization problem, called the Travelling Salesman Problem, is difficult to solve using exhaustive algorithms due to the exponential growth in the number of possible solutions. Interestingly, when presented in Euclidean space (ETSP), humans quickly find good solutions. Past studies, however, are in disagreement whether human solutions are impacted by the participant’s ability to process figural effects in the graph geometry. In this study, we used principal component analysis to combine two correlated [r = 0.37, p < 0.01] self-assessed personality measures, i.e., a participant’s sense of direction and a participant’s level of conscientiousness, onto a single impulsiveness/cautiousness dimension. We then showed, using simple linear regression, that this new dimension is a significant predictor [R² = 0.12, p < 0.01] of the number of edge crossings that occur in human ETSP solutions, a key metric of graph optimality. Our study provides evidence to suggest that human solutions to the ETSP are significantly affected by individual differences, including personality and cognitive traits.