Ing. Petra Fridrichová

In this paper, we address the Close Enough Orienteering Problem (CEOP) that is motivated to find the most rewarding route visiting disk-shaped regions under the given travel budget. The CEOP differs from the regular OP in the continuous optimization of finding the most suitable waypoint locations to collect the reward associated with each region of interest in addition to the selection of the subset of the regions and sequence of their visits as in the OP. We propose to employ the Greedy Randomized Adaptive Search Procedure (GRASP) combinatorial metaheuristic to solve the addressed CEOP, in particular, the GRASP with Segment Remove. The continuous optimization is addressed by the newly introduced heuristic search that is applied in the construction phase and also in the local search phase of the GRASP. The proposed approach has been empirically evaluated using existing benchmarks, and based on the reported comparison with existing algorithms, the proposed GRASP-based approach provides solutions with the competitive quality while its computational requirements are low.