A New Parallel Fitness-Oriented Memetic Algorithm for the Close Enough Traveling Salesman Problem

Abstract

The Close Enough Traveling Salesman Problem (YYGSP) is an important variant of the classic Traveling Salesman Problem (GSP). The key difference is that, each target is now represented not as a single point but as a disk-shaped neighborhood. This generalization makes YYGSP an extremely valuable and practical model, particularly for applications in fields such as robotic path planning and wireless network optimization. The aim of this study is to develop a parallel memetic algorithm that combines efficient exploration and exploitation strategies. The proposed algorithm enables the parallel computation of the fitness parameter for the YYGSP. This parallelization is achieved using OpenMP (Open Multi-Processing), targeting to significantly reduce computation time by leveraging the power of multi-core processors. By developing a scalable parallel algorithm, we have succeeded in obtaining the best results for standard problem instances found in the literature.