A Lagrangian heuristic for the Prize Collecting Travelling Salesman Problem

A Lagrangian heuristic for the Prize Collecting Travelling Salesman Problem

0.00 Avg rating0 Votes
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: , ,
Keywords: orienteering
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.