An effective hybrid evolutionary algorithm for the set orienteering problem

The Set Orienteering Problem (SOP) is a variant of the popular Orienteering Problem (OP) arising from a number of real-life applications. The aim is to find a tour across a subset of customers, while maximizing the collected profit within a given travel time limit. In SOP, vertices (customers) are partitioned into clusters, where a profit is associated to each cluster. The profit of a cluster is collected only if at least one vertex belonging to the cluster is contained in the tour. For NP-hard problem, we present a highly effective hybrid evolutionary algorithm that integrates cluster-based crossover operator, a randomized mutation operator to generate multiple distinct promising offspring solutions, and a two-phase local refinement procedure that explores feasible and infeasible solutions in search of high-quality local optima. Extensive experiments 192 large benchmark instances show that the proposed algorithm significantly outperforms the existing approaches from the SOP literature. In particular, it reports improved best-known solutions (new lower bounds) for 54 instances, while matching the existing best-known for 133 instances. We further investigate the contribution of the key algorithmic elements to success of the proposed approach.