A biased random-key genetic algorithm for the set orienteering problem

This paper addresses the Set Orienteering Problem which is a generalization of the Orienteering Problem where the customers are grouped in clusters, and the profit associated with each cluster is collected by visiting at least one of the customers in the respective cluster. The problem consists of finding a tour that maximizes the collected profit but, since the cost of the tour is limited by a threshold, only a subset of clusters can usually be visited. We propose a Biased Random-Key Genetic Algorithm for solving the Set Orienteering Problem in which three local search procedures are applied to improve the fitness of the chromosomes. In addition, we introduced three rules useful to reduce the size of the instances and to speed up the resolution of the problem. Finally, a hashtable is used to quickly retrieve the information that are required several times during the computation. The computational results, carried out on benchmark instances, show that our algorithm is significantly faster than the other algorithms, proposed in the literature, and it provides solutions very close to the best-known ones.