Journal
RAIRO-OPERATIONS RESEARCH
Volume 55, Issue -, Pages S719-S726Publisher
EDP SCIENCES S A
DOI: 10.1051/ro/2020002
Keywords
prize-collecting traveling salesman problem; MIP heuristics; Branch-and-cut
Categories
Ask authors/readers for more resources
The paper presents the Prize Collecting Traveling Salesman Problem (PCTSP) and its solving methods, with experiments demonstrating the satisfactory results of the proposed approach.
The Prize Collecting Traveling Salesman Problem (PCTSP) represents a generalization of the well-known Traveling Salesman Problem. The PCTSP can be associated with a salesman that collects a prize in each visited city and pays a penalty for each unvisited city, with travel costs among the cities. The objective is to minimize the sum of the costs of the tour and penalties, while collecting a minimum amount of prize. This paper suggests MIP-based heuristics and a branch-and-cut algorithm to solve the PCTSP. Experiments were conducted with instances of the literature, and the results of our methods turned out to be quite satisfactory.
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