Human Performance on the Traveling Salesman and Related Problems: A Review
---
paper_title: Optimisation of man‐on‐board automated storage/retrieval systems

paper_content:

This study is concerned with evaluating the performance of different storage policies and tour construction procedures for multi‐command picking using automated storage‐retrieval systems (AS/RS). The AS/RS machine travel time for each storage policy is derived as a function of the shape of the storage area, the number of picking points and the sequencing algorithm used. The combination of these variables yields various solutions to the problem, thus providing a useful guide in designing effective picking systems. The average travel time of the AS/RS in each configuration is calculated by computer simulation in a full factorial experimental design. A subset of the results derived from this study has been successfully implemented in a case study, involving the BMW AG Italy spare parts distribution warehouse.
---
paper_title: The Traveling Salesman Problem A Computational Study

paper_content:

Thank you very much for downloading the traveling salesman problem a computational study. Maybe you have knowledge that, people have look hundreds times for their favorite novels like this the traveling salesman problem a computational study, but end up in harmful downloads. Rather than reading a good book with a cup of tea in the afternoon, instead they juggled with some malicious virus inside their computer.
---
paper_title: Large travelling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation

paper_content:

Determining efficient sequences of X-ray diffraction measurements on a four-circle diffractometer leads to extremely large traveling salesman problems. Simple TSP heuristics give substantial improvements in utilization at small computational expense. Furthermore, the Lin-Kernighan heuristic consistently produces near-optimal sequences.
---
paper_title: Human Performance on Visually Presented Traveling Salesperson Problems with Varying Numbers of Nodes

paper_content:

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.
---
paper_title: Human performance on the traveling salesman problem

paper_content:

Two experiments on performance on the traveling salesman problem (TSP) are reported. The TSP consists of finding the shortest path through a set of points, returning to the origin. It appears to be an intransigent mathematical problem, and heuristics have been developed to find approximate solutions. The first experiment used 10-point, the second, 20-point problems. The experiments tested the hypothesis that complexity of TSPs is a function of number of nonboundary points, not total number of points. Both experiments supported the hypothesis. The experiments provided information on the quality of subjects’ solutions. Their solutions clustered close to the best known solutions, were an order of magnitude better than solutions produced by three well-known heuristics, and on average fell beyond the 99.9th percentile in the distribution of random solutions. The solution process appeared to be perceptually based.
---
paper_title: The role of cognitive maps in spatial decisions

paper_content:

Abstract The traveling salesman's problem, in which one decides which order between n locations minimizes total travel distance, was used as a laboratory analogue of spatial decisions in large-scale environments. In an experiment in which university students were observed while solving this problem, a group who received numerical information about distances between locations was found to minimize local distances rather than total distance, that is, to choose first the closest location from the starting location, then the closest location from that chosen, and so forth. However, if a picture of the locations was presented, total distance was minimized more frequently than local distances, presumably because subjects changed their decisions which minimized local distances when they discovered spatial patterns indicating that a shorter path existed. It was also found that a picture did not always have to be presented because subjects mentally constructed a functionally equivalent spatial representation from pieces of direction and distance or only direction information. This finding was even clearer when subjects were allowed to draw pictures of the locations.
---
paper_title: Individual Differences in Optimization Problem Solving: Reconciling Conflicting Results

paper_content:

Results on human performance on the Traveling Salesman Problem (TSP) from different laboratories show high consistency. However, one exception is in the area of individual differences. While one research group has consistently failed to fi nd systematic individual differences across instances of TSPs (Chronicle, MacGregor and Ormerod), another group (Vickers, Lee and associates) has found individual differences both within TSP performance and between TSP performance and other cognitive tasks. Among possible reasons for the confl icting results are differences in procedure and differences in the problem in- stances used. To try to resolve the discrepancy, we collected data on TSP performance by combining the procedure used by one group with problem instances used by the other. The comparison involved nine 30-node and nine 40-node TSP problems previously used by the Vickers group, using computer presentation. Here, we had the same problems completed by 112 participants using a paper-and-pencil mode of presentation. We ex- amined the results in the form of distributions of correlations across individuals for each pair of problems of the same size. The distributions for the computer and paper forms of presentation were very similar, and centered between correlations of 0.20 and 0.30. The results indicated the presence of individual differences at a level that fell between those previously reported by the two laboratories. The pattern of results indicated that previ- ous discrepancies did not arise because of differences in procedure. Instead, individual differences appeared to become more prevalent as the diffi culty of problems increased. The results are consistent with an explanation that performance on simpler instances is
---
paper_title: Are Individual Differences in Performance on Perceptual and Cognitive Optimization Problems Determined by General Intelligence?

paper_content:

Studies of human problem solving have traditionally used deterministic tasks that require the execution of a systematic series of steps to reach a rational and optimal solution. Most real-world problems, however, are characterized by uncertainty, the need to consider an enormous number of variables and possible courses of action at each stage in solving the problem, and the need to optimize the solution subject to multiple interacting constraints. There are reliable individual differences in people’s abilities to solve such realistic problems. It also seems likely that people’s ability to solve these difficult problems reflects, or depends on, their intelligence. We report on a study of N = 101 adults who completed a series of visual optimization problems (Traveling Salesperson, Minimum Spanning Tree, and Generalized Steiner Tree Problems), as well as a cognitive optimization problem (a version of the Secretary Problem). We also characterized these individuals along three relevant and important cognitive abilities dimensions—fluid ability, visuo-spatial ability, and cognitive processing speed. Modeling of covariance structures indicated that performance on both types of optimization problems relies on general intelligence and raises the possibility that they can be used to assess intelligence.
---
paper_title: The traveling salesman problem: A hierarchical model

