TL;DR
This paper introduces two enhanced algorithms, k-ABIA and k-ABIA-3opt, that improve upon the Angular Bisector Insertion Algorithm (ABIA) for solving the Traveling Salesman Problem (TSP), especially for large-scale instances. By combining k-means clustering with ABIA and optionally adding a 3-opt local search, these methods achieve better solution quality and/or faster computation times compared to existing approaches.
What Problem Does This Paper Address?
The Traveling Salesman Problem (TSP) is a classic NP-hard problem where the goal is to find the shortest possible route that visits a set of cities exactly once and returns to the origin. While exact algorithms can guarantee the optimal solution, they become computationally infeasible for large numbers of cities. Heuristic algorithms offer a trade-off, providing good approximate solutions much faster. The Angular Bisector Insertion Algorithm (ABIA) is a constructive heuristic known for its speed and stability on small instances, but its performance degrades significantly on larger and more complex (asymmetric) TSPs due to reduced solution quality and increased computational complexity. This paper aims to address these limitations by developing improved versions of ABIA that can handle large-scale TSPs more effectively.
Methods
The core innovation lies in enhancing the ABIA with a "Divide-Conquer-Construct-Optimize" strategy.
- k-Means Clustering: The large TSP instance is first divided into smaller, manageable subproblems using the k-means clustering algorithm. This partitions the cities into clusters, with each cluster containing approximately 100 cities.
- ABIA for Subproblems: The original ABIA is then applied to solve the TSP within each of these smaller clusters. This leverages ABIA's strengths in producing high-quality, stable solutions for smaller problem sizes.
- Inter-Cluster Connection: After solving each subproblem, strategies are developed to connect the resulting tours from different clusters into a single, global tour. For symmetric TSPs (TSP), eight connection methods are proposed, while for asymmetric TSPs (ATSP), four directed connection methods are used, considering the directional constraints.
- 3-Opt Local Search (k-ABIA-3opt): For further refinement and to avoid local optima, the k-ABIA-3opt variant incorporates the 3-opt local search algorithm. This algorithm iteratively improves the tour by removing three edges and reconnecting them in a way that reduces the total tour length.
- k-ABIA (Simplified): The k-ABIA variant omits the 3-opt step, prioritizing computational efficiency while still benefiting from the clustering and inter-cluster connection strategies.
Datasets
The authors evaluated their algorithms on standard benchmark instances from TSPLIB, a widely used repository for TSP datasets. They selected 17 instances for evaluating solution quality (50 to 1000 nodes) and 10 instances for computational efficiency (100 to 1300 cities). For asymmetric TSP (ATSP) evaluation, they used instances with more than 100 cities from TSPLIB.
Key Insights and Ideas
- Clustering as a Scalability Enabler: The most significant insight is that partitioning large TSP instances into smaller clusters using k-means dramatically improves the scalability of constructive heuristics like ABIA. This allows ABIA to be applied effectively to problems it would otherwise struggle with.
- The Power of Hybridization: Combining a constructive heuristic (ABIA) with a clustering technique (k-means) and a local search optimization (3-opt) creates a powerful hybrid approach that balances speed and solution quality.
- Tailored ATSP Strategies: The need for distinct inter-cluster connection strategies for asymmetric TSPs highlights the importance of accounting for directional constraints, which are absent in symmetric TSPs.
- 3-Opt's Crucial Role: The k-ABIA-3opt variant consistently outperforms k-ABIA, demonstrating that the local search refinement step is critical for achieving the highest solution quality, especially in complex scenarios.
- Efficiency vs. Quality Trade-off: The paper clearly presents two options: k-ABIA-3opt for high-quality solutions when time is less constrained, and k-ABIA for rapid, efficient solutions when speed is paramount.
Key Results
- Solution Quality: k-ABIA-3opt achieved the best overall solution quality, with a total deviation of 28.75% across benchmark instances, significantly outperforming AACO-LST (44.86%) and the original ABIA (144.93%). It also achieved the best solution in 7 out of 17 instances.
- Computational Efficiency: k-ABIA was the fastest algorithm, solving 1000-node problems within seconds. k-ABIA-3opt was also significantly faster than GA and ABIA, with a total runtime of 189.083 seconds compared to ABIA's 11,614.367 seconds for the tested instances.
- Stability: Both k-ABIA-3opt and k-ABIA demonstrated strong robustness and stability, with low coefficients of variation (CV) across instances, attributed to their limited randomness.
- ATSP Performance: k-ABIA-3opt also showed superior performance on ATSP instances, achieving the highest solution quality and average rank.
Limitations and Future Work
- Limitations:
- The performance of k-means clustering can be sensitive to the initial centroid selection, which introduces a single source of randomness.
- The paper notes that ABIA's performance is influenced by the initial starting point and bisecting direction, suggesting potential for improvement in these aspects.
- Future Work:
- Dynamic Clustering: Developing adaptive clustering strategies that adjust cluster sizes based on path directional characteristics or point group density for better inter-cluster connections in ATSP.
- Optimized Initial Point/Bisecting Strategy: Designing heuristic rules for precisely selecting initial points and optimizing bisecting directions to reduce time complexity.
- Extension to Other Problems: Applying the proposed method's clustering and refinement strategies to other combinatorial optimization problems like Vehicle Routing, Quadratic Assignment, and Job Shop Scheduling.
- Feature Selection: Exploring the potential of the method's structure-preserving and subset selection capabilities for feature selection tasks in machine learning.
Summary updated