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

Kyritsis, M. ORCID: https://orcid.org/0000-0002-7151-1698, Gulliver, S. ORCID: https://orcid.org/0000-0002-4503-5448 and Feredoes, E. (2018) Acknowledging crossing-avoidance heuristic violations when solving the Euclidean travelling salesperson problem. Psychological Research, 82 (5). pp. 997-1009. ISSN 1430-2772 doi: 10.1007/s00426-017-0881-7

Abstract/Summary

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.

Item Type	Article
URI	https://reading-clone.eprints-hosting.org/id/eprint/70834
Item Type	Article
Refereed	Yes
Divisions	Life Sciences > School of Psychology and Clinical Language Sciences > Neuroscience Henley Business School > Digitalisation, Marketing and Entrepreneurship
Publisher	Springer
Download/View statistics	View download statistics for this item