Traveling purchaser problem


The traveling purchaser problem is an NP-hard problem studied in theoretical computer science. Given a list of marketplaces, the cost of travelling between different marketplaces, and a list of available goods together with the price of each such good at each marketplace, the task is to find, for a given list of articles, the route with the minimum combined cost of purchases and traveling. The traveling salesman problem is a special case of this problem.

Relation to traveling salesman problem (TSP)

The problem can be seen as a generalization of the traveling salesman problem, i.e. each article is available at one market only and each market sells only one item. Since TSP is NP-hard, TPP is NP-hard.

Solving TPP

Approaches for solving the traveling purchaser problem include dynamic programming and tabu search algorithms.