Article ID: | iaor2009609 |
Country: | United Kingdom |
Volume: | 35 |
Issue: | 2 |
Start Page Number: | 628 |
End Page Number: | 637 |
Publication Date: | Feb 2008 |
Journal: | Computers and Operations Research |
Authors: | Feillet Dominique, Bontoux Boris |
Keywords: | programming: travelling salesman |
The traveling purchaser problem (TPP) is a generalization of the traveling salesman problem where markets have to be visited to collect a set of commodities. Each market sells a number of commodities at a known price. The TPP consists in selecting a subset of markets purchasing every product, while minimizing the routing costs and the purchase costs. In this work, we address the solution of the TPP with an ant colony optimization procedure. We combine it with a local-search scheme exploring a new neighborhood structure. This procedure is evaluated on a set of benchmark instances from the literature and permits to improve most of the best-known solutions.