Convex hull and tour crossings in the Euclidean traveling salesperson problem: Implications for human performance studies

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.     

Spatial and contextual factors in human performance on the travelling salesperson problem

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.     

The verbalization of multiple strategies in a variant of the traveling salesperson problem

What kinds of strategies do humans employ when confronted with a complex spatial task, and how do they verbalize these strategies? Previous research concerned with the well-known traveling salesperson problem (TSP) typically aimed at the identification of a generally applicable heuristics that adequately represents human behavior in relation to the abstract task of combining points. This paper adopts a novel perspective in two respects. On the one hand, it addresses the strategies people employ when confronted with a more complex task, involving distractors and feature information rather than identical points. On the other hand, retrospective linguistic representations of the strategies used are analyzed in relation to the behavioral data, using discourse analytic methods. Results show that both the behavioral results and the verbalizations point to a range of strategies related to those proposed for solving abstract TSPs. However, in contrast to earlier accounts in the literature, the participants employ a repertory of multi-faceted strategies and planning processes, simplifying and structuring the problem space across subtasks and processes in flexible ways. These findings provide further insight into the nature of human strategies in spatial problem solving tasks and their retrospective verbalization, highlighting how procedures generally known in the literature may be adapted to more complex tasks, and how they may be verbalized spontaneously.     

Global perceptual processing in problem solving: The case of the traveling salesperson

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.     

Global perceptual processing in problem solving: the case of the traveling salesperson.

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.     

Human performance on the traveling salesman problem

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.     

A comparison of human performance in figural and navigational versions of the traveling salesman problem

Performance on a typical pen-and-paper (figural) version of the Traveling Salesman Problem was compared to performance on a room-sized navigational version of the same task. Nine configurations were designed to examine the use of the nearest-neighbor (NN), cluster approach, and convex-hull strategies. Performance decreased with an increasing number of nodes internal to the hull, and improved when the NN strategy produced the optimal path. There was no overall difference in performance between figural and navigational task modalities. However, there was an interaction between modality and configuration, with evidence that participants relied more heavily on the NN strategy in the figural condition. Our results suggest that participants employed similar, but not identical, strategies when solving figural and navigational versions of the problem. Surprisingly, there was no evidence that participants favored global strategies in the figural version and local strategies in the navigational version.     

The traveling salesman problem: A hierarchical model

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.     

The roles of the convex hull and the number of potential intersections in performance on visually presented traveling salesperson problems

The planar Euclidean version of the traveling salesperson problem requires finding the shortest tour through a two-dimensional array of points. MacGregor and Ormerod (1996) have suggested that people solve such problems by using a global-to-local perceptual organizing process based on the convex hull of the array. We review evidence for and against this idea, before considering an alternative, local-to-global perceptual process, based on the rapid automatic identification of nearest neighbors. We compare these approaches in an experiment in which the effects of number of convex hull points and number of potential intersections on solution performance are measured. Performance worsened with more points on the convex hull and with fewer potential intersections. A measure of response uncertainty was unaffected by the number of convex hull points but increased with fewer potential intersections. We discuss a possible interpretation of these results in terms of a hierarchical solution process based on linking nearest neighbor clusters.     

A longitudinal cross-level model of leader and salesperson influences on sales force technology use and performance

The authors examined the influence of the introduction of a new suite of technology tools on the performance of 592 salespersons. They hypothesized that the salespersons' work experience would have a negative effect on their technology self-efficacy, which in turn would relate positively to their use of technology. Sales performance was hypothesized to be positively related to both past performance and the use of new technology tools. Further, the authors hypothesized that leaders' commitment to sales technology would enhance salespersons' technology self-efficacy and usage, and leaders' empowering behaviors would influence salespersons' technology self-efficacy and moderate the individual-level relationships. Hierarchical linear modeling analyses confirmed all of the hypothesized individual-level relationships and most of the cross-level relationships stemming from average leader behaviors. In particular, empowering leadership exhibited multiple cross-level interactions, as anticipated. Results are discussed in terms of the importance of social-psychological factors related to the success of sales force technology interventions.     

A process model of buyer responses to salesperson transgressions and recovery efforts: the impact of salesperson orientation

Despite the damaging effects often associated with salesperson transgressions, our understanding of how buyers respond to these transgressions and the recovery efforts that typically follow is limited. The authors address this shortcoming across two studies of professional buyers. In the first, the authors examine buyers’ responses to salesperson ethical and service transgressions as moderated by their perceptions of the salesperson (i.e. whether they perceive the salesperson as being selling-oriented (SO) or customer-oriented (CO)). In the second study, the authors contrast the effects of an apology versus compensation in examining buyers’ responses to the overall transgression and recovery episode. Although study results indicate that a customer orientation amplifies buyers’ responses to the initial transgression, they also indicate that buyers’ responses to the overall episode are primarily a function of whether the recovery effort conforms to their expectations. Hence, while favorable salesperson perceptions (i.e. being perceived as CO) are detrimental in the context of the initial transgression, they are beneficial in the context of the overall transgression and recovery episode.     

Evaluating the importance of the convex hull in solving the Euclidean version of the traveling salesperson problem: reply to Lee and Vickers (2000)

Lee and Vickers (2000) suggest that the results of MacGregor and Ormerod (1996), showing that the response uncertainty to traveling salesperson problems (TSPs) increases with increasing numbers of nonboundary points, may have resulted as an artifact of constraints imposed in the construction of stimuli. The fact that similar patterns of results have been obtained for our "constrained" stimuli, for a stimulus constructed under different constraints, for 13 randomly generated stimuli, and for random and patterned 48-point problems provides empirical evidence that the results are not artifactual. Lee and Vickers further suggest that, even if not artifactual, the results are in principle limited to arrays of fewer than 50 points and that, beyond this, the total number of points and number of nonboundary points are "diagnostically equivalent." This claim seems to us incorrect, since arrays of any size can be constructed that will permit experimental tests of whether problem difficulty is influenced by the number of nonboundary points, or the total number of points, or both. We present a reanalysis of our original data using hierarchical regression analysis which indicates that both factors may influence problem complexity.     

