A Path Relinking approach for the Team Orienteering Problem

作者：Souffriau Wouter^*; Vansteenwegen Pieter; Vanden Berghe Greet; Van Oudheusden Dirk

来源：Computers & Operations Research, 2010, 37(11): 1853-1859.

DOI：10.1016/j.cor.2009.05.002

• Team Orienteering Problem
• Metaheuristic
• Path Relinking

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(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(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.

• 出版日期2010-11