Journal
NETWORKS
Volume 54, Issue 1, Pages 56-67Publisher
WILEY
DOI: 10.1002/net.20307
Keywords
prize collecting traveling salesman problem; branch-and-cut; valid inequalities
Funding
- Canadian Natural Sciences and Engineering Research Council (NSERC)
- Fonds Quebecois de la Recherche sur la Nature et les Technologies (FQRNT)
Ask authors/readers for more resources
Given an undirected graph with edge costs and vertex prizes, the aim of the Prize Collecting Traveling Salesman Problem (PCTSP) is to find a simple cycle minimizing the total edge cost while collecting at least a minimum amount of prizes. In this article, we present a branch-and-cut algorithm to solve the PCTSP. We have adapted and implemented some classical polyhedral results for the PCTSP and derived inequalities from cuts designed for the Orienteering Problem. Computational results on instances with more than 500 vertices are reported. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 54(1), 56-67 2009
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available