Skip to main content
Springer Nature Link
Log in

Acknowledging crossing-avoidance heuristic violations when solving the Euclidean travelling salesperson problem

  • Original Article
  • Published:
Psychological Research Aims and scope Submit manuscript

Abstract

If a salesperson aims to visit a number of cities only once before returning home, which route should they take to minimise the total distance/cost? This combinatorial optimization problem is called the travelling salesperson problem (TSP) and has a rapid growth in the number of possible solutions as the number of cities increases. Despite its complexity, when cities and routes are represented in 2D Euclidean space (ETSP), humans solve the problem with relative ease, by applying simple visual heuristics. One of the most important heuristics appears to be the avoidance of path crossings, which will always result in more optimal solutions than tours that contain crossings. This study systematically investigates whether the occurrence of crossings is impacted by geometric properties by modelling their relationship using binomial logistic regression as well as random forests. Results show that properties, such as the number of nodes making up the convex hull, the standard deviation of the angles between nodes, the average distance between all nodes in the graph, the total number of nodes in the graph, and the tour cost (i.e., a measure of performance), are significant predictors of whether crossings are likely to occur.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  • Agarwala, R., Applegate, D. L., Maglott, D., Schuler, G. D., & Schäffer, A. A. (2000). A fast and scalable radiation hybrid map construction and integration strategy. Genome Research, 10(3), 350–364.

    Article  PubMed  PubMed Central  Google Scholar 

  • Anderson, J. R. (1993). Rules of the mind. Hillsdale, NJ: L. Erlbaum Associates.

    Google Scholar 

  • Archer, K. J., & Kimes, R. V. (2008). Empirical characterization of random forest variable importance measures. Computational Statistics and Data Analysis, 52(4), 2249–2260.

    Article  Google Scholar 

  • Babyak, M. A. (2004). What you see may not be what you get: A brief, nontechnical introduction to overfitting in regression-type models. Psychosomatic Medicine, 66(3), 411–421.

    PubMed  Google Scholar 

  • Bender, L. (1938). A visual-motor Gestalt test and its clinical use (Vol. 3)., American Orthopsychiatric Association Monograph Series NY: American Orthopsychiatric Association.

    Google Scholar 

  • Bisiacchi, P. S., Sgaramella, T. M., & Farinello, C. (1998). Planning strategies and control mechanisms: Evidence from closed head injury and aging. Brain and Cognition, 5, 339–361.

    Google Scholar 

  • Bland, R. G., & Shallcross, D. F. (1989). Large travelling salesman problems arising from experiments in X-ray crystallography: a preliminary report on computation. Operations Research Letters, 8(3), 125–128.

    Article  Google Scholar 

  • Blaser, R., & Wilber, J. (2013). A comparison of human performance in figural and navigational versions of the traveling salesman problem. Psychological Research, 77(6), 761–772. doi:10.1007/s00426-012-0470-8.

    Article  PubMed  Google Scholar 

  • Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32.

    Article  Google Scholar 

  • Burns, N. R., Lee, M. D., & Vickers, D. (2006). Are individual differences in performance on perceptual and cognitive optimization problems determined by general intelligence? The Journal of Problem Solving, 1(1), 3.

    Article  Google Scholar 

  • Chronicle, E., MacGregor, J., & Ormerod, T. (2006). Optimizing and “pessimizing”: Human performance with instructional variants of the traveling salesperson problem. The Journal of Problem Solving, 1(1), 7.

    Article  Google Scholar 

  • Dallari, F., Marchet, G., & Ruggeri, R. (2000). Optimisation of man-on-board automated storage/retrieval systems. Integrated Manufacturing Systems, 11(2), 87–93.

    Article  Google Scholar 

  • Dry, M. J., & Fontaine, E. L. (2014). Fast and efficient discrimination of traveling salesperson problem stimulus difficulty. The Journal of Problem Solving, 7(1), 9.

    Article  Google Scholar 

  • Dry, M., Lee, M. D., Vickers, D., & Hughes, P. (2006). Human performance on visually presented traveling salesperson problems with varying numbers of nodes. The Journal of Problem Solving. doi:10.7771/1932-6246.1004.

    Google Scholar 

  • Dry, M., Preiss, K., & Wagemans, J. (2012). Clustering, randomness, and regularity: Spatial distributions and human performance on the traveling salesperson problem and minimum spanning tree problem. The Journal of Problem Solving, 4(1), 2.

    Article  Google Scholar 

  • Eddy, W. F. (1977). A new convex hull algorithm for planar sets. ACM Transactions on Mathematical Software, 3, 398–403.

    Article  Google Scholar 

  • Flood, M. M. (1956). The travelling salesman problem. Operations Research, 4, 61–75.

    Article  Google Scholar 

  • Gandhi, R. (2001). Approximate solution for the Traveling Salesman’s Problem Using Continuous Hopfield Network. ECE 559: Traveling Salesman’s Problem’s Solution using Hopfield NN, pp. 1–9.

  • Gärling, T. (1989). The role of cognitive maps in spatial decisions. Journal of Environmental psychology, 9(4), 269–278.

    Article  Google Scholar 

  • Gollin, E. S. (1960). Developmental studies of visual recognition of incomplete objects. Perceptual and Motor Skills, 11(3), 289–298.

    Article  Google Scholar 

  • Graham, S. M., Joshi, A., & Pizlo, Z. (2000). The Traveling Salesman Problem: A hierarchical model. Memory and Cognition, 28, 1191–1204.

    Article  PubMed  Google Scholar 

  • Hoogeveen, J. A. (1991). Analysis of Christofides’ heuristic: Some paths are more difficult than cycles. Operations Research Letters, 10, 291–295.

    Article  Google Scholar 

  • Hui, S. K., Fader, P. S., & Bradlow, E. T. (2009). Research note-The traveling salesman goes shopping: The systematic deviations of grocery paths from TSP optimality. Marketing Science, 28(3), 566–572.

    Article  Google Scholar 

  • Kass, R. E., & Raftery, A. E. (1995). Bayes factors. Journal of the American Statistical Association, 90(430), 773–795.

    Article  Google Scholar 

  • Kirkpatrick, S. (1984). Optimization by simulated annealing: Quantitative studies. Journal of Statistical Physics, 34(5–6), 975–986.

    Article  Google Scholar 

  • Kuhn, M. (2016). Contributions from Wing J., Weston S., Williams A., Keefer C., Engelhardt A., Cooper T., Mayer Z., Kenkel B., The R Core Team, Benesty M., Lescarbeau R., Ziem A., & Scrucca L.: Classification and regression training. In R Package Version 6.0–70.

  • Larrañaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial Intelligence Review, 13(2), 129–170.

    Article  Google Scholar 

  • MacGregor, J. N., Chronicle, E. P., & Ormerod, T. C. (2004). Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem. Memory and cognition, 32(2), 260–270.

    Article  PubMed  Google Scholar 

  • MacGregor, J. N., & Chu, Y. (2011). Human performance on the traveling salesman and related problems: A review. The Journal of Problem Solving, 3(2), 2.

    Article  Google Scholar 

  • MacGregor, J. N., & Ormerod, T. (1996). Human performance on the traveling salesman problem. Perception and Psychophysics, 58(4), 527–539.

    Article  PubMed  Google Scholar 

  • MacGregor, J. N., Ormerod, T. C., & Chronicle, E. P. (1999). Spatial and contextual factors in human performance on the travelling salesperson problem. Perception, 28(11), 1417–1427.

    Article  PubMed  Google Scholar 

  • Maroco, J., Silva, D., Rodrigues, A., Guerreiro, M., Santana, I., & de Mendonça, A. (2011). Data mining methods in the prediction of Dementia: A real-data comparison of the accuracy, sensitivity and specificity of linear discriminant analysis, logistic regression, neural networks, support vector machines, classification trees and random forests. BMC Research Notes, 4(1), 299.

    Article  PubMed  PubMed Central  Google Scholar 

  • Matai, R., Mittal, M. L., & Singh, S. (2010). Traveling salesman problem: An overview of applications, formulations, and solution approaches. INTECH Open Access Publisher.

  • Newell, A., & Simon, H. A. (1972). Human problem solving. Englewood Cliffs, NJ: Prentice-Hall.

    Google Scholar 

  • Nilsson, C. (2003). Heuristics for the traveling salesman problem (pp. 1–6). Linkoping: Linkoping University.

    Google Scholar 

  • Ormerod, T. C., & Chronicle, E. P. (1999). Global perceptual processing in problem solving: The case of the traveling salesperson. Perception and Psychophysics, 61(6), 1227–1238.

    Article  PubMed  Google Scholar 

  • Pizlo, Z., Stefanov, E., Saalweachter, J., Li, Z., Haxhimusa, Y., & Kropatsch, W. G. (2006). Traveling salesman problem: A foveating pyramid model. The Journal of Problem Solving, 1(1), 8.

    Google Scholar 

  • 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.

    Google Scholar 

  • R Core Team (2016). R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria. https://www.R-project.org/.

  • Schrijver, L. (2003). Combinatorial optimization-polyhedra and efficiency. Algorithms and Combinatorics, 24, 1–1881.

    Google Scholar 

  • Schwarz, G. (1978). Estimating the dimension of a model. The annals of statistics, 6(2), 461–464.

    Article  Google Scholar 

  • Steyerberg, E. W., Harrell, F. E., Borsboom, G. J., Eijkemans, M. J. C., Vergouwe, Y., & Habbema, J. D. F. (2001). Internal validation of predictive models: Efficiency of some procedures for logistic regression analysis. Journal of Clinical Epidemiology, 54(8), 774–781.

    Article  PubMed  Google Scholar 

  • Valenzuela, C. L., & Jones, A. J. (1997). Estimating the Held-Karp lower bound for the geometric TSP. European Journal of Operational Research, 102(1), 157–175.

    Article  Google Scholar 

  • van Rooij, I., Stege, U., & Schactman, A. (2003). Convex hull and tour crossings in the Euclidean traveling salesperson problem: Implications for human performance studies. Memory and cognition, 31(2), 215–220.

    Article  PubMed  Google Scholar 

  • Vickers, D., Lee, M. D., Dry, M., & Hughes, P. (2003). The roles of the convex hull and number of intersections upon performance on visually presented traveling salesperson problems. Memory and Cognition, 31(7), 1094–1104.

    Article  PubMed  Google Scholar 

  • Vickers, D., Mayo, T., Heitmann, M., Lee, M. D., & Hughes, P. (2004). Intelligence and individual differences in performance on three types of visually presented optimisation problems. Personality and Individual Differences, 36(5), 1059–1071.

    Article  Google Scholar 

  • Wang, R., Xiang, J., Zhou, H., Qin, Y., & Zhong, N. (2009). Simulating human heuristic problem solving: A study by combining ACT-R and fMRI brain image. In International Conference on Brain Informatics (pp. 53–62). Springer, Berlin.

  • Wiener, J. M., Ehbauer, N. N., & Mallot, H. A. (2009). Planning paths to multiple targets: Memory involvement and planning heuristics in spatial problem solving. Psychological Research PRPF, 73(5), 644–658.

    Article  Google Scholar 

  • Woeginger, G. J. (2003). Exact algorithms for NP-hard problems: A survey. Lecture Notes in Computer Science, 2570, 185–207.

    Article  Google Scholar 

