Accessibility navigation


Human behaviour in the Euclidean Travelling Salesperson Problem: computational modelling of heuristics and figural effects

Kyritsis, M. ORCID: https://orcid.org/0000-0002-7151-1698, Gulliver, S. ORCID: https://orcid.org/0000-0002-4503-5448, Feredoes, E. and Ud Din, S. (2018) Human behaviour in the Euclidean Travelling Salesperson Problem: computational modelling of heuristics and figural effects. Cognitive Systems Research, 52. pp. 387-399. ISSN 1389-0417

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.1016/j.cogsys.2018.07.027

Abstract/Summary

The Travelling Salesperson Problem (TSP) describes a situation where an imaginary individual wishes to visit multiple cities once before returning to his/her own city. This type of problem is known as a nondeterministic polynomial (NP) hard problem, since the factorial number of solutions results in it being impractical to solve using exhaustive processing. Interestingly, when presented as a Euclidean graph (i.e., ETSP), humans identify near optimal solutions almost effortlessly, despite billions of possible tours. In this study, we consider human processing of the ETSP, and introduce the reader to a number of factors that literature proposes as impacting human performance. We hypothesise that: (i) human ETSP activity may be modelled by considering the quotient relationship between node-to-node and node-to-centroid distances.; and (ii) consideration of figural effects can optimise automated TSP solution generation. In this paper human processing based heuristics are developed, i.e. replacing the cost function within the nearest neighbour algorithm, to guide node selection. Results showed that the quotient relationship between node-to-node and node-to-centroid distances can be used to closely model average human performance, across a range of ETSP graphs. Interestingly, however, additional consideration of graph figural effects (e.g. distance between boundary points in the convex hull, standard deviation of distances between nodes that make up the convex hull, and number of nodes in the convex hull) results in significantly improved tour costs.

Item Type:Article
Refereed:Yes
Divisions:Life Sciences > School of Psychology and Clinical Language Sciences > Department of Psychology
Henley Business School > Business Informatics, Systems and Accounting
ID Code:78414
Publisher:Elsevier

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

Page navigation