A New Parallel Memetic Algorithm for the Close-Enough Traveling Salesman Problem
Abstract
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.
Keywords
Travelling salesman, Parallel algorithm, Memetic, Optimization
Supporting Institution
This research received no external funding.
Ethical Statement
This study does not involve human or animal participants. All procedures followed scientific and ethical principles, and all referenced studies are appropriately cited.
Thanks
I would like to thank Tansel Dokeroglu for his valuable support in the composition of this article.
References
- Arafat, M. Y., Alam, M. M., & Moh, S. (2023). Vision-based navigation techniques for unmanned aerial vehicles: Review and challenges. Drones, 7(2), Article 89. https://doi.org/10.3390/drones7020089
- Behdani, B., & Smith, J. C. (2014). An integer-programming-based approach to the close-enough traveling salesman problem. INFORMS Journal on Computing, 26(3), 415–432. https://doi.org/10.1287/ijoc.2013.0574
- Cariou, C., Moiroux-Arvis, L., Pinet, F., & Chanet, J.-P. (2023). Evolutionary algorithm with geometrical heuristics for solving the close enough traveling salesman problem: Application to the trajectory planning of an unmanned aerial vehicle. Algorithms, 16(1), Article 44. https://doi.org/10.3390/a16010044
- Carrabs, F., Cerrone, C., Cerulli, R., & D’Ambrosio, C. (2017). Improved upper and lower bounds for the close enough traveling salesman problem. In Computational logistics (pp. 165–177). https://doi.org/10.1007/978-3-319-57186-7_14
- Carrabs, F., Cerrone, C., Cerulli, R., & Golden, B. (2020). An adaptive heuristic approach to compute upper and lower bounds for the close-enough traveling salesman problem. INFORMS Journal on Computing, Advance online publication. https://doi.org/10.1287/ijoc.2020.0962
- Chao, I.-M., & Golden, B. L. (1993). Algorithms and solutions to multi-level vehicle routing problems. University of Maryland at College Park.
- Coşar, B. M., Say, B., & Dökeroğlu, T. (2023). A New Greedy algorithm for the curriculum-based course timetabling problem. Düzce Üniversitesi Bilim ve Teknoloji Dergisi, 11(2), 1121–1136. https://doi.org/10.29130/dubited.1113519
- Deckerová, J., Kučerová, K., & Faigl, J. (n.d.). On improvement heuristic to solutions of the close enough traveling salesman problem in environments with obstacles. Proceedings of the 11th European Conference on Mobile Robots (ECMR) (pp. 1–6). IEEE. https://doi.org/10.1109/ECMR59166.2023.10256328
- Deckerová, J., Váňa, P., & Faigl, J. (2024). Combinatorial lower bounds for the generalized traveling salesman problem with neighborhoods. Expert Systems with Applications, 258, Article 125185. https://doi.org/10.1016/j.eswa.2024.125185
- Di Placido, A., Archetti, C., Cerrone, C., & Golden, B. (2023). The generalized close enough traveling salesman problem. European Journal of Operational Research, 310(3), 974–991. https://doi.org/10.1016/j.ejor.2023.04.010