Download references

Acknowledgements

We would like to thank Dr. Rachel Blaser for her detailed and very constructive review. We would also like to thank Dr. Matthew Dry for his constructive review, for providing us instructions on how to make our statistical models more rigorous and useful, and for providing us with ideas on future directions for our work in the area of human performance in the travelling salesperson problem.

Author information

Authors and Affiliations

  1. Computer and Information Science Department, Higher Colleges of Technology, Sharjah, United Arab Emirates

    Markos Kyritsis

  2. Henley Business School, Business Informatics Systems and Accounting, University of Reading, Reading, RG6 6UD, UK

    Stephen R. Gulliver

  3. School of Psychology and Clinical Language Sciences, University of Reading, Whiteknights Road, Reading, RG6 6AL, UK

    Eva Feredoes

Authors
  1. Markos Kyritsis
    View author publications

    Search author on:PubMed Google Scholar

  2. Stephen R. Gulliver
    View author publications

    Search author on:PubMed Google Scholar

  3. Eva Feredoes
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Markos Kyritsis.

Ethics declarations

Funding

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

Conflict of interest

All authors declare that they have no conflict of interest.

Ethical standards

All procedures performed in the study that involved human participants are in accordance with the ethical standards of the Higher Colleges of Technology research committee and were approved by the City Unity College (Athens, Greece) research committee, where this research initially began. Furthermore, the procedures comply with the 1964 Helsinki declaration and its later amendments.

Informed consent

Informed consent was obtained from all individual participants included in the study using online consent forms, which worked as a pre-requisite to participating in our web-based experiment.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kyritsis, M., Gulliver, S.R. & Feredoes, E. Acknowledging crossing-avoidance heuristic violations when solving the Euclidean travelling salesperson problem. Psychological Research 82, 997–1009 (2018). https://doi.org/10.1007/s00426-017-0881-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s00426-017-0881-7