A memetic algorithm for the Orienteering Problem with Mandatory Visits and Exclusionary Constraints

The Orienteering Problem with Mandatory Visits and Exclusionary Constraints (OPMVEC) is to visit a set of mandatory nodes (locations) and some optional nodes, while respecting the compatibility constraint between nodes and the maximum total time budget constraint. It is a variation of the classic orienteering problem that originates from a number of real-life applications. We present a highly effective memetic algorithm (MA) for OPMVEC combining: (i) a dedicated tabu search procedure that considers both feasible and infeasible solutions by constraint relaxation, (ii) a backbone-based crossover, and (iii) a randomized mutation procedure to prevent from premature convergence. Experiments on six classes of 340 benchmark instances from the literature demonstrate highly competitive performance of MA - it reports improved results for 104 instances compared with the existing heuristic approach, while finding matching best-known results for the remaining cases. Additionally, MA can be used to produce a starting point for an exact solver (e.g., CPLEX), leading to an increased number of problem instances that are solved to optimality. We further investigate the contribution of the key algorithmic elements to the success of the proposed approach.