Maximizing the Cost of Shortest Paths between Facilities through Optimal Product Category Locations




Gertin, Thomas

Journal Title

Journal ISSN

Volume Title



A location model is introduced that maximizes the shortest Traveling Salesman Problem (TSP) path between facilities. A scenario has been created where retailers that are interested in designing store layouts wish to maximize the amount of time customers spend in their store. Product location data has been collected from a real supermarket and a representative undirected network has been created. An enumeration method will be used to determine the optimal location of three product categories in the supermarket network. The results contain 5 optimal paths, with an improvement of 32 percent over the store’s existing shortest path. In addition linear programming and heuristics are used to generate solutions and compare the results to the enumeration method. These same methods can be used in other disciplines to optimize product locations or locate undesirable facilities. Future research can test scenarios with additional constraints or find ways to minimize processing time.



Traveling Salesman Problem, Product location, Location science, Network analysis, Operations research, Retail marketing