Yeterince yakın seyyar satıcı problemi için yeni bir paralel memetik algoritma

Year 2026, Volume: 14 Issue: 1, 152 - 162, 21.01.2026

Deniz Cantürk

https://doi.org/10.29130/dubited.1648402

Abstract

Yeterince Yakın Seyahat Eden Satıcı Problemi (YYSESP), her hedefin disk şeklinde bir mahalleye sahip olduğu ve bu mahalledeki herhangi bir noktaya ulaşıldığında ziyaret edilmiş sayıldığı klasik Seyahat Eden Satıcı Problemi'nin bir çeşididir. Bu genelleme, YYSESP'yi robotik yol planlama ve kablosuz ağ optimizasyonu gibi gerçek dünya uygulamaları için önemli bir model haline getirir. Bu çalışma, verimli keşif ve sömürü için OpenMP'den yararlanan YYSESPiçin paralel bir memetik algoritma önermektedir. Yaklaşımımız, paralel bir geçiş operatörünü paralel yerel optimizasyon prosedürleri ve yenilikçi arama operatörleriyle entegre eder. Deneysel sonuçlar, paralel uygulamanın hesaplama verimliliğini önemli ölçüde artırdığını ve sıralı versiyondan daha hızlı yüksek kaliteli çözümler ürettiğini göstermektedir. Ölçeklenebilir bir paralel algoritma ile literatürdeki problem örneklerinin en iyi sonuçlarını elde etmeyi başardık.

Keywords

Seyyar satıcı problemi , paralel algoritmalar , memetik , eniyileme

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

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.

Supporting Institution

This research received no external funding.

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
• Dülger, Ö., & Dökeroğlu, T. (2024). A new parallel tabu search algorithm for the optimization of the maximum vertex weight clique problem. Concurrency and Computation: Practice and Experience, 36(2), Article e7891. https://doi.org/10.1002/cpe.7891
• Faigl, J. (2018). GSOA: Growing self-organizing array: Unsupervised learning for the close-enough traveling salesman problem and other routing problems. Neurocomputing, 312, 120–134. https://doi.org/10.1016/j.neucom.2018.05.079
• Gulczynski, D. J., Heath, J. W., & Price, C. C. (2006). The close enough traveling salesman problem: A discussion of several heuristics. In T. Ibaraki, K. Nonobe, & M. Yagiura (Eds.), Metaheuristics: Progress as real problem solvers (pp. 271–283). Springer. https://doi.org/10.1007/978-0-387-39934-8_16
• Gurobi Optimization, LLC. (n.d.). Gurobi optimization. Retrieved December 28, 2025. https://www.gurobi.com.
• Lasserre, F. (2004). Logistics and the Internet: Transportation and location issues are crucial in the logistics chain. Journal of Transport Geography, 12(1), 73–84. https://doi.org/10.1016/S0966-6923(03)00027-9
• Lei, Z., & Hao, J.-K. (2024). An effective memetic algorithm for the close-enough traveling salesman problem. Applied Soft Computing, 153, Article 111266. https://doi.org/10.1016/j.asoc.2024.111266
• Ma, M., Yang, Y., & Zhao, M. (2013). Tour planning for mobile data-gathering mechanisms in wireless sensor networks. IEEE Transactions on Vehicular Technology, 62 (4), 1472–1483. https://doi.org/10.1109/TVT.2012.2229309
• Mennell, W. K. (2009). Heuristics for solving three routing problems: Close-enough traveling salesman problem, close-enough vehicle routing problem, sequence-dependent team orienteering problem (Doctoral dissertation, University of Maryland, College Park).
• Neri, F., & Cotta, C. (2012). Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation, 2, 1–14. https://doi.org/10.1016/j.swevo.2011.11.003
• Ort, M. (2018). Autonomous navigation in rural environments without detailed prior maps, In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (pp. 2040–2047). IEEE.
• Reinelt, G. (1991). TSPLIB—A traveling salesman problem library. ORSA Journal on Computing, 3(4), 376–384. https://doi.org/10.1287/ijoc.3.4.376
• Tang, J., Hiot Lim, M., Soon Ong, Y., & Joo Er, M. (2006). Parallel memetic algorithm with selective local search for large scale quadratic assignment problems. International Journal of Innovative Computing, Information and Control 2(6).
• Thibbotuwawa, A., Bocewicz, G., Nielsen, P., & Banaszak, Z. (2020). Unmanned aerial vehicle routing problems: A literature review. Applied Sciences, 10(13), Article 4504. https://doi.org/10.3390/app10134504
• Visser, O., Sippel, S. R., & Thiemann, L. (2021). Imprecision farming? Examining the (in)accuracy and risks of digital agriculture. Journal of Rural Studies, 86, 623–632. https://doi.org/10.1016/j.jrurstud.2021.07.024
• Wang, X., Golden, B., & Wasil, E. (2019). A Steiner Zone Variable Neighborhood Search Heuristic for the Close-Enough Traveling Salesman Problem. Computers & Operations Research, 101, 200–219. https://doi.org/10.1016/j.cor.2018.07.023
• Yang, Z., Xiao, M.-Q., Ge, Y.-W., Feng, D.-L., Zhang, L., Song, H.-F., & Tang, X.-L. (2018). A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods. European Journal of Operational Research, 265(1), 65–80. https://doi.org/10.1016/j.ejor.2017.07.024