Improved solutions for the traveling purchaser problem
The traveling purchaser problem (TPP) is a generalization of the well-known traveling salesman problem (TSP), which has many real-world applications. Examples include the purchase of the required raw materials for the manufacturing factories in which the total cost has to be minimized, and the scheduling of a set of jobs over some machines with different set-up and job processing costs in which the total cost for completing the jobs has to be minimized. The TPP has been shown to be computationally intractable. Therefore, many heuristic solution procedures have been proposed to solve the TPP approximately. The purpose of this paper is to consider some variations of the existing solution procedures to improve the solutions. Computational experiments and performance comparisons among the existing algorithms as well as the proposed variations are provided, and the results are analyzed. The traveling purchaser problem (TPP) is an interesting generalization of the well-known traveling salesman problem (TSP), in which a list of commodity items have to be purchased at some markets selling various commodities with different prices, and the total travel and purchase costs must be minimized. Applications include the purchase of raw materials for the manufacturing factories in which the total cost has to be minimized, and the scheduling of jobs over some machines with different set-up and job processing costs in which the total costs for completing the jobs has to be minimized. The TPP has been shown to be computationally intractable. Therefore, many 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 some variations of these algorithms to improve the solutions. The proposed variations are compared with the existing solution procedures. The results indicate that the proposed variations significantly improve the existing solutions.
network optimization combinatorics complexity