An Experimental Study of Human Problem-Solving Strategies in the Travelling Salesman Problem

The purpose of this research was to assess the strategies used by humans in solving a small-scale version of the Travelling Salesman Problem and to compare these strategies both with those employed by domestic chicks in an equivalent setting and with an AI model built to simulate animal behavior. The resulting strategies were compared to two classical solutions to this problem: the Nearest Neighbour strategy and a specific version of the Optimal strategy. Human subjects (n = 36) were asked to connect three series of 8 points each (called mazes), starting from a common origin indicated by a star. The dependent variables were the timing and the order in which the subjects connected the dots, while the independent variables were the three combinations in which the mazes were arranged and presented to the subjects. Results showed that the paths chosen by human subjects tended to follow an Optimal strategy in 82% of their steps and a Nearest Neighbour strategy in 75% of their steps, while both chicks and the AI model produced total distances closer to those calculated using the Nearest Neighbour strategy.