A TABU search heuristic for the team orienteering problem

This paper describes a tabu search heuristic for the Team Orienteering Problem (TOP). The TOP is a variant of the well-known Vehicle Routing Problem in which a set of vehicle tours are constructed such that the total collected reward received from visiting a subset of customers is maximized and the length of each vehicle tour is restricted by a pre-specified limit. The tabu search heuristic is embedded in an adaptive memory procedure that alternates between small and large neighborhood stages during the solution improvement phase. Both random and greedy procedures for neighborhood solution generation are employed and infeasible, as well as feasible, solutions are explored in the process. Results from computational experiments conducted on a set of published test problems show that the proposed technique consistently produces high-quality solutions and outperforms other published heuristics for the TOP. (C) 2003 Elsevier Ltd. All rights reserved.