A Path Relinking approach for the Team Orienteering Problem

This paper introduces a Path Relinking metaheuristic approach for solving the Team Orienteering Problem (TOP), a particular routing problem in which a score is earned for visiting a location. The objective is to maximise the sum of the scores, while not exceeding a time budget TmaxTmax for travelling to the selected locations. In the case of the simple Orienteering Problem (OP), a single route connecting all selected locations should be followed; in TOP mm routes are required and the length of each route is restricted to TmaxTmax. A fast and a slow variant of the approach are tested using a large set of test instances from the literature; they are compared to other state-of-the-art approaches. The fast variant achieves an average gap of 0.39% to the best known solutions in 5.0 s of calculation time, while the slow variant achieves a 0.04% gap within 272.8 s. Moreover, next to achieving most of the best known solutions for many testproblems, the slow variant improved the best known results in five instances.