2025年02期 v.46 9-17页
黄启华1 冯子俊2 杜玉晓1 王烁哲1
（1.广东工业大学，广东 广州 510006
2.九江天赐高新材料有限公司，江西 九江 332500）
摘要：针对当前衣物裁剪路径优化算法无法同时满足高精度和低时间消耗的问题，提出基于K-means与2-Opt改进的贪心路径优化算法。首先，利用K-means聚类算法进行大规模旅行商问题的局部分组；然后，采用2-Opt改进的贪心算法优化路径；最后，通过最近邻连接方法对子问题的解进行类间连接。实验结果验证了该算法具有较好的路径和效率优化能力。
关键词：衣物裁剪路径优化；K-means聚类算法；2-Opt算法；贪心算法
中图分类号：TP391 文献标志码：A 文章编号：1674-2605(2025)02-0002-09
DOI：10.12475/aie.20250202 开放获取
Research on an Improved Greedy Path Optimization Algorithm
Based on K-means and 2-Opt
HUANG Qihua1 FENG Zijun2 DU Yuxiao1 WANG Shuozhe1
(1.Guangdong University of Technology, Guangzhou 510006, China
2.Jiu Jiang Tinci Materials Technology Co., Ltd., Jiujiang 332500, China)
Abstract: Aiming at the problem that current garment cutting path optimization algorithms cannot simultaneously satisfy high precision and low time consumption, this paper proposes an improved greedy path optimization algorithm based on K-means and 2-Opt. First, the K-means clustering algorithm is used for local grouping of large-scale traveling salesman problems. Then, a 2-Opt improved greedy algorithm is adopted to optimize the path. Finally, the nearest neighbor connection method is employed to connect solutions of sub-problems between clusters. Experimental results verify that the proposed algorithm demonstrates superior path and efficiency optimization capabilities.
Keywords: garment cutting path optimization; K-means clustering algorithm; 2-Opt algorithm; greedy algorithm