The importance of the convex hull for human performance on the traveling salesman problem: a comment on MacGregor and Ormerod (1996)

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.     

A qualitative study of leader behaviors perceived to enable salesperson performance

Abstract

This study builds on and extends previous sales leadership research by exploring sales professionals’ perceptions of effective leadership behaviors. Semistructured interviews with both sales leaders and salespeople working in a global enterprise software company were examined through a qualitative analysis. Results indicated that participants believed sales leadership played an important role in influencing sales performance. When asked to describe specific sales leader behaviors that best enable salesperson performance, sales professionals – both sales leaders and salespeople – overwhelmingly referenced coaching, followed by collaborating, championing, and customer engaging. We define and describe these four key sales leader behaviors and identify four potential mediating variables (trust, confidence, optimism, and resilience), from which emerges a conceptual framework of sales leader behaviors perceived to enable salesperson performance. We examine these four key sales leader behaviors and mediators in the broader context of leadership theory, particularly transformational, servant, authentic, and adaptive leadership theories. The key contribution of this study is the identification of a set of leader behaviors that are likely to be especially effective in modern sales organizations given that they originated from the perceptions of sales professionals themselves.     

Perceived optimality of competing solutions to the Euclidean travelling salesperson problem

The Travelling Salesperson Problem (TSP) is a nondeterministic-polynomial hard (NP-hard) combinatorial problem that occurs in a wide range of industrial domains, including logistics, route finding, and computer wiring. Interestingly, despite the problem’s inherent computational difficulty, when presented in Euclidean space (ETSP), human participants can produce close-to-optimal solutions in near-linear time. However, when asked to compare and select the most optimum solution from a set of pre-defined competing solution options, participants can struggle. In this study we investigate this paradox by asking participants to compare four closed-loop Euclidean TSP solutions, in order to determine which solution they perceived to have the most optimal tour cost. We hypothesise that the extracted geometric properties have an effect on stimulus selection in a discrimination task (selection or no selection). Accordingly, we extracted four geometric properties from competing stimuli in order to create a perceptual activation function. Predictive analytics demonstrated that a classification model could identify the most optimal solution 97% of the time using the perceptual activation scores alone, yet human participants only correctly determined the most optimal solution 47% of the time. Mixed-effects models suggest that ‘likelihood of stimulus selection’ can be modelled as a function of the weighted coefficients of competing perceptual activation scores within each trial; however only a small amount of the variance is explained by these perceptual activation scores. Finally, a drift–diffusion model was used to create a theoretical framework of how likelihood of stimulus selection is influenced by competing perceptual activators. Our study highlights a novel way of extracting and analysing the importance of geometric properties that influence ETSP discrimination tasks, and links this analysis to human behaviour when discriminating between competing ETSP solutions.     

The aesthetic appeal of minimal structures: judging the attractiveness of solutions to traveling salesperson problems

Ormerod and Chronicle (1999) reported that optimal solutions to traveling salesperson problems were judged to be aesthetically more pleasing than poorer solutions and that solutions with more convex hull nodes were rated as better figures. To test these conclusions, solution regularity and the number of potential intersections were held constant, whereas solution optimality, the number of internal nodes, and the number of nearest neighbors in each solution were varied factorially. The results did not support the view that the convex hull is an important determinant of figural attractiveness. Also, in contrast to the findings of Ormerod and Chronicle, there were consistent individual differences. Participants appeared to be divided as to whether the most attractive figure enclosed a given area within a perimeter of minimum or maximum length. It is concluded that future research in this area cannot afford to focus exclusively on group performance measures.     

A production system model for human problem solving

Summary A new production system model was developed for a class of transformation problems, based upon the results of an experiment which evaluated the psychological validity of a noticing order in problem solving. This model specifies how general problem solving heuristics interact with domain knowledge and how possible actions are assembled from externally presented information. The production system may conceptually be divided into three groups: move generation, move evaluation, and move execution productions. The simulation model was evaluated by a second experiment. With a common set of parameter values, good fits were obtained between the predicted and observed data. The significance of individual productions was assessed by running simulations with individual productions deleted. While previous simulations have described subjects' behavior on a single problem, the present model successfully predicted human problem solving in three structurally different problems. The proposed production system thus gives a detailed account of the procedural knowledge that subjects use in transformation problems.     

A hierarchical bayesian model of human decision-making on an optimal stopping problem

We consider human performance on an optimal stopping problem where people are presented with a list of numbers independently chosen from a uniform distribution. People are told how many numbers are in the list, and how they were chosen. People are then shown the numbers one at a time, and are instructed to choose the maximum, subject to the constraint that they must choose a number at the time it is presented, and any choice below the maximum is incorrect. We present empirical evidence that suggests people use threshold-based models to make decisions, choosing the first currently maximal number that exceeds a fixed threshold for that position in the list. We then develop a hierarchical generative account of this model family, and use Bayesian methods to learn about the parameters of the generative process, making inferences about the threshold decision models people use. We discuss the interesting aspects of human performance on the task, including the lack of learning, and the presence of large individual differences, and consider the possibility of extending the modeling framework to account for individual differences. We also use the modeling results to discuss the merits of hierarchical, generative and Bayesian models of cognitive processes more generally.