Jump to content

Traveling purchaser problem

Add links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Velatrix (talk | contribs) at 19:24, 16 July 2014 (Standardised spelling of "travelling"-->"traveling" with respect to name of article). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 TSP

The problem can be seen as a generalization of the traveling salesman problem, ie. 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

  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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Traveling_purchaser_problem&oldid=617218753"