NotesFAQContact Us
Collection
Advanced
Search Tips
Peer reviewed Peer reviewed
Direct linkDirect link
ERIC Number: EJ1055679
Record Type: Journal
Publication Date: 2006
Pages: 13
Abstractor: As Provided
Reference Count: 21
ISBN: N/A
ISSN: EISSN-1932-6246
Human Performance on Visually Presented Traveling Salesperson Problems with Varying Numbers of Nodes
Dry, Matthew; Lee, Michael D.; Vickers, Douglas; Hughes, Peter
Journal of Problem Solving, v1 n1 Article 4 p20-32 Fall 2006
We investigated the properties of the distribution of human solution times for Traveling Salesperson Problems (TSPs) with increasing numbers of nodes. New experimental data are presented that measure solution times for carefully chosen representative problems with 10, 20, . . . 120 nodes. We compared the solution times predicted by the convex hull procedure proposed by MacGregor and Ormerod (1996), the hierarchical approach of Graham, Joshi, and Pizlo (2000), and by five algorithms drawn from the artificial intelligence and operations research literature. The most likely polynomial model for describing the relationship between mean solution time and the size of a TSP is linear or near-linear over the range of problem sizes tested, supporting the earlier finding of Graham et al. (2000). We argue the properties of the solution time distributions place strong constraints on the development of detailed models of human performance for TSPs, and provide some evaluation of previously proposed models in light of our findings.
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: http://docs.lib.purdue.edu/jps/
Publication Type: Journal Articles; Reports - Research
Education Level: N/A
Audience: N/A
Language: English
Sponsor: N/A
Authoring Institution: N/A