Some factors affecting performance of rats in the traveling salesman problem

Adaptive specialization for spatial memory does not improve route efficiency: Comparing the ability of Clark's nutcrackers (Nucifraga columbiana) and pigeons (Columba livia) to solve traveling salesperson problems

An important question in comparative cognition is whether animals are capable of planning ahead. Todd and Hills (Current Directions in Psychological Science, 29(3), 309-315, 2020) recently suggested that the ability to plan and choose internally may have scaffolded upon the cognitive mechanisms required by animals to search among patchy resources in their external environment. The traveling salesperson problem (TSP) is a spatial optimization problem in which a traveler is faced with the task of finding the best route from a start location to two or more destinations or targets. The Clark's nutcracker (Nucifraga columbiana) is a food-storing corvid with a highly specialized spatial memory. Spatial memory would appear to be deeply rooted in the cognitive mechanisms required for choosing efficiently among multiple alternative routes during a TSP. If so, then species like nutcrackers that are more dependent upon spatial memory for survival may have a greater ability to plan ahead or choose more efficiently among different route options than species that have less selective pressure for remembering the location of food, like pigeons. We examined the ability of nutcrackers to solve TSPs using the same procedures and target configurations as in our past research (Gibson, Wilkerson, & Kelly, Animal Cognition, 15, 379-391, 2012) to explore if nutcrackers can efficiently solve TSPs and how their route solutions compare with those of pigeons. Nutcrackers did not display an advantage in route efficiency and performed comparably to pigeons. Both species tended to prefer a nearest-neighbor strategy to more globally efficient routes. Having a more robust spatial memory may not improve the ability of animals to determine routes to multiple locations.

Contribution of the hippocampus to performance on the traveling salesperson problem in rats

The Traveling Salesman Problem (TSP) is an optimization problem in which the subject attempts to find the shortest possible route that passes through a set of fixed locations exactly once. The TSP is used in cognitive and behavioral research to study problem solving and spatial navigation. While the TSP has been studied in some depth from this perspective, the biological mechanisms underlying the behavior have not yet been explored. The hippocampus is a structure in the brain that is known to be involved in tasks that require spatial memory. Because the TSP requires spatial problem solving, we designed the current study to determine whether the hippocampus is required to find efficient solutions to the TSP, and if so, what role the hippocampus serves. Rats were pretrained on the TSP, which involved learning to retrieve bait from targets in a variety of spatial configurations. Matched for performance, rats were then divided into two groups, receiving either a hippocampal lesion or a control sham surgery. After recovering from surgery, the rats were tested on eight new configurations. A variety of behavioral measures were recorded, including distance travelled, number of revisits, memory span, and latency. The results showed that the sham group outperformed the lesion group on most of these measures. Based on the behavioral data and histological tissue analysis of each group, we determined that the hippocampus is involved in successful performance in the TSP, particularly regarding memory for which targets have already been visited.

Bee Inspired Novel Optimization Algorithm and Mathematical Model for Effective and Efficient Route Planning in Railway System

Railway and metro transport systems (RS) are becoming one of the popular choices of transportation among people, especially those who live in urban cities. Urbanization and increasing population due to rapid development of economy in many cities are leading to a bigger demand for urban rail transit. Despite being a popular variant of Traveling Salesman Problem (TSP), it appears that the universal formula or techniques to solve the problem are yet to be found. This paper aims to develop an optimization algorithm for optimum route selection to multiple destinations in RS before returning to the starting point. Bee foraging behaviour is examined to generate a reliable algorithm in railway TSP. The algorithm is then verified by comparing the results with the exact solutions in 10 test cases, and a numerical case study is designed to demonstrate the application with large size sample. It is tested to be efficient and effective in railway route planning as the tour can be completed within a certain period of time by using minimal resources. The findings further support the reliability of the algorithm and capability to solve the problems with different complexity. This algorithm can be used as a method to assist business practitioners making better decision in route planning.