# What forms of the travelling salesman problem are difficult for humans to solve?

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 , 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?

 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.

• 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. Aug 15 '13 at 2:51