The traveling purchaser problem (TPP) is an

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

problem studied in

Operations research Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a branch of applied mathematics that deals with the development and application of analytical methods to improve management and ...

and

theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

. 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 In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exac ...

(TSP) is a

special case In logic, especially as applied in mathematics, concept is a special case or specialization of concept precisely if every instance of is also an instance of but not vice versa, or equivalently, if is a generalization of .Brown, James Robert.� ...

of this problem.

Relation to traveling salesman problem (TSP)

The problem can be seen as a generalization of the traveling salesman problem, which can be viewed as the special case of TPP where 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 Tabu search (TS) is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986 and formalized in 1989. Local (neighborhood) searches take a potential solution to a ...

algorithms.{{cite web , url=http://infos2008.fci.cu.edu.eg/infos/DSS_04_P024-030.pdf , archive-url=https://web.archive.org/web/20160610114059/http://infos2008.fci.cu.edu.eg/infos/DSS_04_P024-030.pdf , archive-date=2016-06-10 , url-status=dead , title=A Tabu Search Approach for solving the Travelling Purchase Problem

References

NP-complete problems Travelling salesman problem

Relation to traveling salesman problem (TSP)

Solving TPP

See also

References