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 $T_{\mathit{max}}$ 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 $m$ routes are required and the length of each route is restricted to $T_{\mathit{max}}$ . 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.0s of calculation time, while the slow variant achieves a 0.04% gap within 272.8s. Moreover, next to achieving most of the best known solutions for many testproblems, the slow variant improved the best known results in five instances.