NotesFAQContact Us
Search Tips
Peer reviewed Peer reviewed
Direct linkDirect link
ERIC Number: EJ1116134
Record Type: Journal
Publication Date: 2008-Jul
Pages: 25
Abstractor: As Provided
ISSN: EISSN-1932-6246
Some Tours Are More Equal than Others: The Convex-Hull Model Revisited with Lessons for Testing Models of the Traveling Salesperson Problem
Tak, Susanne; Plaisier, Marco; van Rooij, Iris
Journal of Problem Solving, v2 n1 Article 2 p4-28 Jul 2008
To explain human performance on the "Traveling Salesperson" problem (TSP), MacGregor, Ormerod, and Chronicle (2000) proposed that humans construct solutions according to the steps described by their convex-hull algorithm. Focusing on tour length as the dependent variable, and using only random or semirandom point sets, the authors claimed empirical support for their model. In this paper we argue that the empirical tests performed by MacGregor et al. do not constitute support for the model, because they instantiate what Meehl (1997) coined "weak tests" (i.e., tests with a high probability of yielding confirmation even if the model is false). To perform "strong" tests of the model, we implemented the algorithm in a computer program and compared its performance to that of humans on six point sets. The comparison reveals substantial and systematic differences in the shapes of the tours produced by the algorithm and human participants, for five of the six point sets. The methodological lesson for testing TSP models is twofold: (1) Include qualitative measures (such as tour shape) as a dependent variable, and (2) use point sets for which the model makes "risky" predictions.
Purdue University Press. Stewart Center Room 370, 504 West State Street, West Lafayette, IN 47907. Tel: 800-247-6553; Fax: 419-281-6883; e-mail: pupress@purdue,edu; Web site:
Publication Type: Journal Articles; Reports - Research
Education Level: Higher Education; Postsecondary Education
Audience: N/A
Language: English
Sponsor: N/A
Authoring Institution: N/A
Identifiers - Location: Netherlands
Grant or Contract Numbers: N/A