paper_content:

Our review of prior literature on spatial information processing in perception, attention, and memory indicates that these cognitive functions involve similar mechanisms based on a hierarchical architecture. The present study extends the application of hierarchical models to the area of problem solving. First, we report results of an experiment in which human subjects were tested on a Euclidean traveling salesman problem (TSP) with 6 to 30 cities. The subject’s solutions were either optimal or near-optimal in length and were produced in a time that was, on average, a linear function of the number of cities. Next, the performance of the subjects is compared with that of five representative artificial intelligence and operations research algorithms, that produce approximate solutions for Euclidean problems. None of these algorithms was found to be an adequate psychological model. Finally, we present a new algorithm for solving the TSP, which is based on a hierarchical pyramid architecture. The performance of this new algorithm is quite similar to the performance of the subjects.
---
paper_title: Global perceptual processing in problem solving: The case of the traveling salesperson

paper_content:

The traveling salesperson problem (TSP) consists of finding the shortest tour around a set of locations and is an important task in computer science and operations research. In four experiments, the relationship between processes implicated in the recognition of good figures and the identification of TSP solutions was investigated. In Experiment 1, a linear relationship was found between participants’ judgments of good figure and the optimality of solutions to TSPs. In Experiment 2, identification performance was shown to be a function of solution optimality and problem orientation. Experiment 3 replicated these findings with a forced-pace method, suggesting that global processing, rather than a local processing strategy involving point-by-point analysis of TSP solutions, is the primary process involved in the derivation of best figures for the presented TSPs. In Experiment 4, the role of global precedence was confirmed using a priming method, in which it was found that short (100 msec) primes facilitated solution identification, relative to no prime or longer primes. Effects of problem type were found in all the experiments, suggesting that local features of some problems may disrupt global processing. The results are discussed in terms of Sanocki’s (1993) global-to-local contingency model. We argue that global perceptual processing may contribute more generally to problem solving and that human performance can complement computational TSP methods.
---
paper_title: Human performance on visually presented Traveling Salesman problems

paper_content:

Abstract Little research has been carried out on human performance in optimization problems, such as the Traveling Salesman problem (TSP). Studies by Polivanova (1974, Voprosy Psikhologii, 4, 41–51) and by MacGregor and Ormerod (1996, Perception & Psychophysics, 58, 527–539) suggest that: (1) the complexity of solutions to visually presented TSPs depends on the number of points on the convex hull; and (2) the perception of optimal structure is an innate tendency of the visual system, not subject to individual differences. Results are reported from two experiments. In the first, measures of the total length and completion speed of pathways, and a measure of path uncertainty were compared with optimal solutions produced by an elastic net algorithm and by several heuristic methods. Performance was also compared under instructions to draw the shortest or the most attractive pathway. In the second, various measures of performance were compared with scores on Raven's advanced progressive matrices (APM). The number of points on the convex hull did not determine the relative optimality of solutions, although both this factor and the total number of points influenced solution speed and path uncertainty. Subjects' solutions showed appreciable individual differences, which had a strong correlation with APM scores. The relation between perceptual organization and the process of solving visually presented TSPs is briefly discussed, as is the potential of optimization for providing a conceptual framework for the study of intelligence.
---
paper_title: Perceptual or Analytical Processing? Evidence from Children's and Adult's Performance on the Euclidean Traveling Salesperson Problem

paper_content:

The Euclidean Traveling Salesperson Problem (E-TSP) is a useful task to study how humans optimize when faced with computational intractability. It has been found that humans are capable of finding high-quality solutions for E-TSP in a relatively short time and with seemingly little cognitive effort. This observation has led to two general proposals: The high quality of performance on E-TSP reflects (a) the output of automatic and innate perceptual processes or (b) a fundamentally intelligent approach to the task by humans. An experiment was performed to compare performance of three age groups (7- year-olds, 12-year-olds, and adults). Our findings provide corroborating evidence that high-level performance on E-TSP is attainable with perceptual processing alone. At the same time, the exceptionally high performance of adult participants suggests that they additionally exploit their cognitive-analytic skills to improve upon what their visual systems provide.
---
paper_title: The role of prefrontal cortex in visuo-spatial planning: a repetitive TMS study

paper_content:

The visuo-spatial planning process is based on an “opportunistic” combination of heuristics and strategies, carried out in small units during the execution of plans. In order to investigate the functional role of the prefrontal cortex in heuristic switching, 42 healthy controls performed a labyrinth crossing task (the Maps Test). During this computerized version of the Travelling Salesperson Problem, subjects had to decide which order of locations optimizes total travel time and distance. This task was performed with and without 1 Hz repetitive transcranial magnetic stimulation (rTMS), which exerts an inhibitory action on the targeted area, applied during the task over bilateral frontal sites (active stimulation) and parieto-occipital site (sham stimulation). Only repetitive bilateral rTMS over F3 and F4 significantly decreased the number of strategies with changes of heuristics, and increased the number of movements required to solve the task. This behaviour contrasts with the performance of healthy subjects in the planning task, but is consistent with the performance of frontal traumatic brain injury patients. The results indicate that, in a visuo-spatial problem-solving task, the prefrontal cortex is involved in the switching between heuristics during the execution of a plan.
---
paper_title: Human performance on the traveling salesman problem

