University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem.

MacGregor, JN, Chronicle, EP and Ormerod, TC (2004) Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem. Mem Cognit, 32 (2). pp. 260-270.

Full text not available from this repository.


Untrained adults appear to have access to cognitive processes that allow them to perform well in the Euclidean version of the traveling salesperson problem (E-TSP). They do so despite the famous computational intractability of the problem, which stems from its combinatorial complexity. A current hypothesis is the humans' good performance is based on following a strategy of connecting boundary points in order (the convex hull hypothesis). Recently, an alternative has been proposed, that performance is governed by a strategy of avoiding crossings. We examined the crossing avoidance hypothesis from the perspectives of its capacity to explain existing data, its theoretical adequacy, and its ability to explain the results of three new experiments. In Experiment 1, effects on the solution quality of number of points versus number of interior points were compared. In Experiment 2, the distributions of observed paths were compared with those predicted from the two hypotheses. In Experiment 3, figural effects were varied to induce crossings. The results of the experiments were more consistent with the convex hull than with the crossing avoidance hypothesis. Despite its simplicity and intuitive appeal, crossing avoidance does not provide a complete alternative to the convex hull hypothesis. Further elucidation of human strategies and heuristics for optimization problems such as the E-TSP will aid our understanding of how cognitive processes have adapted to the demands of combinatorial difficulty.

Item Type: Article
Divisions : Surrey research (other units)
Authors :
MacGregor, JN
Chronicle, EP
Date : March 2004
Uncontrolled Keywords : Commerce, Humans, Travel
Related URLs :
Depositing User : Symplectic Elements
Date Deposited : 17 May 2017 09:58
Last Modified : 24 Jan 2020 18:11

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800