Human behaviour in the Euclidean Travelling Salesperson Problem: Computational modelling of heuristics and figural effects |
| |
| Affiliation: | 1. Computer and Information Science Department, Higher Colleges of Technology, Sharjah, United Arab Emirates;2. Henley Business School, Business Informatics Systems and Accounting, University of Reading, Whiteknights Road, RG6 6UD, United Kingdom;3. School of Psychology and Clinical Language Sciences, University of Reading, Whiteknights Road, RG6 6AL, United Kingdom;1. Center for Logic, Language, and Cognition, University of Torino, Italy;2. Computer Science Department, University of Torino, Italy;1. The Center for Chinese Modern City Studies, East China Normal University, China;2. School of Urban and Regional Science, East China Normal University, China;1. Department of Computer Science and Engineering, MNM Jain Engineering College, Chennai, Tamil Nadu, India;2. Department of Information Technology, Adhiyamaan College of Engineering, Hosur, Tamil Nadu, India;1. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China;2. Collaborative Innovation Center of Geospatial Technology, Wuhan 430079, China;3. School of Geosciences, China University of Petroleum, Qingdao 266580, China;4. School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China;5. Department of Geography & The Environment, University of Denver, Denver, CO 80208-0710, USA;1. Department of Electronics and Communication, Narayanaguru College of Engineering, Kuzhithurai, Kanyakumari, India;2. Department of Electronics and Communication, St. Xavier’s College of Engineering, Chunkankadai, Kanyakumari, India |
| |
| Abstract: | 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. |
| |
| Keywords: | Travelling Salesperson Problem Computational model Heuristics |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