paper_content:

Two experiments on performance on the traveling salesman problem (TSP) are reported. The TSP consists of finding the shortest path through a set of points, returning to the origin. It appears to be an intransigent mathematical problem, and heuristics have been developed to find approximate solutions. The first experiment used 10-point, the second, 20-point problems. The experiments tested the hypothesis that complexity of TSPs is a function of number of nonboundary points, not total number of points. Both experiments supported the hypothesis. The experiments provided information on the quality of subjects’ solutions. Their solutions clustered close to the best known solutions, were an order of magnitude better than solutions produced by three well-known heuristics, and on average fell beyond the 99.9th percentile in the distribution of random solutions. The solution process appeared to be perceptually based.
---
paper_title: The role of cognitive maps in spatial decisions

paper_content:

Abstract The traveling salesman's problem, in which one decides which order between n locations minimizes total travel distance, was used as a laboratory analogue of spatial decisions in large-scale environments. In an experiment in which university students were observed while solving this problem, a group who received numerical information about distances between locations was found to minimize local distances rather than total distance, that is, to choose first the closest location from the starting location, then the closest location from that chosen, and so forth. However, if a picture of the locations was presented, total distance was minimized more frequently than local distances, presumably because subjects changed their decisions which minimized local distances when they discovered spatial patterns indicating that a shorter path existed. It was also found that a picture did not always have to be presented because subjects mentally constructed a functionally equivalent spatial representation from pieces of direction and distance or only direction information. This finding was even clearer when subjects were allowed to draw pictures of the locations.
---
paper_title: Visuospatial planning in the travelling salesperson problem: a connectionist account of normal and impaired performance.

paper_content:

Planning is a fundamental cognitive function frequently employed in common daily activities. The Travelling Salesperson Problem (TSP), in which participants decide what order between a number of locations optimizes total travel distance, is a paradigm that allows the study of planning and strategy choice. In the TSP, subjects adopt visuo-spatial heuristics to perform the task and operate a continuous monitoring to adapt their behaviour. We present a connectionist model of the TSP that simulates bottom-up and top-down influences observed in the execution of the task. The model accounts for the continuous monitoring observed in healthy participants, and, after a simulated lesion, it also accounts for the decrease of heuristic switching observed in frontal patients and in normal subjects under repetitive transcranial magnetic stimulation (rTMS) over frontal lobe.
---
paper_title: Planning times during traveling salesman's problem: Differences between closed head injury and normal subjects

paper_content:

We studied planning behavior in a group of normal subjects and a group of closed head injury patients (CHI). A computerized version of the traveling salesman's problem was used as a visuospatial planning ability task. The program collected measurements of partial times, number of moves, and number of skipped subgoals. These measures allow us to calculate a “planning index” of subjects' planning ability. Results show that CHI patients present limitations in the planning process due to the lack of ongoing planning.
---
paper_title: Heuristic rules for sequential spatial decisions

paper_content:

Abstract One problem faced by individuals on a frequent basis is that of simultaneously making several spatial decisions, as manifested in, for instance, choices of travel destinations entailed by multistop trips. Rather than deriving optimal solutions, descriptive models of such decisions need to be developed on the basis of empirical observations of how they are actually made. The small amount of available research has identified the use of several simplifying heuristics. The focus of this paper is to examine the use of additional heuristics, such as the formation of clusters of locations as part of the decision-making process. Data from experiments with human subjects solving fictitious spatial-choice problems are presented. The results are classified on the basis of several criteria, and, as such, support the notion that subjects use a limited number of heuristics to plan a route and, furthermore, that the choice of the heuristics depends on the parameters of the search space.
---
paper_title: Human performance on visually presented Traveling Salesman problems

paper_content:

Abstract Little research has been carried out on human performance in optimization problems, such as the Traveling Salesman problem (TSP). Studies by Polivanova (1974, Voprosy Psikhologii, 4, 41–51) and by MacGregor and Ormerod (1996, Perception & Psychophysics, 58, 527–539) suggest that: (1) the complexity of solutions to visually presented TSPs depends on the number of points on the convex hull; and (2) the perception of optimal structure is an innate tendency of the visual system, not subject to individual differences. Results are reported from two experiments. In the first, measures of the total length and completion speed of pathways, and a measure of path uncertainty were compared with optimal solutions produced by an elastic net algorithm and by several heuristic methods. Performance was also compared under instructions to draw the shortest or the most attractive pathway. In the second, various measures of performance were compared with scores on Raven's advanced progressive matrices (APM). The number of points on the convex hull did not determine the relative optimality of solutions, although both this factor and the total number of points influenced solution speed and path uncertainty. Subjects' solutions showed appreciable individual differences, which had a strong correlation with APM scores. The relation between perceptual organization and the process of solving visually presented TSPs is briefly discussed, as is the potential of optimization for providing a conceptual framework for the study of intelligence.
---
paper_title: Convex Hull and Tour Crossings in the Euclidean Traveling Salesperson Problem: Implications for Human Performance Studies

paper_content:

Recently there has been growing interest among psychologists in human performance on the Euclidean traveling salesperson problem (E-TSP). A debate has been initiated on what strategy people use in solving visually presented E-TSP instances. The most prominent hypothesis is the convex-hull hypothesis, originally proposed by MacGregor and Ormerod (1996). We argue that, in the literature so far, there is no evidence for this hypothesis. Alternatively we propose and motivate the hypothesis that people aim at avoiding crossings.
---
paper_title: Gender differences in visuospatial planning: An eye movements study

