A memetic algorithm for the team orienteering problem

The team orienteering problem (TOP) is a generalization of the orienteering problem. A limited number of vehicles is available to visit customers from a potential set. Each vehicle has a predefined running-time limit, and each customer has a fixed associated profit. The aim of the TOP is to maximize the total collected profit. In this paper we propose a simple hybrid genetic algorithm using new algorithms dedicated to the specific scope of the TOP: an Optimal Split procedure for chromosome evaluation and local search techniques for mutation. We have called this hybrid method a memetic algorithm for the TOP. Computational experiments conducted on standard benchmark instances clearly show our method to be highly competitive with existing ones, yielding new improved solutions in at least 5 instances.