Article ID: | iaor1999974 |
Country: | Netherlands |
Volume: | 81 |
Issue: | 1 |
Start Page Number: | 289 |
End Page Number: | 305 |
Publication Date: | Jul 1998 |
Journal: | Annals of Operations Research |
Authors: | Maffioli F., Sciomachen A., Dell'Amico M. |
Keywords: | orienteering |
In this paper, we consider the Prize Collecting Travelling Salesman Problem, which is a variant of the Travelling Salesman Problem, 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 Lagrangian 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.