A heuristic approach for the Travelling Purchaser Problem

The Travelling Purchaser Problem (TPP) is a known generalization of the Travelling Salesman Problem, and is defined as follows. Let us consider a set of products and a set of markets. Each market is provided with a limited amount of each product at a known price. The TPP consists in selecting a subset of markets such that a given demand of each product can be purchased, minimizing the routing cost and the purchasing cost. This problem arises in several applications, mainly in routing and scheduling contexts, and it is NP-hard in the strong sense. A new heuristic approach based on a local-search scheme, exploring a new neighbourhood structure, is proposed. The key idea is to perform a k-exchange of markets instead of the classical 1-exchanges. A neighbour of a given TPP solution is another TPP solution obtained by removing a path of consecutive markets, and by inserting other markets so as to restore the feasibility. This proposal is evaluated on a broad class of instances from literature, where the routing costs are Euclidean distances. Computational results show that our proposal is favourably compared to previous heuristic algorithms in literature.