Accessibility navigation


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

Kyritsis, M., Gulliver, S. 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

Full text not archived in this repository.

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item 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
Refereed:Yes
Divisions:Faculty of Life Sciences > School of Psychology and Clinical Language Sciences > Neuroscience
Henley Business School > Business Informatics, Systems and Accounting
ID Code:70834
Publisher:Springer

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation