A Branch-and-Cut Algorithm for the Undirected Traveling Purchaser Problem

Gilbert Laporte (), Jorge Riera-Ledesma () and Juan-José Salazar-González ()
Additional contact information
Gilbert Laporte: HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Quebec, Canada H3T 2A7
Jorge Riera-Ledesma: DEIOC, Facultad de Matemáticas, Universidad de La Laguna, 38271 La Laguna, Tenerife, Spain
Juan-José Salazar-González: DEIOC, Facultad de Matemáticas, Universidad de La Laguna, 38271 La Laguna, Tenerife, Spain

Operations Research, 2003, vol. 51, issue 6, 940-951

Abstract: The purpose of this paper is to present a branch-and-cut algorithm for the undirected Traveling Purchaser Problem which consists of determining a minimum-cost route through a subset of markets, where the cost is the sum of travel and purchase costs. The problem is formulated as an integer linear program, and several families of valid inequalities are derived to strengthen the linear relaxation. The polyhedral structure of the formulation is analyzed and several classes of valid inequalities are proved to be facet defining. A branch-and-cut procedure is developed and tested over four classes of randomly generated instances. Results show that the proposed algorithm outperforms all previous approaches and can optimally solve instances containing up to 200 markets.

Keywords: Transportation: vehicle routing; Networks/graphs: traveling salesman (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.6.940.24921 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:51:y:2003:i:6:p:940-951

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().