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

The Close-Enough Traveling Salesman Problem (CETSP) is a generalization of the classical TSP, where each target is associated with a disk-shaped neighborhood and is considered visited when any point within this region is reached. This variant has strong practical applications such as robotic path planning and wireless network optimization. In this study, a parallel memetic algorithm is proposed for the CETSP, implemented using OpenMP to enhance the efficiency of both exploration and exploitation processes. The algorithm incorporates a parallel crossover operator, parallel local search procedures, and customized search strategies. Experimental evaluations were conducted on 24 established benchmark instances. The results indicate that parallel implementation achieves notable improvements in both computational efficiency and solution quality compared to its sequential counterpart. Specifically, the proposed method attained new best-known solutions in seven instances. For example, on the bubbles6 instance, the solution cost was reduced from 1229.66 to 1221.05 (a 0.70% improvement), while on team3_300, it decreased from 464.20 to 461.89 (a 0.50% improvement). Across large-scale instances, the algorithm demonstrated performance gains ranging from 0.1% to 1.2% relative to existing methods, while maintaining competitive results on smaller problems. These findings confirm that parallelization can meaningfully enhance both computational speed and optimization performance in solving the CETSP.