Traveling purchaser problem

The traveling purchaser problem (TPP) is an NP-hard problem studied in Operations research and 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 (TSP) 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, 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.^[1]

Solving TPP

Approaches for solving the traveling purchaser problem include dynamic programming^[2] and tabu search algorithms.^[3]

References

^ "Heuristics for the traveling purchaser problem" (PDF). Archived from the original (PDF) on 2015-09-24.
^ "A Dynamic Programming Approach for a Travelling Purchaser Problem With Additional Constraints" (PDF). Archived from the original (PDF) on 2019-09-29.
^ "A Tabu Search Approach for solving the Travelling Purchase Problem" (PDF). Archived from the original (PDF) on 2016-06-10.

[Heuristics_for_the_traveling_purchaser_problem-1] "Heuristics for the traveling purchaser problem" (PDF). Archived from the original (PDF) on 2015-09-24.

[A_Dynamic_Programming_Approach_for_a_Travelling_Purchaser_Problem_With_Additional_Constraints-2] "A Dynamic Programming Approach for a Travelling Purchaser Problem With Additional Constraints" (PDF). Archived from the original (PDF) on 2019-09-29.

[A_Tabu_Search_Approach_for_solving_the_Travelling_Purchase_Problem-3] "A Tabu Search Approach for solving the Travelling Purchase Problem" (PDF). Archived from the original (PDF) on 2016-06-10.

[1]

[2]

[3]

Traveling purchaser problem

Traveling purchaser problem

Traveling purchaser problem

Add your contribution

Hub overview

Root Wikipedia Article

Traveling purchaser problem

Relation to traveling salesman problem (TSP)

Solving TPP

See also

References