Problem z podróżującym nabywcą

Problem podróżującego nabywcy ( TPP ) to problem NP-trudny badany w informatyce teoretycznej . Mając listę targowisk, koszt przejazdu między różnymi targowiskami oraz listę dostępnych towarów wraz z ceną każdego takiego towaru na każdym targowisku, zadaniem jest znalezienie dla danej listy towarów trasy o minimalnej łączny koszt zakupów i podróży. Szczególnym przypadkiem tego problemu jest problem komiwojażera ( TSP) .

Związek z problemem komiwojażera (TSP)

Problem można postrzegać jako uogólnienie problemu komiwojażera, który można postrzegać jako szczególny przypadek TPP, w którym każdy artykuł jest dostępny tylko na jednym rynku, a każdy rynek sprzedaje tylko jeden przedmiot. Ponieważ TSP jest NP-trudne, TPP jest NP-trudne.

Rozwiązywanie TPP

Podejścia do rozwiązania problemu podróżującego nabywcy obejmują programowanie dynamiczne i algorytmy wyszukiwania tabu .

Zobacz też

Problem z wyznaczaniem tras pojazdów

^ „Heurystyka problemu podróżującego nabywcy” (PDF) . Zarchiwizowane od oryginału (PDF) w dniu 2015-09-24.
^ „Podejście do programowania dynamicznego dla problemu podróżującego nabywcy z dodatkowymi ograniczeniami” (PDF) . Zarchiwizowane od oryginału (PDF) w dniu 29.09.2019.
^ „Podejście tabu w celu rozwiązania problemu zakupów w podróży” (PDF) . Zarchiwizowane od oryginału (PDF) w dniu 10.06.2016 r.

[Heuristics_for_the_traveling_purchaser_problem-1] „Heurystyka problemu podróżującego nabywcy” (PDF) . Zarchiwizowane od oryginału (PDF) w dniu 2015-09-24.

[A_Dynamic_Programming_Approach_for_a_Travelling_Purchaser_Problem_With_Additional_Constraints-2] „Podejście do programowania dynamicznego dla problemu podróżującego nabywcy z dodatkowymi ograniczeniami” (PDF) . Zarchiwizowane od oryginału (PDF) w dniu 29.09.2019.

[A_Tabu_Search_Approach_for_solving_the_Travelling_Purchase_Problem-3] „Podejście tabu w celu rozwiązania problemu zakupów w podróży” (PDF) . Zarchiwizowane od oryginału (PDF) w dniu 10.06.2016 r.