Abstract
This paper introduces a significantly improved 1.5-approximation algorithm for the Subpath Planning Problem (SPP), a variant of the Traveling Salesman Problem (TSP) where specific segments of the route are pre-defined. By refining the classic Christofides’ algorithm to handle these fixed subpaths directly, the authors achieve the 1.5-approximation threshold—the gold standard for metric TSP. Furthermore, the authors propose a new generalization called the Subgroup Planning Problem (SGPP) and demonstrate a 10% improvement in solution quality over previous state-of-the-art methods on large-scale datasets.
Introduction: The Subpath Planning Problem
The Subpath Planning Problem (SPP) involves finding the shortest possible loop (tour) that incorporates a set of mandatory segments, or "subpaths." This problem arises in practical applications such as robotics, where a robot might need to follow specific lines or "nicks" on a surface (e.g., car polishing) rather than just visiting discrete points.
SPP is a strict generalization of the Traveling Salesman Problem; if every subpath consists of a single point, the problem reduces to TSP. Given that TSP is NP-hard, SPP is at least as difficult. Previous theoretical guarantees for SPP were limited to a 2-approximation. This work aims to bridge that gap, reaching a 1.5-approximation ratio.
Methodology
The researchers developed two primary algorithms to address SPP and its generalization.
1. 1.5-Approximation for SPP
The core innovation is a direct adaptation of Christofides’ algorithm. Unlike previous methods that transformed SPP into a standard TSP instance—thereby introducing "noise" and worsening the approximation ratio—this approach respects subpaths natively.
- S-Spanning Tree: The algorithm first constructs a Minimum Spanning Tree (MST) forced to include all mandatory subpaths. This is achieved by contracting each subpath into a single point, finding a standard MST, and then uncontracting them.
- Matching and Eulerian Cycles: Similar to the standard Christofides approach, a minimum-weight perfect matching is found for odd-degree vertices to create a graph where every vertex has an even degree, enabling an Eulerian cycle.
- Smart Shortcutting: During the shortcutting phase, the algorithm ensures it never shortcuts across a mandatory subpath, preserving problem constraints while maintaining the 1.5 ratio.
2. 3-Approximation for SGPP
The authors also introduce the Subgroup Planning Problem (SGPP). In this variant, vertices are clustered into groups, and the agent must visit all vertices within a group consecutively before moving to the next. The proposed approach involves finding an approximate path within each group first, then treating those paths as subpaths in the SPP algorithm.
Experimental Evaluation
The algorithms were evaluated using VLSI (Very Large Scale Integration) datasets, with instances ranging from 130 to over 21,000 vertices. Since these are standard TSP benchmarks, the authors generated subpaths using two methods:
- Proximity-based: Connecting nearby points to simulate logical paths.
- Random: Connecting distant points to create more challenging metric instances.
Key Results and Insights
The study yielded several significant findings:
- Theoretical Advancement: The best-known approximation ratio for metric SPP was improved from 2.0 to 1.5. The authors proved this 1.5-approximation is "tight," meaning further improvement would likely require a breakthrough in the general TSP problem.
- Solution Quality: Numerical experiments showed that the new algorithm outperformed the previous state-of-the-art (Safilian et al., 2016) by more than 10% in tour length for large instances.
- Computational Efficiency: The algorithm maintains a complexity of $O(n^3)$. It solved instances with 10,000 vertices in under 20 minutes, making it approximately 30% faster than previous methods by avoiding complex transformations.
- Metric Flexibility: The algorithm only requires the triangle inequality to hold for edges outside mandatory subpaths, increasing its applicability to real-world robotics.
Conclusion and Future Work
While the 1.5-approximation represents a major step forward, it remains bounded by the current limits of metric TSP algorithms. Future research could explore a 2.75-approximation for SGPP by incorporating "Clustered TSP" techniques. Additionally, integrating kinematic constraints, such as turning radii, would be essential for practical hardware implementation in robotics.
Summary updated