Abstract
Recently there has been growing interest among psychologists in human performance on the Euclidean traveling salesperson problem (E-TSP). A debate has been initiated on what strategy people use in solving visually presented E-TSP instances. The most prominent hypothesis is the convex-hull hypothesis, originally proposed by MacGregor and Ormerod (1996). We argue that, in the literature so far, there is no evidence for this hypothesis. Alternatively we propose and motivate the hypothesis that people aim at avoiding crossings.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Flood, M. M. (1956). The traveling-salesman problem.Operations Research,4, 61–75.
Garey, M. R., &Johnson, D. S. (1979).Computers and intractability: A guide to the theory of NP-completeness. New York: Freeman.
Golden, B. L., Bodin, L. D., Doyle, T., &Stewart, W. (1980). Approximate traveling salesman algorithms.Operations Research,28, 694–711.
Graham, S. M., Joshi, A., &Pizlo, Z. (2000). The traveling salesman problem: A hierarchical model.Memory & Cognition,28, 1191–1204.
Lee, M. D., &Vickers, D. (2000). The importance of the convex hull for human performance on the traveling salesman problem: A comment on MacGregor and Ormerod (1996).Perception & Psychophysics,62, 226–228.
MacGregor, J. N., &Ormerod, T. C. (1996). Human performance on the traveling salesman problem.Perception & Psychophysics,58, 527–539.
MacGregor, J. N., &Ormerod, T. C. (2000). Evaluating the importance of the convex hull in solving the Euclidean version of the traveling salesperson problem: Reply to Lee and Vickers (2000).Perception & Psychophysics,62, 1501–1503.
MacGregor, J. N., Ormerod, T. C., &Chronicle, E. P. (1999). Spatial and contextual factors in human performance on the traveling salesperson problem.Perception,28, 1417–1427.
MacGregor, J. N., Ormerod, T. C., &Chronicle, E. P. (2000). A model of human performance on the traveling salesperson problem.Memory & Cognition,28, 1183–1190.
Ormerod, T. C., &Chronicle, E. P. (1999). Global perceptual processing in problem solving: The case of the traveling salesperson.Perception & Psychophysics,61, 1227–1238.
Polivanova, N. I. (1974). On some functional and structural features of the visual-intuitive components of a problem-solving process.Voprosy Psychologii [Questions in Psychology],4, 41–51.
Schactman, A. (2002).Childrens performance on the traveling salesperson problem. Unpublished honors thesis, University of Victoria, Victoria, BC.
Vickers, D., Butavicius, M., Lee, M. D., &Medvedev, A. (2001). Human performance on visually presented traveling salesman problems.Psychological Research,65, 34–45.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by a research grant from the National Science and Engineering Research Council (NSERC) of Canada and a research grant from the University of Victoria, both awarded to U.S. While working on this article, I.R. was additionally supported by NSERC Grant OGP0121280-97, awarded to Helena Kadlec.
Rights and permissions
About this article
Cite this article
Van Rooij, I., Stege, U. & Schactman, A. Convex hull and tour crossings in the Euclidean traveling salesperson problem: Implications for human performance studies. Memory & Cognition 31, 215–220 (2003). https://doi.org/10.3758/BF03194380
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.3758/BF03194380