The traveling purchaser problem (TPP) is an NP-hard

NP-hard

NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

 problem studied in theoretical computer science

Theoretical computer science

Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

. Given a list of market-places, their distances and the cost of the available articles, the task is to find a route which minimizes the cost for buying a certain set of articles available at differing prices while incorporating the costs of traveling. The traveling salesman problem is a special case of this problem.

Reduction to TSP

The problem can be reduced to the traveling salesman problem if each article is available at one market only and each market sells only one item. Thus it is NP-hard.

Solving TPP

Approaches for solving the traveling purchaser problem include dynamic programming

Dynamic programming

In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...

and tabu search algorithms.