Path planning and optimization in the traveling salesman problem: Nearest neighbor vs. region-based strategies

Abstract

According to the number of targets, route planning can be a very complex task. Human navigators, however, usually solve route planning tasks fastly and efficiently. Here two experiments are presented that studied human route planning performance, route planning strategies employed, and cognitive processes involved. For this, 25 places were arranged on a regular grid in a large room. Each place was marked by a unique symbol. Subjects were repeatedly asked to solve traveling salesman problems (TSP), i.e. to find the shortest closed loop connecting a given start place with a number of target places. For this, subjects were given a so-called 'shopping list' depicting the symbols of the start place and the target places. While the TSP is computationally hard, sufficient solutions can be found by simple strategies such as the nearest neighbor strategy. In Experiment 1, it was tested whether humans deployed the nearest neighbor strategy (NNS) when solving the TSP. Results showed that subjects outperformed the NNS in cases in which the NNS did not predict the optimal solution, suggesting that the NNS is not sufficient to explain human route planning behavior. As a second possible strategy a region-based approach was tested in Experiment 2. When optimal routes required more region transitions than other, sub-optimal routes, subjects preferred these sub-optimal routes. This result suggests that subjects first planned a coarse route on the region level and then refined the route during navigation. Such a hierarchical planning stragey would allow to reduce computational effort during route planning.
In a control condition, the target places were directly marked in the environment rather than being depicted on the shopping list. As subjects did not have to identify and remember the positions of the target places based on the shopping list during route planning, this control condition tested for the influence of spatial working memory for route planning performance. Results showed a strong performance increase in the control condition, emphasizing the prominent role of spatial working memory for route planning.