Humans exceed capabilities of known AI algorithms on the Travelling Salesperson Problem?

Apparently so, says a friend, who notes,

The TSP is a pedagogical problem used to test new AI algorithms. It is used because it is in a class of problems where the complexity scales exponentially with problem size, making finding solutions using a computer very difficult.


Interestingly, human performance on the TSP scales linearly or near linearly with problem size. Either there is some shortcut humans are using, or they have some other capability not exhibited by AI algorithms.

Here’s more on the problem:

The Traveling Salesman Problem is one of the most intensively studied problems in computational mathematics. These pages are devoted to the history, applications, and current research of this challenge of finding the shortest route visiting each member of a collection of locations and returning to your starting point.

But bees can solve it.

What I would like to know is this: If the computer programmer became a travelling salesperson, would he solve an equivalent problem faster than the machine he is trying to use?

Abstract

Little research has been carried out on human performance in optimization problems, such as the Traveling Salesman problem (TSP). Studies by Polivanova (1974, Voprosy Psikhologii, 4, 41–51) and by MacGregor and Ormerod (1996, Perception & Psychophysics, 58, 527–539) suggest that: (1) the complexity of solutions to visually presented TSPs depends on the number of points on the convex hull; and (2) the perception of optimal structure is an innate tendency of the visual system, not subject to individual differences. Results are reported from two experiments. In the first, measures of the total length and completion speed of pathways, and a measure of path uncertainty were compared with optimal solutions produced by an elastic net algorithm and by several heuristic methods. Performance was also compared under instructions to draw the shortest or the most attractive pathway. In the second, various measures of performance were compared with scores on Raven's advanced progressive matrices (APM). The number of points on the convex hull did not determine the relative optimality of solutions, although both this factor and the total number of points influenced solution speed and path uncertainty. Subjects' solutions showed appreciable individual differences, which had a strong correlation with APM scores. The relation between perceptual organization and the process of solving visually presented TSPs is briefly discussed, as is the potential of optimization for providing a conceptual framework for the study of intelligence.
Received: 28 December 1998?/?Accepted: 20 January 2000