The traveling salesman problem (TSP) is an optimization problem in which the goal is to find the shortest possible route that passes through each of a set of points in space. The TSP is of interest not only in the fields of mathematics, computer science, and engineering, but also in cognitive and behavioral research to study problem-solving and spatial navigation. Humans are able to complete even complex TSPs with a high degree of efficiency, and distance minimization in TSP analogs has been observed in a variety of nonhuman species as well. Tasks based on the TSP also have the potential for translational research on cognitive and neurological disorders such as Alzheimer's disease. The current experiment was designed to examine the effects of target number on TSP performance in rats. After pretraining, rats were tested once on each of several target configurations, and their travel routes were recorded. We examined the routes for general efficiency, as well as evidence for strategy use including the nearest neighbor (NN) strategy and crossing avoidance. Our results indicate that latency and route length increase in proportion to the number of targets. Rats also showed a strong tendency to avoid path crossing, and to select NN targets, which strengthened with increasing target numbers. Taken together, our results indicate that travel efficiency decreases linearly in relation to the target number rather than the number of possible routes, which grows factorially with a target number. Additionally, spatial memory and route selection strategy are also affected by an increasing number of targets. [ABSTRACT FROM AUTHOR]