paper_content:

Gender studies report a male advantage in several visuospatial abilities. Only few studies however, have evaluated differences in visuospatial planning behaviour with regard to gender. This study was aimed at exploring whether gender may affect the choice of cognitive strategies in a visuospatial planning task and, if oculomotor measures could assist in disentangling the cognitive processes involved. A computerised task based on the travelling salesperson problem paradigm, the Maps test, was used to investigate these issues. Participants were required to optimise time and space of a path travelling among a set of sub-goals in a spatially constrained environment. Behavioural results suggest that there are no gender differences in the initial visual processing of the stimuli, but rather during the execution of the plan, with males showing a shorter execution time and a higher path length optimisation than females. Males often showed changes of heuristics during the execution while females seemed to prefer a constant strategy. Moreover, a better performance in behavioural and oculomotor measures seemed to suggest that males are more able than females in either the optimisation of spatial features or the realisation of the planned scheme. Despite inconclusive findings, the results support previous research and provide insight into the level of cognitive processing involved in navigation and planning tasks, with regard to the influence of gender.
---
paper_title: Human performance on the traveling salesman problem

paper_content:

Two experiments on performance on the traveling salesman problem (TSP) are reported. The TSP consists of finding the shortest path through a set of points, returning to the origin. It appears to be an intransigent mathematical problem, and heuristics have been developed to find approximate solutions. The first experiment used 10-point, the second, 20-point problems. The experiments tested the hypothesis that complexity of TSPs is a function of number of nonboundary points, not total number of points. Both experiments supported the hypothesis. The experiments provided information on the quality of subjects’ solutions. Their solutions clustered close to the best known solutions, were an order of magnitude better than solutions produced by three well-known heuristics, and on average fell beyond the 99.9th percentile in the distribution of random solutions. The solution process appeared to be perceptually based.
---
paper_title: Who Solved the Secretary Problem

paper_content:

In Martin Gardner's Mathematical Games column in the February 1960 issue of Scientific American, there appeared a simple problem that has come to be known today as the Secretary Problem, or the Marriage Problem. It has since been taken up and developed by many eminent probabilists and statisticians and has been extended and generalized in many different directions so that now one can say that it constitutes a "field" within mathematics-probability-optimization. The object of this article is partly historical (to give a fresh view of the origins of the problem, touching upon Cayley and Kepler), partly review of the field (listing the subfields of recent interest), partly serious (to answer the question posed in the title), and partly entertainment. The contents of this paper were first given as the Allen T. Craig lecture at the University of Iowa, 1988.
---
paper_title: Individual Differences in Optimization Problem Solving: Reconciling Conflicting Results

paper_content:

Results on human performance on the Traveling Salesman Problem (TSP) from different laboratories show high consistency. However, one exception is in the area of individual differences. While one research group has consistently failed to fi nd systematic individual differences across instances of TSPs (Chronicle, MacGregor and Ormerod), another group (Vickers, Lee and associates) has found individual differences both within TSP performance and between TSP performance and other cognitive tasks. Among possible reasons for the confl icting results are differences in procedure and differences in the problem in- stances used. To try to resolve the discrepancy, we collected data on TSP performance by combining the procedure used by one group with problem instances used by the other. The comparison involved nine 30-node and nine 40-node TSP problems previously used by the Vickers group, using computer presentation. Here, we had the same problems completed by 112 participants using a paper-and-pencil mode of presentation. We ex- amined the results in the form of distributions of correlations across individuals for each pair of problems of the same size. The distributions for the computer and paper forms of presentation were very similar, and centered between correlations of 0.20 and 0.30. The results indicated the presence of individual differences at a level that fell between those previously reported by the two laboratories. The pattern of results indicated that previ- ous discrepancies did not arise because of differences in procedure. Instead, individual differences appeared to become more prevalent as the diffi culty of problems increased. The results are consistent with an explanation that performance on simpler instances is
---
paper_title: Are Individual Differences in Performance on Perceptual and Cognitive Optimization Problems Determined by General Intelligence?

paper_content:

Studies of human problem solving have traditionally used deterministic tasks that require the execution of a systematic series of steps to reach a rational and optimal solution. Most real-world problems, however, are characterized by uncertainty, the need to consider an enormous number of variables and possible courses of action at each stage in solving the problem, and the need to optimize the solution subject to multiple interacting constraints. There are reliable individual differences in people’s abilities to solve such realistic problems. It also seems likely that people’s ability to solve these difficult problems reflects, or depends on, their intelligence. We report on a study of N = 101 adults who completed a series of visual optimization problems (Traveling Salesperson, Minimum Spanning Tree, and Generalized Steiner Tree Problems), as well as a cognitive optimization problem (a version of the Secretary Problem). We also characterized these individuals along three relevant and important cognitive abilities dimensions—fluid ability, visuo-spatial ability, and cognitive processing speed. Modeling of covariance structures indicated that performance on both types of optimization problems relies on general intelligence and raises the possibility that they can be used to assess intelligence.
---
paper_title: Intelligence and individual differences in performance on three types of visually presented optimisation problems

paper_content:

