A branch and bound algorithm for the traveling purchaser problem

An important generalization of the traveling salesman problem called the traveling purchaser problem is considered. A branch and bound algorithm which solves a related simple plant location problem for calculating the bounds is proposed for this problem. Computational experiments with this algorithm provide the evidence that moderate size problems of up to 25 cities and 100 commodities can be solved in reasonable computation time. The problem is shown to have applications in the areas of scheduling, warehousing and routing.