A Lagrangean Heuristic for Prize Collecting Travelling Salesman Problem

In this paper we consider the Prize Collecting Travelling Salesman Problem (PCTSP), that is a variant of the Travelling Salesman Problem (TSP) where a tour visiting each node at most once in a given graph has to be computed, such that a prize is associated with each node and a penalty has to be paid for every unvisited node; moreover, a knapsack constraint guarantees that a sufficiently large prize is collected. We develop a Lagrangean heuristic and obtain an upper bound in the form of a feasible solution starting from a lower bound to the problem recently proposed in the literature. We evaluate these bounds utilizing both randomly generated instances and real ones with very satisfactory results.