Although problem solving is an essential expression of intelligence, both experimental and differential psychology have neglected an important class of problems, for which it is difficult or impossible for systematic procedures to provide a definitive solution. Two experiments are described, in which participants’ solutions to three computationally difficult problems (a Travelling Salesperson, a Minimal Spanning Tree, and a Generalised Steiner Tree problem) all showed consistent individual differences that intercorrelated reliably and correlated moderately with scores on Raven’s Advanced Progressive Matrices. The results are interpreted in terms of a theory of visual perception based on the efficient use of information about the relative position of stimulus elements. # 2003 Elsevier Ltd. All rights reserved.
---
paper_title: Perceptual or Analytical Processing? Evidence from Children's and Adult's Performance on the Euclidean Traveling Salesperson Problem

paper_content:

The Euclidean Traveling Salesperson Problem (E-TSP) is a useful task to study how humans optimize when faced with computational intractability. It has been found that humans are capable of finding high-quality solutions for E-TSP in a relatively short time and with seemingly little cognitive effort. This observation has led to two general proposals: The high quality of performance on E-TSP reflects (a) the output of automatic and innate perceptual processes or (b) a fundamentally intelligent approach to the task by humans. An experiment was performed to compare performance of three age groups (7- year-olds, 12-year-olds, and adults). Our findings provide corroborating evidence that high-level performance on E-TSP is attainable with perceptual processing alone. At the same time, the exceptionally high performance of adult participants suggests that they additionally exploit their cognitive-analytic skills to improve upon what their visual systems provide.
---
paper_title: Human performance on the traveling salesman problem

paper_content:

Two experiments on performance on the traveling salesman problem (TSP) are reported. The TSP consists of finding the shortest path through a set of points, returning to the origin. It appears to be an intransigent mathematical problem, and heuristics have been developed to find approximate solutions. The first experiment used 10-point, the second, 20-point problems. The experiments tested the hypothesis that complexity of TSPs is a function of number of nonboundary points, not total number of points. Both experiments supported the hypothesis. The experiments provided information on the quality of subjects’ solutions. Their solutions clustered close to the best known solutions, were an order of magnitude better than solutions produced by three well-known heuristics, and on average fell beyond the 99.9th percentile in the distribution of random solutions. The solution process appeared to be perceptually based.
---
paper_title: Spatial and contextual factors in human performance on the travelling salesperson problem

paper_content:

The travelling salesperson problem (TSP) provides a realistic and practical example of a visuo-spatial problem-solving task. In previous research, we have found that the quality of solutions produced by human participants for small TSPs compares well with solutions from a range of computer algorithms. We have proposed that the ability of participants to find solutions reflects the natural properties of human perception, solutions being found through global perceptual processing of the problem array to extract a best figure from the TSP points. In this paper, we extend the study of human performance on the task in order to understand further how human abilities are utilised in solving real-world TSPs. The results of experiment 1 show that high levels of solution quality are maintained in solving larger TSPs than had been investigated previously with human participants, and that the presence of an implied real-world context in the problems has no effect upon performance. Experiment 2 demonstrated that the presence of regularity in the point layout of a TSP can facilitate performance. This was confirmed in experiment 3, where effects of the internality of point clusters were also found. All three experiments were consistent with a global, perceptually based approach to the problem by participants. We suggest that the role of perceptual processing in spatial problem-solving is an important area for further research in both theoretical and applied domains.
---
paper_title: The importance of the convex hull for human performance on the traveling salesman problem: A comment on MacGregor and Ormerod (1996)

paper_content:

MacGregor and Ormerod (1996) have presented results purporting to show that human performance on visually presented traveling salesman problems, as indexed by a measure of response uncertainty, is strongly determined by the number of points in the stimulus array falling inside the convex hull, as distinct from the total number of points. It is argued that this conclusion is artifactually determined by their constrained procedure for stimulus construction, and, even if true, would be limited to arrays with fewer than around 50 points.
---
paper_title: A model of human performance on the traveling salesperson problem

paper_content:

A computational model is proposed of how humans solve the traveling salesperson problem (TSP). Tests of the model are reported, using human performance measures from a variety of 10-, 20-, 40-, and 60-node problems, a single 48-node problem, and a single 100-node problem. The model provided a range of solutions that approximated the range of human solutions and conformed closely to quantitative and qualitative characteristics of human performance. The minimum path lengths of subjects and model deviated by average absolute values of 0.0%, 0.9%, 2.4%, 1.4%, 3.5%, and 0.02% for the 10-, 20-, 40-, 48-, 60-, and 100-node problems, respectively. Because the model produces a range of solutions, rather than a single solution, it may find better solutions than some conventional heuristic algorithms for solving TSPs, and comparative results are reported that support this suggestion.
---
paper_title: Global perceptual processing in problem solving: The case of the traveling salesperson

paper_content:

The traveling salesperson problem (TSP) consists of finding the shortest tour around a set of locations and is an important task in computer science and operations research. In four experiments, the relationship between processes implicated in the recognition of good figures and the identification of TSP solutions was investigated. In Experiment 1, a linear relationship was found between participants’ judgments of good figure and the optimality of solutions to TSPs. In Experiment 2, identification performance was shown to be a function of solution optimality and problem orientation. Experiment 3 replicated these findings with a forced-pace method, suggesting that global processing, rather than a local processing strategy involving point-by-point analysis of TSP solutions, is the primary process involved in the derivation of best figures for the presented TSPs. In Experiment 4, the role of global precedence was confirmed using a priming method, in which it was found that short (100 msec) primes facilitated solution identification, relative to no prime or longer primes. Effects of problem type were found in all the experiments, suggesting that local features of some problems may disrupt global processing. The results are discussed in terms of Sanocki’s (1993) global-to-local contingency model. We argue that global perceptual processing may contribute more generally to problem solving and that human performance can complement computational TSP methods.
---
paper_title: Convex hull or crossing avoidance? Solution heuristics in the travelling salesperson problem

