Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Traveling purchaser problem
open-in-new
<h2 id="relation-to-traveling-salesman-problem-tsp">Relation to traveling salesman problem (TSP)</h2> <p>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.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> </p> <h2 id="solving-tpp">Solving TPP</h2> <p>Approaches for solving the traveling purchaser problem include <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming</a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> and <a href="/facts/Tabu_search/olw8qTSl">tabu search</a> algorithms.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Vehicle_routing_problem/TS5pWNdR">Vehicle routing problem</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>"Heuristics for the traveling purchaser problem" (PDF). Archived from the original (PDF) on 2015-09-24. <a href="https://web.archive.org/web/20150924015724/http://www.fsa.ulaval.ca/personnel/renaudj/pdf/Recherche/tpp(purchaser)%20COR.pdf" target="_blank">https://web.archive.org/web/20150924015724/http://www.fsa.ulaval.ca/personnel/renaudj/pdf/Recherche/tpp(purchaser)%20COR.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>"A Dynamic Programming Approach for a Travelling Purchaser Problem With Additional Constraints" (PDF). Archived from the original (PDF) on 2019-09-29. <a href="https://web.archive.org/web/20190929213713/http://www.di.unipi.it/optimize/Events/proceedings/T/C/4/TC4-1.pdf" target="_blank">https://web.archive.org/web/20190929213713/http://www.di.unipi.it/optimize/Events/proceedings/T/C/4/TC4-1.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>"A Tabu Search Approach for solving the Travelling Purchase Problem" (PDF). Archived from the original (PDF) on 2016-06-10. <a href="https://web.archive.org/web/20160610114059/http://infos2008.fci.cu.edu.eg/infos/DSS_04_P024-030.pdf" target="_blank">https://web.archive.org/web/20160610114059/http://infos2008.fci.cu.edu.eg/infos/DSS_04_P024-030.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>