10
$\begingroup$

In the traveling salesman problem (TSP) we are given a set of nodes, where one node is the starting node. The task is to find the shortest tour starting at the start node visiting every node exactly once. A variant of the more general TSP is the Euclidean TSP, where the distance between two cities is the usual Euclidean distance. Different metrics can also be considered, suck as the city-block metric.

Based on experimental data in [1], the authors claim that Euclidean TSP instances are easy for humans. They also gathered data on case where the metric used is the city-block metric. They note that "... people are near-optimal for these problems in both metrics."

  • What variants of the travelling salesman problem are hard for humans?
  • Has any research been done on this?

[1] Walwyn, A. L., & Navarro, D. J. (2010). Minimal Paths in the City Block: Human Performance on Euclidean and Non-Euclidean Traveling Salesperson Problems. The Journal of Problem Solving, 3(1), 5.

Improve this question
$\endgroup$
1
  • $\begingroup$ My conjecture is that whenever, for a given problem, the optimality gap for the greedy heuristic is small, then it's easy for humans so solve. $\endgroup$
    – Wuschelbeutel Kartoffelhuhn
    Aug 15, 2013 at 2:51

1 Answer 1

Reset to default
7
$\begingroup$

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 & 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

Improve this answer
$\endgroup$
1
  • $\begingroup$ When you say "citation graph" are you referring to this tool? $\endgroup$
    – Seanny123
    Jul 22, 2014 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.