Acknowledging crossing-avoidance heuristic violations when solving the Euclidean travelling salesperson problem
- 12 June 2017
- journal article
- research article
- Published by Springer Nature in Psychological Research
- Vol. 82 (5) , 997-1009
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.Keywords
This publication has 36 references indexed in Scilit:
- 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 forestsBMC Research Notes, 2011
- Intelligence and individual differences in performance on three types of visually presented optimisation problemsPersonality and Individual Differences, 2004
- Convex hull and tour crossings in the Euclidean traveling salesperson problem: Implications for human performance studiesMemory & Cognition, 2003
- Internal validation of predictive modelsJournal of Clinical Epidemiology, 2001
- Optimisation of man-on-board automated storage/retrieval systemsIntegrated Manufacturing Systems, 2000
- Human performance on the traveling salesman problemPerception & Psychophysics, 1996
- Bayes FactorsJournal of the American Statistical Association, 1995
- Analysis of Christofides' heuristic: Some paths are more difficult than cyclesOperations Research Letters, 1991
- Estimating the Dimension of a ModelThe Annals of Statistics, 1978
- A New Convex Hull Algorithm for Planar SetsACM Transactions on Mathematical Software, 1977