A GRASP/Path-Relinking algorithm for the traveling purchaser problem

The Traveling Purchaser Problem (TPP) is a generalization of the TSP that consists in choosing which nodes (markets) to visit to create a tour that allows to buy a set of products at minimum transportation and purchasing cost. The TPP has gained attention due to the computational challenges it poses and the potential applications it can support in today's technology-driven industry. This paper presents a GRASP-based methodology for the TPP based on three constructive procedures (route-first, purchase-first, and purchase-and-route) and two local search operators (insert and remove). The methodology is strengthened with a Path Relinking strategy to improve the GRASP performance by re-combining a set of elite solutions and with a Filtering strategy to improve the algorithm's efficiency by avoiding local search operations on the least promising solutions. The algorithm is tested with 855 instances of the asymmetric TPP and 190 instances of the symmetric TPP. Computational results prove the benefit of including the Path Relinking and Filtering strategies and suggest that the purchase-first constructive procedure is the most competitive in terms of objective function value with little extra effort in execution time with respect to the other constructive procedures. Our results outperform published results for the asymmetric TPP in a statistically significant way and show competitive performance for the symmetric TPP.