Human performance in the Traveling Salesman Problem is influenced by spatial scale

Abstract

Like many other animals, we humans frequently face complex route optimization problems when planning journeys between multiple locations. Several strategies can be employed to approach such Traveling Salesman Problems. However, these may be strongly constrained by spatial scales, for instance if the goal is to navigate in a supermarket, in a city, or across a continent. Here, we monitored the route optimization performances of human subjects collecting objects in a video game simulating 3D environments at various spatial scales. Unexpectedly, route optimization performances peaked at intermediate spatial scales, where participants could use global optimization strategies. At very large and very small spatial scales, however, participants predominantly employed less efficient local optimization strategies. At the very large scale, the considerable distances between objects prevented them from being seen all at once, making global planning difficult. At the very small scale, participants reported having chosen the shortest path, although they did not. This mismatch between perceived and actual performances suggests suboptimal alternatives were sufficiently short to be considered equivalent to the optimal route. Spatial scale thus strongly influences route planning in human navigators and may determine the spatial behaviors of a wide range of animals facing similar routing problems in their everyday lives.