GRASP with path relinking for the orienteering problem

GRASP with path relinking for the orienteering problem

0.00 Avg rating0 Votes
Article ID: iaor201525335
Volume: 65
Issue: 12
Start Page Number: 1800
End Page Number: 1813
Publication Date: Dec 2014
Journal: Journal of the Operational Research Society
Authors: , , ,
Keywords: knapsack problem, NP-hard, orienteering, GRASP
Abstract:

In this paper, we address an optimization problem resulting from the combination of the well‐known travelling salesman and knapsack problems. In particular, we target the orienteering problem, originated in the context of sport, which consists of maximizing the total score associated with the vertices visited in a path within the available time. The problem, also known as the selective travelling salesman problem, is NP‐hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in routing and tourism. We propose a heuristic method–based on the Greedy Randomized Adaptive Search Procedure (GRASP) and the Path Relinking methodologies–for finding approximate solutions to this optimization problem. We explore different constructive methods and combine two neighbourhoods in the local search of GRASP. Our experimentation with 196 previously reported instances shows that the proposed procedure obtains high‐quality solutions employing short computing times.

Reviews

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