Swipe om te navigeren naar een ander artikel
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.
Log in om toegang te krijgen
Met onderstaand(e) abonnement(en) heeft u direct toegang:
Anderson, J. R. (1993). Rules of the mind. Hillsdale, NJ: L. Erlbaum Associates.
Archer, K. J., & Kimes, R. V. (2008). Empirical characterization of random forest variable importance measures. Computational Statistics and Data Analysis, 52(4), 2249–2260. CrossRef
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
Bender, L. (1938). A visual-motor Gestalt test and its clinical use (Vol. 3)., American Orthopsychiatric Association Monograph Series NY: American Orthopsychiatric Association.
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.
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. CrossRef
Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32. CrossRef
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. CrossRef
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. CrossRef
Dallari, F., Marchet, G., & Ruggeri, R. (2000). Optimisation of man-on-board automated storage/retrieval systems. Integrated Manufacturing Systems, 11(2), 87–93. CrossRef
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. CrossRef
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.
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. CrossRef
Eddy, W. F. (1977). A new convex hull algorithm for planar sets. ACM Transactions on Mathematical Software, 3, 398–403. CrossRef
Flood, M. M. (1956). The travelling salesman problem. Operations Research, 4, 61–75. CrossRef
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. CrossRef
Gollin, E. S. (1960). Developmental studies of visual recognition of incomplete objects. Perceptual and Motor Skills, 11(3), 289–298. CrossRef
Hoogeveen, J. A. (1991). Analysis of Christofides’ heuristic: Some paths are more difficult than cycles. Operations Research Letters, 10, 291–295. CrossRef
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. CrossRef
Kass, R. E., & Raftery, A. E. (1995). Bayes factors. Journal of the American Statistical Association, 90(430), 773–795. CrossRef
Kirkpatrick, S. (1984). Optimization by simulated annealing: Quantitative studies. Journal of Statistical Physics, 34(5–6), 975–986. CrossRef
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. CrossRef
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. CrossRef
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. CrossRefPubMedPubMedCentral
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.
Nilsson, C. (2003). Heuristics for the traveling salesman problem (pp. 1–6). Linkoping: Linkoping University.
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.
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.
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.
Schwarz, G. (1978). Estimating the dimension of a model. The annals of statistics, 6(2), 461–464. CrossRef
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. CrossRef
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. CrossRef
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. CrossRef
Woeginger, G. J. (2003). Exact algorithms for NP-hard problems: A survey. Lecture Notes in Computer Science, 2570, 185–207. CrossRef
- Acknowledging crossing-avoidance heuristic violations when solving the Euclidean travelling salesperson problem
Stephen R. Gulliver
- Springer Berlin Heidelberg