A Branch-and-Cut and MIP-based heuristics for the Prize-Collecting Travelling Salesman Problem

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.

Automated summary

The paper presents the Prize Collecting Traveling Salesman Problem (PCTSP) and its solving methods, with experiments demonstrating the satisfactory results of the proposed approach.