A TABU Search Heuristic for theCapacitated Team Orienteering Problem

In this paper, we develop a heuristic algorithm to solve the Capacitated Team Orienteering Problem (CTOP), which is a capacitated version of the Team Orienteering Problem (TOP). In the TOP, a number of vehicle tours need to be constructed such that the total collected reward is maximized, while a limitation on the tour duration exists. In the CTOP, additionally, customers have a non-negative demand and vehicles face capacity constraints. Our solution technique builds upon the solution method for the TOP as proposed by Tang and Miller-Hooks (2005). An adaptive memory procedure incorporates a tabu search procedure, which makes use of variable neighbourhood search and executes random and greedy tour improvement procedures. Computational experiments reveal that our heuristic is able to yield highquality solutions for the TOP as well as the CTOP in an efficient way.