Innovative Clustering-Driven Techniques for Enhancing Initial Solutions in Euclidean Traveling Salesman Problems with Machine Learning Integration

Integrating machine learning techniques within metaheuristics has shown promise for effectively solving combinatorial problems like the Traveling Salesman Problem (TSP). However, key challenges remain in initializing metaheuristics to balance exploration and exploitation across vast search spaces. This paper introduces a novel clustering-driven technique for constructing high-quality initial solutions to Euclidean TSP instances. Our method uses hierarchical hybrid clustering with K-means, affinity propagation, and density peaks clustering to recursively partition cities into a compressed quadtree structure. A rigorous assessment using the Davies–Bouldin index and Gini coefficient optimizes intra- and inter-cluster quality and balance at each level. The multi-tiered decomposition strategically abstracts complex optimization landscapes into localized clusters that are solved efficiently in parallel within each using heuristics such as nearest neighbor and ant colony optimization. A genetic networking heuristic then interconnects independent intra-cluster solutions to construct unified inter-cluster routes. The clustering-guided initialization provides a diverse population of initialized tours that balance global exploration against localized exploitation. To validate our method, we conduct experiments using the generated solutions to seed a simulated annealing metaheuristic. This experimental evaluation will demonstrate this technique’s ability to initialize metaheuristics for TSP instances closer to optimality compared to traditional methods.