Home > Research > Publications & Outputs > A comparison of heuristic and human performance...

Research

Associated organisational unit

Electronic data

Links

View graph of relations

A comparison of heuristic and human performance on open versions of the traveling salesperson problem.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

A comparison of heuristic and human performance on open versions of the traveling salesperson problem. / MacGregor, James N.; Chronicle, Edward P.; Ormerod, ThomasC.
In: Journal of Problem Solving, Vol. 1, No. 1, 2006, p. 33-43.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

MacGregor, JN, Chronicle, EP & Ormerod, T 2006, 'A comparison of heuristic and human performance on open versions of the traveling salesperson problem.', Journal of Problem Solving, vol. 1, no. 1, pp. 33-43. <http://docs.lib.purdue.edu/jps/vol1/iss1/5/>

APA

MacGregor, J. N., Chronicle, E. P., & Ormerod, T. (2006). A comparison of heuristic and human performance on open versions of the traveling salesperson problem. Journal of Problem Solving, 1(1), 33-43. http://docs.lib.purdue.edu/jps/vol1/iss1/5/

Vancouver

MacGregor JN, Chronicle EP, Ormerod T. A comparison of heuristic and human performance on open versions of the traveling salesperson problem. Journal of Problem Solving. 2006;1(1):33-43.

Author

MacGregor, James N. ; Chronicle, Edward P. ; Ormerod, ThomasC. / A comparison of heuristic and human performance on open versions of the traveling salesperson problem. In: Journal of Problem Solving. 2006 ; Vol. 1, No. 1. pp. 33-43.

Bibtex

@article{f871ce6c2b864f09aa35292b5e48270c,
title = "A comparison of heuristic and human performance on open versions of the traveling salesperson problem.",
abstract = "We compared the performance of three heuristics with that of subjects on variants of a well-known combinatorial optimization task, the Traveling Salesperson Problem (TSP). The present task consisted of finding the shortest path through an array of points from one side of the array to the other. Like the standard TSP, the task is computationally intractable and, as with the standard TSP, people appear to be able to find good solutions with relative ease. The three heuristics used mechanisms that have been cited as potentially relevant in human performance in the standard task. These were: convex hull, nearest neighbor, and crossing avoidance. We compared heuristic and human performance in terms of lengths of paths, overlap between solutions, and number of crossings. Of the three heuristics, the convex hull appeared to result in the best overall fit with human solutions.",
author = "MacGregor, {James N.} and Chronicle, {Edward P.} and ThomasC. Ormerod",
year = "2006",
language = "English",
volume = "1",
pages = "33--43",
journal = "Journal of Problem Solving",
issn = "1932-6246",
publisher = "Purdue University Press",
number = "1",

}

RIS

TY - JOUR

T1 - A comparison of heuristic and human performance on open versions of the traveling salesperson problem.

AU - MacGregor, James N.

AU - Chronicle, Edward P.

AU - Ormerod, ThomasC.

PY - 2006

Y1 - 2006

N2 - We compared the performance of three heuristics with that of subjects on variants of a well-known combinatorial optimization task, the Traveling Salesperson Problem (TSP). The present task consisted of finding the shortest path through an array of points from one side of the array to the other. Like the standard TSP, the task is computationally intractable and, as with the standard TSP, people appear to be able to find good solutions with relative ease. The three heuristics used mechanisms that have been cited as potentially relevant in human performance in the standard task. These were: convex hull, nearest neighbor, and crossing avoidance. We compared heuristic and human performance in terms of lengths of paths, overlap between solutions, and number of crossings. Of the three heuristics, the convex hull appeared to result in the best overall fit with human solutions.

AB - We compared the performance of three heuristics with that of subjects on variants of a well-known combinatorial optimization task, the Traveling Salesperson Problem (TSP). The present task consisted of finding the shortest path through an array of points from one side of the array to the other. Like the standard TSP, the task is computationally intractable and, as with the standard TSP, people appear to be able to find good solutions with relative ease. The three heuristics used mechanisms that have been cited as potentially relevant in human performance in the standard task. These were: convex hull, nearest neighbor, and crossing avoidance. We compared heuristic and human performance in terms of lengths of paths, overlap between solutions, and number of crossings. Of the three heuristics, the convex hull appeared to result in the best overall fit with human solutions.

M3 - Journal article

VL - 1

SP - 33

EP - 43

JO - Journal of Problem Solving

JF - Journal of Problem Solving

SN - 1932-6246

IS - 1

ER -