Paper Info
Title
The traveling purchaser problem with budget constraint
Abstract
Let us consider a set of markets plus a depot and a set of products for each of which a positive demand is specified. Each product is made available in a subset of markets in each of which only a given quantity, less than or equal to the required one, can be purchased at a given unit price. The distance between each couple of markets and between each market and the depot is known. The Traveling Purchaser Problem with Budget constraint (TPP-B) looks for a simple cycle starting at and ending to the depot and visiting a subset of markets at a minimum traveling cost and such that the demand for each product is satisfied and the cost globally spent for purchasing the products does not exceed a defined budget threshold. As the TPP also this problem arises in several application domains, but while the former has been largely studied, very few contributions exist in the literature for the TPP-B. We propose and compare two solution algorithms, an enhanced local-search heuristic and a variable neighborhood search (VNS) approach also tested in a multi-start variant. The proposed algorithms have been used to solve both the capacitated and the uncapacitated version of the problem. Test problems have been obtained by adding a budget constraint to known benchmark instances for the TPP.
Year
DOI
Venue
2009
10.1016/j.cor.2008.09.001
Computers & OR
Keywords
Field
DocType
application domain,multi-start variant,benchmark instance,Purchaser Problem,budget threshold,positive demand,purchaser problem,budget constraint,Budget constraint,enhanced local-search heuristic,proposed algorithm,test problem
Traveling purchaser problem,Mathematical optimization,Budget constraint,Local search (optimization),Mathematics
Journal
Volume
Issue
ISSN
36
7
Computers and Operations Research
Citations 
PageRank 
References 
14
0.66
8
Authors
2
Name
Order
Citations
PageRank
Renata Mansini157443.10
Barbara Tocchella2140.66