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.
Article PDF
Similar content being viewed by others
Rerefences
Dantzig, G. B., Fulkerson, D. R., &Johnson, S. M. (1959). On a linear-programming, combinatorial approach to the travellingsalesman problem.Operations Research,7, 58–66.
Flood, M. M. (1956). The travelling salesman problem.Operations Research,4, 61–75.
Golden, B., Bodin, L., Doyle, T., &Stewart, W. (1980). Approximate travelling salesman algorithms.Operations Research,28, 694–711.
Krolak, P., Felts, W., &Marble, G. (1971). A man—machine approach toward solving the travelling salesman problem.Communications of the ACM,14, 327–334.
Lee, R. K. L. (1985).A heuristic approach to the travelling salesman problem (Unpublished Management Report). University of Victoria, School of Public Administration.
MacGregor, J. N., &Ormerod, T. (1996). Human performance on the travelling salesman problem.Perception & Psychophysics,58, 527–539.
MacGregor, J. N., Ormerod, T. C., &Chronicle, E. P. (1999). Spatial and contextual factors in the travelling salesperson problem.Perception,28, 1417–1428.
Michie, D., Fleming, J. G., &Oldfield, J. V. (1968). A comparison of heuristic, interactive and unaided methods of solving a shortestroute problem. In D. Michie (Ed.),Machine intelligence 3 (pp. 245–255). New York: Elsevier.
Norback, J. P., &Love, R. F. (1977). Geometric approaches to solving the travelling salesman problem.Management Science,23, 1208–1223.
Ormerod, T. C., &Chronicle, E. P. (1999). Global perceptual processes in problem solving: The case of the traveling salesperson.Perception & Psychophysics,61, 1227–1238.
Sangalli, A. (1992, December 12). Why sales reps pose a hard problem.New Scientist,136, 24–28.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Macgregor, J.N., Ormerod, T.C. & Chronicle, E.P. A model of human performance on the traveling salesperson problem. Memory & Cognition 28, 1183–1190 (2000). https://doi.org/10.3758/BF03211819
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.3758/BF03211819