paper_content:

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 that 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 ofinterior 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.
---
paper_title: Convex Hull and Tour Crossings in the Euclidean Traveling Salesperson Problem: Implications for Human Performance Studies

paper_content:

Recently there has been growing interest among psychologists in human performance on the Euclidean traveling salesperson problem (E-TSP). A debate has been initiated on what strategy people use in solving visually presented E-TSP instances. The most prominent hypothesis is the convex-hull hypothesis, originally proposed by MacGregor and Ormerod (1996). We argue that, in the literature so far, there is no evidence for this hypothesis. Alternatively we propose and motivate the hypothesis that people aim at avoiding crossings.
---
paper_title: Global vs. local information processing in visual/spatial problem solving: The case of traveling salesman problem

paper_content:

Human visual/spatial problem solving often requires both global and local information to be processed. But the relationship between those two kinds of information and the way in which they interact with one another during problem solving has not been thoroughly discussed. In the particular setting of solving the traveling salesman problem (TSP), we investigated into the relative roles of global and local information processing. An experiment was conducted to measure the importance of global information and the possible constraints of global information processing on search. A model was built to simulate human TSP performance and was used to investigate further the relationship between global information processing and local information processing. Our model was compared with the human data we collected and with other models of human TSP solving.
---
paper_title: Traveling Salesman Problem: a Foveating Pyramid Model

paper_content:

We tested human performance on the Euclidean Traveling Salesman Problem using problems with 6–50 cities. Results confirmed our earlier findings that: (a) the time of solving a problem is proportional to the number of cities, and (b) the solution error grows very slowly with the number of cities. We formulated a new version of a pyramid model. The new model has an adaptive spatial structure, and it simulates visual acuity and visual attention. Specifically, the model solves the E-TSP problem sequentially by moving attention from city to city, the same way human subjects do. The model includes a parameter representing the magnitude of local search. This parameter allows modeling individual differences among the subjects. The computational complexity of the current implementation of the model is O(n 2 ), but this can most likely be improved to O[nlog(n)]. Simulation experiments demonstrated psychological plausibility of the new model.
---
paper_title: The traveling salesman problem: A hierarchical model

paper_content:

Our review of prior literature on spatial information processing in perception, attention, and memory indicates that these cognitive functions involve similar mechanisms based on a hierarchical architecture. The present study extends the application of hierarchical models to the area of problem solving. First, we report results of an experiment in which human subjects were tested on a Euclidean traveling salesman problem (TSP) with 6 to 30 cities. The subject’s solutions were either optimal or near-optimal in length and were produced in a time that was, on average, a linear function of the number of cities. Next, the performance of the subjects is compared with that of five representative artificial intelligence and operations research algorithms, that produce approximate solutions for Euclidean problems. None of these algorithms was found to be an adequate psychological model. Finally, we present a new algorithm for solving the TSP, which is based on a hierarchical pyramid architecture. The performance of this new algorithm is quite similar to the performance of the subjects.
---
paper_title: Human performance on the traveling salesman problem

paper_content:

Two experiments on performance on the traveling salesman problem (TSP) are reported. The TSP consists of finding the shortest path through a set of points, returning to the origin. It appears to be an intransigent mathematical problem, and heuristics have been developed to find approximate solutions. The first experiment used 10-point, the second, 20-point problems. The experiments tested the hypothesis that complexity of TSPs is a function of number of nonboundary points, not total number of points. Both experiments supported the hypothesis. The experiments provided information on the quality of subjects’ solutions. Their solutions clustered close to the best known solutions, were an order of magnitude better than solutions produced by three well-known heuristics, and on average fell beyond the 99.9th percentile in the distribution of random solutions. The solution process appeared to be perceptually based.
---
paper_title: The traveling salesman problem: A hierarchical model

paper_content:

Our review of prior literature on spatial information processing in perception, attention, and memory indicates that these cognitive functions involve similar mechanisms based on a hierarchical architecture. The present study extends the application of hierarchical models to the area of problem solving. First, we report results of an experiment in which human subjects were tested on a Euclidean traveling salesman problem (TSP) with 6 to 30 cities. The subject’s solutions were either optimal or near-optimal in length and were produced in a time that was, on average, a linear function of the number of cities. Next, the performance of the subjects is compared with that of five representative artificial intelligence and operations research algorithms, that produce approximate solutions for Euclidean problems. None of these algorithms was found to be an adequate psychological model. Finally, we present a new algorithm for solving the TSP, which is based on a hierarchical pyramid architecture. The performance of this new algorithm is quite similar to the performance of the subjects.
---
paper_title: Some Tours are More Equal than Others: The Convex-Hull Model Revisited with Lessons for Testing Models of the Traveling Salesperson Problem

paper_content:

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.
---
paper_title: Convex hull or crossing avoidance? Solution heuristics in the travelling salesperson problem

paper_content:

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 that 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 ofinterior 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.
---
paper_title: Convex Hull and Tour Crossings in the Euclidean Traveling Salesperson Problem: Implications for Human Performance Studies

paper_content:

