12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > A model of human performance on the traveling s...
View graph of relations

« Back

A model of human performance on the traveling salesperson problem.

Research output: Contribution to journalJournal article

Published

Journal publication date2000
JournalMemory and Cognition
Journal number7
Volume28
Number of pages8
Pages1183-1190
Original languageEnglish

Abstract

A computational model is proposed of how humans solve the traveling salesperson problem (TSP). Tests of the model are reported, using human performance 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 closely to quantitative and qualitative characteristics of human performance. The minimum path lengths of subjects and model deviated by average absolute 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 solutions than some conventional heuristic algorithms for solving TSPs, and comparative results are reported that support this suggestion.