—The Traveling Salesman Goes Shopping: The Systematic Deviations of Grocery Paths from TSP Optimality
AbstractWe 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 (i.e., not following the TSP-order of category purchases), and the additional distance because of (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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by INFORMS in its journal Marketing Science.
Volume (Year): 28 (2009)
Issue (Month): 3 (05-06)
traveling salesman problem; grocery shopping path; path data optimality;
You can help add them by filling out this form.
reading list or among the top items on IDEAS.Access and download statisticsgeneral information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc).
If references are entirely missing, you can add them using this form.