GRASP with path relinking for the orienteering problem

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.