密集型多轮廓裁片的刀具空行程路径寻优

doi:10.11772/j.issn.1001-9081.2014.01.0281

计算机应用 ›› 2014, Vol. 34 ›› Issue (1): 281-285.DOI: 10.11772/j.issn.1001-9081.2014.01.0281

密集型多轮廓裁片的刀具空行程路径寻优

李迅¹,²,陈明²

1.
2. 哈尔滨工业大学深圳研究生院, 广东深圳 518055

收稿日期:2013-06-03 修回日期:2013-08-02 出版日期:2014-01-01 发布日期:2014-02-14
通讯作者: 陈明
作者简介:李迅(1986-),男,湖北恩施人,硕士研究生,主要研究方向:CAM、人工智能；陈明(1979-),男,湖南邵阳人,博士,主要研究方向:CAD/CAM、计算机图形图像、企业信息化。
基金资助:
国家自然科学基金资助项目;广东省自然科学基金资助项目;深圳创新基础研究基金资助项目

Idle travel optimization of tool path on intensive multi-profile patterns

LI Xun²,CHEN Ming²

Received:2013-06-03 Revised:2013-08-02 Online:2014-01-01 Published:2014-02-14
Contact: CHEN Ming

摘要/Abstract

摘要： 服装行业中缩短刀具裁剪空行程对于高效裁剪布料具有重要意义。结合服装裁片排列具有轮廓形状复杂、分布密集的特点,将问题转化成广义旅行商问题。基于最大最小蚁群(MMAS)算法提出了一种新的用于裁片刀具空行程路径寻优的算法——密集多轮廓蚁群算法,该算法包括4步:1)用MMAS算法确定初步裁片顺序;2)由裁片顺序寻找各裁片入刀节点;3)将各裁片的入刀节点再次用MMAS进行顺序优化重组得到初步裁剪路径;4)反复迭代第2)步和第3)步以求得最优路径。实验验证了所提算法的有效性,对比现有的扫描算法以及双信息素蚁群(NACS)算法其结果分别提升了60.15%和22.44%,该算法在刀具空行程优化上具有明显优势。

关键词: 密集型多轮廓裁片, 空行程, 路径寻优, 广义旅行商问题, 最大最小蚁群算法

Abstract: In the garment industry, shortening idle travel of tool path is important to efficiently cut these patterns from a piece of cloth. As these cutting patterns are of complex shapes and distributed intensively, it is not trivial to obtain the optimal cutting tool path via the existing algorithms. Based on MAX-MIN Ant System (MMAS), a new algorithm was proposed to optimize the idle travel of tool path. The algorithm consists of four steps: 1) using standard MMAS algorithm to define the pattern order; 2) seek the node as the tool entrance on each pattern; 3) optimize the node sequence with MMAS; 4) repeat the step 2) and 3) to achieve the optimal tool path. The experiments show that the proposed algorithm can effectively generate optimal tool path. Compared with the line-scanning algorithm and Novel Ant Colony System (NACS) algorithm, the result has been improved by 60.15% and 22.44% respectively.

Key words: intensive multi-profile patterns, idle travel, path optimization, Generalized Traveling Salesman Problem (GTSP), Max-Min Ant System (MMAS) algorithm

中图分类号:

TP391.7

李迅陈明. 密集型多轮廓裁片的刀具空行程路径寻优[J]. 计算机应用, 2014, 34(1): 281-285.

LI Xun CHEN Ming. Idle travel optimization of tool path on intensive multi-profile patterns[J]. Journal of Computer Applications, 2014, 34(1): 281-285.

参考文献

[1] LIEN, Y.N., MA, E., WAH, B.W.S. Transformation of the generalized traveling salesman problem into the standard traveling salesman problem [J]. Information Sciences, 1993, 74(1-2): 177-189.
[2] NOON C.E, BEAN, J.C. An efficient transformation of the generalized traveling salesman problem [J]. INFOR, 1993, 31(1): 39-44.
[3] Dimitrijevi? V., ?ari? Z. An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs [J]. Information Science, 1997, 102(1-4): 105-110.
[4] LAPORTE,G. SEMET,F. Computational evaluation of a transformation procedure for the symmetric generalized traveling salesman problem[J]. INFOR, 1999, 37(2): 114-120.
[5] BEHZAD, A., MODARRES, M. A new efficient transformation of the generalized traveling salesman problem into traveling salesman problem [C].// Proceedings of the 15th International Conference of Systems Engineering. Berlin: [s. n.], 2002:6-8.
[6] RENAUD, J., BOCTOR, F.F. An efficient composite heuristic for the Symmetric Generalized Traveling Salesman Problem[J]. European Journal of Operational Research, 1998, 108(3):571-584.
[7] MATEI O.，POP P. An Efficient Genetic Algorithm for Solving the Generalized Traveling Salesman Problem[C]. // IEEE International Conference. Cluj-Napoca: [s. n.], 2010:87-92
[8] GUTIN, G., KARAPETYAN, D. A memetic algorithm for the generalized traveling salesman problem [J].Natual Computing, 2010, 9(1): 47-60.
[9] P.C. POP, O. MATEI, and C. SABO.A New Approach for Solving the Generalized Traveling Salesman Problem [J]. Hybrid Metaheuristics, 2010, 6373: 62-72.
[10] YANG Jin-hui., SHI Xiao-hu, Marchese, M., LIANG, Yan-chun. An ant colony optimization method for generalized TSP problem [J]. Progress in Natual Science, 2008, 18(11): 1417-1422
[11] Hu, B., Raidl, G. Effective neighborhood structures for the generalized traveling salesman problem[C].//Evolutionary Computation in Combinatorial Optimization. Naples, Italy:[s. n.], 2008:36-47.
[12] Bontoux, B., Artigues, C., Feillet, D. A Memetic Algorithm with a Large Neighborhood Crossover Operator for the Generalized Traveling Salesman Problem [J]. Computers & Operations Research, 2010, 37(11): 1844-1852.
[13] Karapetyan D., Gutin G.. Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesmen problem [J]. European Journal of Operational Research, 2012,219(2): 234-251.
[14] MOU Lian-ming. A Novel Ant Colony System with Double Pheromones for the Generalized TSP [C]. //Natural Computation, Sichuan:[s. n.], 2011:1923-1928.
[15] Thomas, S. Holger, H. MAX-MIN Ant System [J].Future generations computer systems, 2000, 16(8):889-914.

密集型多轮廓裁片的刀具空行程路径寻优

Idle travel optimization of tool path on intensive multi-profile patterns

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	梅伟, 赵云涛, 毛雪松, 李维刚. 基于离散灰狼算法的喷涂机器人路径规划方法[J]. 计算机应用, 2020, 40(11): 3379-3384.
[2]	林基明, 班文娇, 王俊义, 童记超. 基于并行遗传最大最小蚁群算法的分布式数据库查询优化[J]. 计算机应用, 2016, 36(3): 675-680.
[3]	乔现伟, 乔蕾. 基于限域拟牛顿法的混沌类电磁学机制算法及其在路径寻优中的应用[J]. 计算机应用, 2015, 35(3): 696-699.