Traveling purchaser problem

The traveling purchaser problem (TPP) 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 (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, 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.[1]

Solving TPP

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

gollark: The (lack of) graphics didn't help.
gollark: I played it once, but it was too complex and confusing for me to get into it.
gollark: It's annoying that they charge a premium for it, to be honest, ECC exists by default on everything else, but still, I remember reading that it wasn't actually a huge problem.
gollark: Eeeeh. Are RAM errors *that* common?
gollark: You also pay for markup and quite possibly extra stuff you don't need.

See also

References
  1. Heuristics for the traveling purchaser problem
  2. A Dynamic Programming Approach for a Travelling Purchaser Problem With Additional Constraints
  3. A Tabu Search Approach for solving the Travelling Purchase Problem
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.