巡回購入者問題

巡回購買者問題（TPP）は、オペレーションズ・リサーチと 理論計算機科学において研究されているNP困難問題です。市場のリスト、異なる市場間の移動コスト、入手可能な商品のリストと各市場における各商品の価格が与えられた場合、与えられた商品リストに対して、購入コストと移動コストの合計が最小となる経路を見つけるという課題があります。巡回セールスマン問題（TSP）は、この問題の特殊なケースです。

巡回セールスマン問題（TSP）との関係

この問題は巡回セールスマン問題の一般化と見なすことができ、巡回セールスマン問題はTPPの特殊なケースと見なすことができます。TPPでは、各商品は1つの市場でのみ入手可能であり、各市場では1つの商品のみが販売されます。巡回セールスマン問題はNP困難であるため、TPPもNP困難です。^{[ 1 ]}

TPPの解決

巡回購入者問題を解決するためのアプローチには、動的計画法^{[ 2 ]}とタブー探索アルゴリズム^{[ 3 ]が含まれる。}

参照

• 車両経路問題

参考文献

1. 「旅行購入者問題のためのヒューリスティックス」（PDF） 。2015年9月24日時点のオリジナル（PDF）からアーカイブ。
2. 「追加制約を伴う巡回購入者問題に対する動的計画法アプローチ」（PDF） 。2019年9月29日時点のオリジナル（PDF）からアーカイブ。
3. 「移動購入問題を解決するためのタブー探索アプローチ」（PDF） 。2016年6月10日時点のオリジナル（PDF）からアーカイブ。