購買者旅行問題

Abstract

購買者旅行問題 (TPP) 是知名的銷售員旅行問題 (TSP) 的一種有趣的推 廣。問題大致定義如下：在已知有數個不同的市場，分別販賣不同的商品 種類與商品價格之下，購買者經由走訪其中的幾個市場之後，購買到需要 的所有商品，目標則是期望花費的總成本(包括旅行成本與購買成本）達 到最小。因為購買者旅行問題的複雜度很高，即使是在問題資料有嚴格限 制的情況之下，也被證明是 NP-hard，所以，許多學者已分別提出不同的 啟發式演算法，來求購買者旅行問題的近似解，包括：搜尋演算法 (search algorithm)，推廣式的節省法 (generalized-savings algorithm)，旅行路線消減法 (tour-reduction algorithm)，以及商品 加附法 (commodity-adding algorithm)。在本篇論文中，我們將對這些 已經提出的演算法，分別考量不同的改良修正程序。再將這些新提出的改 良版本與原先的版本做一比較。根據實驗計算的結果，這些新提出的改良 版本都對原先的版本有十分顯著的改善。 The traveling purchaser problem (TPP) is an interesting generalization of the well-known traveling salesman problem (TSP), in which a set of commodity itemshave to be purchased at some markets selling various commodities with different prices, and the total travel and purchase costs must be minimized. The TPP has been shown to be NP-hard, even when severe restrictions on problem data are imposed. Because of the problem's complexity, numerous heuristic solution procedures including the search algorithm, the generalized-savings algorithm, the tour- reduction algorithm, and the commodity-adding algorithm, have been proposed to solve the TPP approximately. In this paper, we consider several variations of the existing algorithms to improve the solutions. The proposed variations are compared with the existing solution procedures. The results indicated that the proposed variations significantly improved the original versions of the existing solution procedures.