Some tours are more equal than others : the convex-hull model revisited with lessons for testing models of the traveling salesperson problem

S.W. Tak, M. Plaisier, I. Rooij, van

Research output: Contribution to journalArticleAcademicpeer-review

96 Downloads (Pure)

Abstract

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 confi rmation 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 fi ve 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.
Original languageEnglish
Pages (from-to)4-28
JournalJournal of Problem Solving
Volume2
Issue number1
Publication statusPublished - 2006

Fingerprint

Dive into the research topics of 'Some tours are more equal than others : the convex-hull model revisited with lessons for testing models of the traveling salesperson problem'. Together they form a unique fingerprint.

Cite this