New Harris Hawks algorithms for the Close-Enough Traveling Salesman Problem

Abstract

This study introduces a novel application of the Harris Hawks Optimization (HHO) algorithm to the Close-Enough Traveling Salesman Problem (CETSP), a challenging combinatorial optimization problem where circular neighborhoods rather than exact coordinates represent target points. To tackle the CETSP’s spatial complexity and high-dimensional solution space, we develop new HHO algorithms, including a parallel multi-population variant designed using the OpenMP framework. This parallel algorithm allows multiple subpopulations to evolve simultaneously, increasing diversity and computational efficiency, particularly on large-scale and real-time instances. Furthermore, new problem-specific exploration and exploitation operators are introduced, tailored to the CETSP’s geometric structure, enabling better guidance of the search process toward high-quality solutions. A comprehensive empirical evaluation is conducted on 47 benchmark instances, encompassing synthetic problem instances and a real-world robotic welding scenario in automotive manufacturing. The results show that the proposed methods outperform existing state-of-the-art techniques such as Genetic Algorithm (GA), Memetic Algorithm (MA-CETSP) and Variable Neighborhood Search (VNS)-based approaches, achieving 18 new best-known solutions. The experimental findings underline the strong convergence behavior, robustness across diverse problem sizes, and practical applicability of the algorithm. Additionally, the algorithm’s modular and extensible structure leads the way for future adaptations to multi-objective and dynamic versions of CETSP, broadening its relevance for both academic research and industrial deployment. • This is the first study in the literature to apply the HHO algorithm to the CETSP, bridging a significant gap in the existing body of research. • A novel parallel multi-population variant of HHO, leveraging the OpenMP framework to boost computational efficiency, is proposed. This parallel design enables scalable performance on large instances, which is critical for real-time and industrial applications. • New exploration and exploitation operators are proposed, specifically tailored for the spatial structure of the CETSP, allowing the algorithm to better navigate its complex and high-dimensional solution space. • Extensive experimentation on 47 benchmark instances, including large-scale and real-world datasets (e.g., car door welding), demonstrates that our approach achieves 18 new best-known solutions, outperforming other state-of-the-art methods such as GA, MA-CETSP, and VNS based techniques. • We present a real-world case study demonstrating how CETSP modeling and our proposed algorithm can optimize robotic path planning in car manufacturing, thereby highlighting their industrial applicability. • The algorithm’s modular design and adaptability offer a foundation for future extensions to multi-objective and dynamic CETSP variants.