A model of human performance on the traveling salesperson problem

A computational model is proposed of how humans solve the traveling salespe rson problem (TSP). Tests of the model are reported, using human performanc e measures from a variety of 10-, 20-, 40-, and 60-node problems, a single 48-node problem, and a single 100-node problem. The model provided a range of solutions that approximated the range of human solutions and conformed c losely to quantitative and qualitative characteristics of human performance . The minimum path lengths of subjects and model deviated by average absolu te values of 0.0%, 0.9%, 2.4%, 1.4%, 3.5%, and 0.02% for the 10-, 20-, 40-, 48-, 60-, and 100-node problems, respectively. Because the model produces a range of solutions, rather than a single solution, it may find better sol utions than some conventional heuristic algorithms for solving TSPs, and co mparative results are reported that support this suggestion.