A modified variable neighborhood search algorithm for orienteering problems

This study proposes a modified variable neighborhood search (MVNS) algorithm to solve the orienteering problem (OP). Different from the classical variable neighborhood search (VNS) methods, the proposed MVNS algorithm divides the search space into several sub-regions according to the constraint levels under investigation. During the search process, the MVNS algorithm selects the base solution from a candidate list which consists of one solution at each constraint level. The neighboring solutions found in the neighborhood search are then compared with all solutions in the candidate list, and update the list if applicable. The proposed algorithm is able to solve single-objective OPs with several constraint levels simultaneously. The performance of the proposed MVNS algorithm is tested on a set of well-known benchmark instances and compared with other algorithms in the literatures. The computational results show that MVNS obtains 65 best-known solutions out of 67 instances. The proposed MVNS algorithm shows its promising in both efficiency and effectiveness on solving orienteering problems.