基于K-means与2-Opt改进的贪心路径优化算法研究  

Research on an Improved Greedy Path Optimization Algorithm Based on K-means and 2-Opt

作　　者：黄启华 冯子俊 杜玉晓[1] 王烁哲 HUANG Qihua;FENG Zijun;DU Yuxiao;WANG Shuozhe(Guangdong University of Technology,Guangzhou 510006,China;Jiu Jiang Tinci Materials Technology Co.,Ltd.,Jiujiang 332500,China)

机构地区：[1]广东工业大学,广东广州510006 [2]九江天赐高新材料有限公司,江西九江332500

出　　处：《自动化与信息工程》2025年第2期9-17,共9页Automation & Information Engineering

基　　金：国家自然科学基金(61976059,61640213)。

摘　　要：针对当前衣物裁剪路径优化算法无法同时满足高精度和低时间消耗的问题,提出基于K-means与2-Opt改进的贪心路径优化算法。首先,利用K-means聚类算法进行大规模旅行商问题的局部分组;然后,采用2-Opt改进的贪心算法优化路径;最后,通过最近邻连接方法对子问题的解进行类间连接。实验结果验证了该算法具有较好的路径和效率优化能力。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.

关 键 词：衣物裁剪路径优化 K-MEANS聚类算法 2-Opt算法 贪心算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]