Effective Algorithms for a Bounded Version of the Uncapacitated TPP

Let us consider a set of markets plus a depot and a set of products. Each product is made available at a given price in a subset of markets. The distance between each couple of markets and between each market and the depot is known. The Uncapacitated Traveling Purchaser Problem with Budget constraint (UTPP-B) looks for a simple cycle starting at and ending to the depot which visits a subset of markets at the minimum traveling cost while purchasing all products at a global cost that does not exceed a defined budget threshold. Although the problem arises in several application domains very few contributions exist in the literature for the UTPP-B. We propose and compare two solution algorithms for the problem, an enhanced local search heuristic and a Variable Neighborhood Search (VNS) approach. UTPP benchmark instances with additional budget constraints are used for computational experiments. Heuristic performances are compared to exact solution values provided in [13] while solving with a single-objective hierarchical approach a bi-objective UTPP.