Efficient technique utilizing an embedding hierarchical clustering-based representation into crossed cubes for TSP optimization

Optimization challenges necessitate the development of strategies to address computational complexity, aiming to increase efficiency, reduce expenses, or improve the allocation and management of resources. Decomposition, notably clustering, offers streamlined solutions. K-means, Affinity Propagation, and Density Peaks are foundational for clustering unlabeled data. Hierarchical clustering enhances robustness through multi-level decomposition. The evaluation considers quantitative metrics and domain-specific assessments. Alternative representations like cluster-based abstractions offer new perspectives for complex problems. This paper introduces a novel hierarchical framework for solving the Euclidean Traveling Salesman Problem (TSP) using compressed quadtrees topology via recursive hybrid clustering. The cities are hierarchically clustered into a compressed quadtree, optimizing intra-cluster cohesion and inter-cluster separation, assessed by certain adequate indexes such as the Davies-Bouldin index and Gini coefficient. The 2D hierarchical representation enhances parallelizability for concurrent optimization. The compressed quadtree is embedded into crossed cubes to improve scalability, fault tolerance, and economic resource utilization. A one-by-one dilation 2 embedding minimizes distance distortions. The integration of recursive hybrid clustering, compressed quadtrees, and crossed cubes offers an innovative framework for hierarchical decomposition and parallelization in Euclidean TSP optimization.