<p>I just quickly looked this up on Google Scholar and found the following interesting reference :</p>

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

<p>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.</p>

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

CC BY-SA 3.0
2014-07-22T23:51:45.130Z
When you say "citation graph" are you referring to [this tool](http://www.madhavajay.com/kalki/)?
Seanny123
CC BY-SA 3.0
2013-08-14T17:34:17.700Z
2013-08-14T17:34:17.700Z
lmjohns3
<p>In the <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem"><em>traveling salesman problem</em> (TSP)</a> 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 <em>Euclidean TSP</em>, where the distance between two cities is the usual Euclidean distance. Different metrics can also be considered, suck as the <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP">city-block metric</a>.</p>

<p>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."</p>

<ul>
<li><strong>What variants of the travelling salesman problem are hard for humans?</strong></li>
<li><strong>Has any research been done on this?</strong></li>
</ul>

<hr>

<p>[1] Walwyn, A. L., &amp; 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.</p>

CC BY-SA 3.0
2013-08-15T02:51:11.140Z
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.
Wuschelbeutel Kartoffelhuhn
<cognitive-psychology><problem-solving>
What forms of the travelling salesman problem are difficult for humans to solve?
Juho
# What forms of the travelling salesman problem are difficult for humans to solve?

(Asked by: username_0 on 2013-08-04)

In the [*traveling salesman problem* (TSP)](http://en.wikipedia.org/wiki/Travelling_salesman_problem) 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](http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP).

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.

**Tags:** cognitive-psychology, problem-solving

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2013-08-14. Score: 7 | Accepted answer

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>

> **Comments:**
> **username_3**: When you say "citation graph" are you referring to [this tool](http://www.madhavajay.com/kalki/)?  

---