Recently there has been growing interest among psychologists in human performance on the Euclidean traveling salesperson problem (E-TSP). A debate has been initiated on what strategy people use in solving visually presented E-TSP instances. The most prominent hypothesis is the convex-hull hypothesis, originally proposed by MacGregor and Ormerod (1996). We argue that, in the literature so far, there is no evidence for this hypothesis. Alternatively we propose and motivate the hypothesis that people aim at avoiding crossings.
---
paper_title: Global vs. local information processing in visual/spatial problem solving: The case of traveling salesman problem

paper_content:

Human visual/spatial problem solving often requires both global and local information to be processed. But the relationship between those two kinds of information and the way in which they interact with one another during problem solving has not been thoroughly discussed. In the particular setting of solving the traveling salesman problem (TSP), we investigated into the relative roles of global and local information processing. An experiment was conducted to measure the importance of global information and the possible constraints of global information processing on search. A model was built to simulate human TSP performance and was used to investigate further the relationship between global information processing and local information processing. Our model was compared with the human data we collected and with other models of human TSP solving.
---
paper_title: Global vs. local information processing in visual/spatial problem solving: The case of traveling salesman problem

paper_content:

Human visual/spatial problem solving often requires both global and local information to be processed. But the relationship between those two kinds of information and the way in which they interact with one another during problem solving has not been thoroughly discussed. In the particular setting of solving the traveling salesman problem (TSP), we investigated into the relative roles of global and local information processing. An experiment was conducted to measure the importance of global information and the possible constraints of global information processing on search. A model was built to simulate human TSP performance and was used to investigate further the relationship between global information processing and local information processing. Our model was compared with the human data we collected and with other models of human TSP solving.
---
paper_title: Some Tours are More Equal than Others: The Convex-Hull Model Revisited with Lessons for Testing Models of the Traveling Salesperson Problem

paper_content:

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.
---
paper_title: Visuospatial planning in the travelling salesperson problem: a connectionist account of normal and impaired performance.

paper_content:

Planning is a fundamental cognitive function frequently employed in common daily activities. The Travelling Salesperson Problem (TSP), in which participants decide what order between a number of locations optimizes total travel distance, is a paradigm that allows the study of planning and strategy choice. In the TSP, subjects adopt visuo-spatial heuristics to perform the task and operate a continuous monitoring to adapt their behaviour. We present a connectionist model of the TSP that simulates bottom-up and top-down influences observed in the execution of the task. The model accounts for the continuous monitoring observed in healthy participants, and, after a simulated lesion, it also accounts for the decrease of heuristic switching observed in frontal patients and in normal subjects under repetitive transcranial magnetic stimulation (rTMS) over frontal lobe.
---
paper_title: Heuristic rules for sequential spatial decisions

paper_content:

Abstract One problem faced by individuals on a frequent basis is that of simultaneously making several spatial decisions, as manifested in, for instance, choices of travel destinations entailed by multistop trips. Rather than deriving optimal solutions, descriptive models of such decisions need to be developed on the basis of empirical observations of how they are actually made. The small amount of available research has identified the use of several simplifying heuristics. The focus of this paper is to examine the use of additional heuristics, such as the formation of clusters of locations as part of the decision-making process. Data from experiments with human subjects solving fictitious spatial-choice problems are presented. The results are classified on the basis of several criteria, and, as such, support the notion that subjects use a limited number of heuristics to plan a route and, furthermore, that the choice of the heuristics depends on the parameters of the search space.
---
paper_title: Chimpanzee Spatial Memory Organization

paper_content:

Juvenile chimpanzees, carried around an outdoor field and shown up to 18 randomly placed hidden foods, remembered most of these hiding places and the type of food that was in each. Their search pattern approximated an optimum routing, and they rarely rechecked a place they had already emptied of food.
---
paper_title: Pigeons and People Select Efficient Routes When Solving a One-Way "Traveling Salesperson" Task

paper_content:

The authors presented people (Experiment 1) and pigeons (Experiments 2 and 3) with a large number of 1-way traveling salesperson problems that consisted of 3, 4, and 5 identical stimuli (nodes) on a computer monitor. The sequence of nodes that each traveler selected was recorded, and the distance of the route was subsequently determined. The routes the pigeons and people selected were reliably more efficient than those used by a Monte Carlo model given the same problems. The pigeons’ routes were significantly less efficient than a nearest neighbor model of performance, however. In Experiment 3, pigeons were required to select a route that was within the top 33% of all possible solutions for a given problem. The pigeons’ solutions were significantly more efficient than those observed in Experiment 2, in which the behavioral criterion was not imposed. The mechanisms that pigeons and people may have been using to solve the traveling salesperson problems are discussed.
---
paper_title: Optimal foraging and the traveling salesman

paper_content:

Abstract Optimal foraging models are examined that assume animals forage for discrete point resources on a plane and attempt to minimize their travel distance between resources. This problem is similar to the well-known traveling salesman problem: A salesman must choose the shortest path from his home office to all cities on his itinerary and back to his home office again. The traveling salesman problem is in a class of enigmatic problems, called NP-complete, which can be so difficult to solve that animals might be incapable of finding the best solution. Two major results of this analysis are: (1) The simple foraging strategy of always moving to the closest resource site does surprisingly well. More sophisticated strategies of “looking ahead” a small number of steps, choosing the shortest path, then taking a step, do worse if all the resource sites are visited, but do slightly better (less than 10%) if not all the resource sites are visited. (2) Short cyclical foraging routes resulted when resources were allowed to renew. This is suggested as an alternative explanation for “trap-lining” in animals that forage for discrete, widely separated resources.
---
paper_title: Distance Minimization in Downtown Pedestrian Shopping

