This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Hui, S. K. Articles by Bradlow, E. T. Search for Related Content

Research Note—The Traveling Salesman Goes Shopping: The Systematic Deviations of Grocery Paths from TSP Optimality

Stern School of Business, New York University, New York 10012
The Wharton School of the University of Pennsylvania, Philadelphia, Pennsylvania 19104
The Wharton School of the University of Pennsylvania, Philadelphia, Pennsylvania 19104
khui{at}stern.nyu.edu
faderp{at}wharton.upenn.edu
ebradlow{at}wharton.upenn.edu

We examine grocery shopping paths using the traveling salesman problem (TSP) as a normative frame of reference. We define the TSP-path for each shopper as the shortest path that connects all of his purchases. We then decompose the length of each observed path into three components: the length of the TSP-path, the additional distance because of order deviation (i.e., not following the TSP-order of category purchases), and the additional distance because of travel deviation (i.e., not following the shortest point-to-point route). We explore the relationship between these deviations and different aspects of in-store shopping/purchase behavior. Among other things, our results suggest that (1) a large proportion of trip length is because of travel deviation; (2) paths that deviate substantially from the TSP solution are associated with larger shopping baskets; (3) order deviation is strongly associated with purchase behavior, while travel deviation is not; and (4) shoppers with paths closer to the TSP solution tend to buy more from frequently purchased product categories.

Key Words: traveling salesman problem; grocery shopping path; path data optimality
History: Received: October 1, 2007; accepted: March 5, 2008.