The Traveling Salesman Problem (TSP) is a cornerstone of combinatorial optimization. However, many real-world applications require visiting locations in predefined clusters—a variation known as the Clustered TSP (CTSP). This paper, presented at AAAI-25, introduces significant theoretical and practical advancements for CTSP and its generalization, the Subgroup Planning Problem (SGPP).
The Challenge of Clustered Routing
In the Clustered TSP, a set of vertices is partitioned into clusters, and the objective is to find a minimum-weight tour that visits all vertices in one cluster before moving to the next. The Subgroup Planning Problem (SGPP) extends this by relaxing the global triangle inequality. In SGPP, the triangle inequality is only guaranteed to hold within each subgroup or when transitioning between specific types of nodes, making it particularly relevant for robotics and automated manufacturing where movement costs are non-uniform.
Prior to this work, the best polynomial-time approximation for SGPP was a 3-approximation. This research aims to bridge the gap between the general SGPP and the more constrained CTSP.
Proposed Algorithmic Framework
The authors propose three distinct strategies tailored to different problem constraints:
- Hybrid Polynomial-Time Algorithm: By combining two sub-algorithms—one optimized for "heavy" internal group edges and another for "light" ones—the researchers achieved a 2.167-approximation in $O(n^3)$ time.
- Fixed-Parameter Tractability (FPT) by Group Size ($t$): When the number of locations within each group is small, the problem can be approached via dynamic programming. The key insight here was a novel cost function that minimizes the internal path weight relative to the entry and exit points, leading to a 2.072-approximation.
- FPT by Number of Groups ($m$): For instances with a small number of total groups, the authors developed a method to optimally concatenate paths. This yields an approximation ratio $\beta < 1.5$, where $\beta$ is tied to the current state-of-the-art for the Path TSP problem.
Key Results and Theoretical Impact
The primary contribution of this work is the significant reduction in approximation ratios across multiple settings. By demonstrating that SGPP can be solved with a 2.167 ratio, the authors prove that relaxing the triangle inequality does not necessarily make the problem significantly harder to approximate than standard CTSP.
Experimental evaluations on standard VLSI benchmark datasets (ranging from 131 to over 744,000 vertices) confirmed these theoretical gains. While the FPT algorithms provide superior accuracy, they exhibit the expected exponential scaling with respect to their parameters ($t$ or $m$), highlighting a trade-off between solution quality and computational time.
Conclusion
This research provides a more robust toolkit for solving complex routing problems. By leveraging parameter-specific strategies and refined cost functions, the authors have established new benchmarks for both CTSP and SGPP. Future work will likely focus on "Ordered SGPP," where the sequence of clusters is fixed, further tailoring these solutions to specific industrial automation needs.
Summary updated