Variable Neighborhood Search for the Orienteering Problem

This paper considers three variations of Variable Neighborhood Search (VNS) and presents the first algorithm solely based on VNS to solve the Orienteering Problem, indicating that the algorithm designed by using Reduced VNS instead of the local search phase of the traditional VNS is the best.

Abstract

The Orienteering Problem (OP) is a version of TSP with profits in which instead of a cycle, a path is sought. In this paper, we consider three variations of Variable Neighborhood Search (VNS) and present the first algorithm solely based on VNS to solve the OP. The experimental results for the benchmark problems indicate that the algorithm, designed by using Reduced VNS instead of the local search phase of the traditional VNS, is the best amongst other variations of VNS we tried; it is the most robust and produces the best results, in terms of solution quality, within a reasonable amount of time. Moreover, it improves the best known results for several benchmark problems and reproduces the best results for others.