Cluster-Based Path Optimization Framework for Garment Cutting Using K-Means and CAC-LK

In automated garment-cutting systems, idle-travel path planning becomes computationally expensive when the number of cutting pieces reaches medium-to-large scales (80–150 nodes), directly affecting production efficiency. To address the limitations of traditional heuristic methods in solution quality and runtime stability, this study proposes a cluster-based local search framework integrating K-means clustering with a Cluster-Aware Constrained Lin–Kernighan (CAC-LK) algorithm. K-means partitions entry points into compact spatial clusters to reduce the computational scale, and an adaptive depth-constrained CAC-LK procedure optimizes intra-cluster paths while maintaining a predictable runtime. Inter-cluster routes are connected using a nearest-neighbor strategy. Experiments on simulated datasets with 85 and 140 nodes show that the proposed method reduces the idle-travel distance by 4–10% compared with K-means + 3-opt while achieving a more stable runtime than unconstrained K-means + LK. The results demonstrate that the proposed framework provides an effective balance between path quality, scalability, and computational stability, showing strong applicability for real-time intelligent garment-cutting systems.