Fusion of k-Means and Local Search Approach: An Improved Angular Bisector Insertion Algorithm for Solving the Traveling Salesman Problem

The Angular Bisector Insertion Constructive Heuristic Algorithm (ABIA), though effective for small-scale TSPs, suffers from reduced solution quality and high computational complexity in larger instances due to the degradation of its geometric properties. To address this, two enhanced variants—k-ABIA and k-ABIA-3opt—are proposed. k-ABIA employs k-means clustering to decompose large-scale problems into subgroups, each solved via ABIA, with designed inter-cluster connections to reduce global search cost. k-ABIA-3opt further integrates 3-opt local search and ATSP-specific refinement strategies to avoid local optima. Both algorithms were benchmarked against GA, AACO-LST, and the original ABIA on instances ranging from 100 to 1200 nodes, considering solution quality, stability, runtime, and ATSP performance. k-ABIA-3opt achieved the best overall solution quality, with a total deviation of 28.75%, outperforming AACO-LST (44.86%) and ABIA (144.93%). Meanwhile, k-ABIA, with its O(n2) complexity and low constant overhead, was the fastest, solving 1000-node problems within seconds on standard hardware. Both variants exhibit strong robustness due to minimal stochasticity. For ATSP, k-ABIA-3opt further incorporates directed graph-specific optimization strategies, yielding the best solution quality among all tested algorithms. In summary, k-ABIA-3opt is well-suited for scenarios demanding high-quality solutions within tight time constraints, while k-ABIA provides an efficient option for rapid large-scale TSP solving. Together, they offer scalable and effective solutions for both symmetric and asymmetric TSP instances.