Editing Travelling salesman problem (section)

== Human and animal performance ==
The TSP, in particular the [[Euclidean distance|Euclidean]] variant of the problem, has attracted the attention of researchers in [[cognitive psychology]]. It has been observed that humans are able to produce near-optimal solutions quickly, in a close-to-linear fashion, with performance that ranges from 1% less efficient, for graphs with 10–20 nodes, to 11% less efficient for graphs with 120 nodes.<ref>{{citation|title=Human performance on the traveling salesman problem|first1=J. N.|last1=Macgregor|first2=T.|last2=Ormerod|journal=Perception & Psychophysics|date=June 1996|volume=58|issue=4|pages=527–539|doi=10.3758/BF03213088|pmid=8934685|doi-access=free}}.</ref><ref>{{Cite journal |last1=Dry|first1=Matthew|last2=Lee|first2=Michael D.|last3=Vickers|first3=Douglas|last4=Hughes|first4=Peter|date=2006|title=Human Performance on Visually Presented Traveling Salesperson Problems with Varying Numbers of Nodes |journal=The Journal of Problem Solving|volume=1|issue=1|doi=10.7771/1932-6246.1004|issn=1932-6246|citeseerx=10.1.1.360.9763}}</ref> The apparent ease with which humans accurately generate near-optimal solutions to the problem has led researchers to hypothesize that humans use one or more heuristics, with the two most popular theories arguably being the convex-hull hypothesis and the crossing-avoidance heuristic.<ref>{{Cite journal|last1=Rooij |first1=Iris Van|last2=Stege|first2=Ulrike|last3=Schactman|first3=Alissa|date=2003-03-01|title=Convex hull and tour crossings in the Euclidean traveling salesperson problem: Implications for human performance studies|journal=Memory & Cognition |volume=31|issue=2|pages=215–220|doi=10.3758/bf03194380|pmid=12749463|issn=0090-502X|citeseerx=10.1.1.12.6117|s2cid=18989303}}</ref><ref>{{Cite journal|last1=MacGregor|first1=James N.|last2=Chu|first2=Yun |date=2011 |title=Human Performance on the Traveling Salesman and Related Problems: A Review|journal=The Journal of Problem Solving|volume=3|issue=2|doi=10.7771/1932-6246.1090|issn=1932-6246|doi-access=free}}</ref><ref>{{Cite journal |last1=MacGregor |first1=James N.|last2=Chronicle|first2=Edward P.|last3=Ormerod|first3=Thomas C.|date=2004-03-01|title=Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem|journal=Memory & Cognition |volume=32|issue=2|pages=260–270|doi=10.3758/bf03196857|pmid=15190718|issn=0090-502X|doi-access=free}}</ref> However, additional evidence suggests that human performance is quite varied, and individual differences as well as graph geometry appear to affect performance in the task.<ref>{{Cite journal|last1=Vickers|first1=Douglas|last2=Mayo|first2=Therese|last3=Heitmann|first3=Megan|last4=Lee|first4=Michael D|last5=Hughes|first5=Peter |title=Intelligence and individual differences in performance on three types of visually presented optimisation problems|journal=Personality and Individual Differences|volume=36|issue=5|pages=1059–1071|doi=10.1016/s0191-8869(03)00200-9|year=2004}}</ref><ref>{{Cite journal|last1=Kyritsis|first1=Markos|last2=Gulliver|first2=Stephen R.|last3=Feredoes|first3=Eva|date=2017-06-12|title=Acknowledging crossing-avoidance heuristic violations when solving the Euclidean travelling salesperson problem|journal=Psychological Research|volume=82|issue=5|pages=997–1009|doi=10.1007/s00426-017-0881-7|pmid=28608230|s2cid=3959429|issn=0340-0727}}</ref><ref>{{Cite journal|last1=Kyritsis |first1=Markos|last2=Blathras |first2=George|last3=Gulliver|first3=Stephen|last4=Varela|first4=Vasiliki-Alexia|title=Sense of direction and conscientiousness as predictors of performance in the Euclidean travelling salesman problem |journal=Heliyon|volume=3 |issue=11|pages=e00461|doi=10.1016/j.heliyon.2017.e00461|pmid=29264418|pmc=5727545|date=2017-01-11|doi-access=free |bibcode=2017Heliy...300461K }}</ref> Nevertheless, results suggest that computer performance on the TSP may be improved by understanding and emulating the methods used by humans for these problems,<ref>{{Cite journal|last1=Kyritsis|first1=Markos|last2=Gulliver|first2=Stephen R.|last3=Feredoes|first3=Eva|last4=Din|first4=Shahab Ud|date=December 2018 |title=Human behaviour in the Euclidean Travelling Salesperson Problem: Computational modelling of heuristics and figural effects|journal=Cognitive Systems Research|volume=52|pages=387–399|doi=10.1016/j.cogsys.2018.07.027 |s2cid=53761995}}</ref> and have also led to new insights into the mechanisms of human thought.<ref name="hptsp">{{citation|title=Human performance on the traveling salesman and related problems: A review|first1=James N. |last1=MacGregor|first2=Yun|last2=Chu |journal=Journal of Problem Solving|volume=3|issue=2|year=2011|url=https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1090&context=jps|doi=10.7771/1932-6246.1090|doi-access=free}}.</ref> The first issue of the ''Journal of Problem Solving'' was devoted to the topic of human performance on TSP,<ref>[https://docs.lib.purdue.edu/jps/vol1/iss1/ ''Journal of Problem Solving'' 1(1)], 2006, retrieved 2014-06-06.</ref> and a 2011 review listed dozens of papers on the subject.<ref name="hptsp"/>

A 2011 study in [[animal cognition]] titled "Let the Pigeon Drive the Bus," named after the children's book ''[[Don't Let the Pigeon Drive the Bus!]]'', examined spatial cognition in pigeons by studying their flight patterns between multiple feeders in a laboratory in relation to the travelling salesman problem. In the first experiment, pigeons were placed in the corner of a lab room and allowed to fly to nearby feeders containing peas. The researchers found that pigeons largely used proximity to determine which feeder they would select next. In the second experiment, the feeders were arranged in such a way that flying to the nearest feeder at every opportunity would be largely inefficient if the pigeons needed to visit every feeder. The results of the second experiment indicate that pigeons, while still favoring proximity-based solutions, "can plan several steps ahead along the route when the differences in travel costs between efficient and less efficient routes based on proximity become larger."<ref>{{Cite journal|last1=Gibson|first1=Brett|last2=Wilkinson|first2=Matthew|last3=Kelly|first3=Debbie|date=2012-05-01|title=Let the pigeon drive the bus: pigeons can plan future routes in a room|journal=Animal Cognition|language=en|volume=15|issue=3|pages=379–391|doi=10.1007/s10071-011-0463-9|issn=1435-9456|pmid=21965161|s2cid=14994429}}</ref> These results are consistent with other experiments done with non-primates, which have proven that some non-primates were able to plan complex travel routes. This suggests non-primates may possess a relatively sophisticated spatial cognitive ability.