paper_content:

Downtown pedestrian shopping was observed with the purpose of determining whether shoppers attempted to minimize walking distance, and, if so, whether, as has been suggested in previous research, they did that by successively choosing the closest locations. In downtown of an average-sized Swedish city (about 80 000 residents), 150 shoppers were interviewed in a parking lot when they were coming back from shopping rounds. 69% of the shoppers visited more than one location, and 51% visited more than two locations. Of those who visited more than two different locations, 35 (69%) attempted to minimize walking distance. This was most frequently done by first choosing the location farthest away, then minimizing distance successively back to the parking lot. In this way shoppers probably attempted to minimize both the walking distance and the effort to carry goods. Some shoppers managed to choose routes which were shorter than if they had minimized distance successively. This finding was consistent with the results of laboratory studies demonstrating the role of maplike mental representations for distance-minimizing choices.
---
paper_title: The role of prefrontal cortex in visuo-spatial planning: a repetitive TMS study

paper_content:

The visuo-spatial planning process is based on an “opportunistic” combination of heuristics and strategies, carried out in small units during the execution of plans. In order to investigate the functional role of the prefrontal cortex in heuristic switching, 42 healthy controls performed a labyrinth crossing task (the Maps Test). During this computerized version of the Travelling Salesperson Problem, subjects had to decide which order of locations optimizes total travel time and distance. This task was performed with and without 1 Hz repetitive transcranial magnetic stimulation (rTMS), which exerts an inhibitory action on the targeted area, applied during the task over bilateral frontal sites (active stimulation) and parieto-occipital site (sham stimulation). Only repetitive bilateral rTMS over F3 and F4 significantly decreased the number of strategies with changes of heuristics, and increased the number of movements required to solve the task. This behaviour contrasts with the performance of healthy subjects in the planning task, but is consistent with the performance of frontal traumatic brain injury patients. The results indicate that, in a visuo-spatial problem-solving task, the prefrontal cortex is involved in the switching between heuristics during the execution of a plan.
---
paper_title: Visuospatial planning in the travelling salesperson problem: a connectionist account of normal and impaired performance.

paper_content:

Planning is a fundamental cognitive function frequently employed in common daily activities. The Travelling Salesperson Problem (TSP), in which participants decide what order between a number of locations optimizes total travel distance, is a paradigm that allows the study of planning and strategy choice. In the TSP, subjects adopt visuo-spatial heuristics to perform the task and operate a continuous monitoring to adapt their behaviour. We present a connectionist model of the TSP that simulates bottom-up and top-down influences observed in the execution of the task. The model accounts for the continuous monitoring observed in healthy participants, and, after a simulated lesion, it also accounts for the decrease of heuristic switching observed in frontal patients and in normal subjects under repetitive transcranial magnetic stimulation (rTMS) over frontal lobe.
---
paper_title: Planning times during traveling salesman's problem: Differences between closed head injury and normal subjects

paper_content:

We studied planning behavior in a group of normal subjects and a group of closed head injury patients (CHI). A computerized version of the traveling salesman's problem was used as a visuospatial planning ability task. The program collected measurements of partial times, number of moves, and number of skipped subgoals. These measures allow us to calculate a “planning index” of subjects' planning ability. Results show that CHI patients present limitations in the planning process due to the lack of ongoing planning.
---
paper_title: Center of mass perception and inertial frames of reference.

paper_content:

Center of mass perception was investigated by varying the shape, size, and orientation of planar objects. Shape was manipulated to investigate symmetries as information. The number of reflective symmetry axes, the amount of rotational symmetry, and the presence of radial symmetry were varied. Orientation affected systematic errors. Judgments tended to undershoot the center of mass. Random errors increased with size and decreased with symmetry. Size had no effect on random errors for maximally symmetric objects, although orientation did. The spatial distributions of judgments were elliptical. Distribution axes were found to align with the principle moments of inertia. Major axes tended to align with gravity in maximally symmetric objects. A functional and physical account was given in terms of the repercussions of error. Overall, judgments were very accurate.
---
paper_title: Convex hull or crossing avoidance? Solution heuristics in the travelling salesperson problem

paper_content:

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 that 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 ofinterior 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.
---

```plaintext
Title: Human Performance on the Traveling Salesman and Related Problems: A Review

Section 1: What Are Combinatorial Optimization Problems?
Description 1: Overview of combinatorial optimization problems and the complexity related to finding optimal solutions.

Section 2: The Standard TSP
Description 2: Examination of human performance on the Traveling Salesman Problem (TSP) and the factors influencing it.

Section 3: Related Problems
Description 3: Analysis of variations of the TSP and other related optimization problems.

Section 4: Instructional Variants of TSPs
Description 4: Discussion on how different instructions can affect human performance on TSPs.

Section 5: Other Optimization Tasks
Description 5: Exploration of human performance on optimization problems other than the TSP.

Section 6: Theoretical Accounts of Human Performance
Description 6: Review of theoretical models proposed to explain human performance on the TSP and similar tasks.

Section 7: Broader Developments
Description 7: Overview of the application of TSP-related studies in various fields, including animal studies, spatial cognition, and neuropsychology.

Section 8: Future Directions
Description 8: Future research directions and challenges in studying human performance on optimization problems.
```