A Pattern Recognition Lexi-Search Approach to the Variant Traveling Purchaser Problem

Abstract

The traveling purchaser problem (TPP) is a generalization of the well-known traveling salesman problem. The purchaser is aware of the travel cost between a pair of markets and between a depot and markets, the purchase cost and availability of a product at each market, and the demand for the products. The purchaser has the choice of selecting a subset of markets, where the products and how much quantity to be purchased. The objective is to determine an optimal tour for a purchaser that begins and ends at the depot to purchase a set of products from a subset of markets such that the sum of travel and purchase costs is least within the threshold values on the maximum number of markets visited and the number of products purchased at any one market. The problem involves three interesting plans, such as the selection plan, the routing plan, and the purchasing plan. This problem is frequently faced by the shoppers and it has several applications in different domains including production scheduling, transportation, network design, machine scheduling, manufacturing, etc. This paper presents an extended version of TPP along with its mathematical modeling using an integer programming and a deterministic pattern recognition lexi-search algorithm to solve optimally. To test the efficiency of the algorithm, the experiments are carried out on distinct large size benchmark data sets. The extensive comparative computational results show that the proposed algorithm is capable of finding improved solutions on several benchmark data sets reported for capacitated and uncapacitated instances.

Keywords

• Traveling salesman problem
• traveling purchaser problem
• integer programming
• pattern recognition Lexi-search algorithm