What forms of the travelling salesman problem are difficult for humans to solve?
I just quickly looked this up on Google Scholar and found the following interesting reference :


JN Macgregor, T Ormerod. "Human performance on the traveling salesman problem." Perception &amp; Psychophysics Volume 58, Issue 4, pp 527-539 (June 1996)


This paper claims that "complexity of TSPs is a function of number of nonboundary points, not total number of points." They define a nonboundary point as a point inside the convex hull that encompasses all points in the problem. This paper also makes some interesting observations about perceptual space for humans in this task, claiming that the problem appears to be solved by humans in a 2D problem space that matches the 2D perceptual space. Finally, the references cited by this paper indicate that at least some research has gone into the question of human performance on the TSP as far back as the late 1960s.

It looks like you might also get some useful pointers by following the citation graph from this paper forward in time : http://scholar.google.com/scholar?cites=9195299723226128892