In this paper, we consider the Prize Collecting Travelling Salesman Pr
oblem (PCTSP), which is a variant of the Travelling Salesman Problem (
TSP), where a tour visiting each node at most once in a given graph ha
s 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 Lagrangian heuristic and obtain an upper bound in the form
of a feasible solution starting from a lower bound to the problem rece
ntly proposed in the literature. We evaluate these bounds utilizing bo
th randomly generated instances and real ones with very satisfactory r
esults.