针对成衣样版特征的裁剪路径优化设计

金爱燕， 高佩佩， 尚笑梅

(1. 苏州大学 纺织与服装工程学院， 江苏 苏州 215021； 2. 江苏和鹰机电科技有限公司， 江苏 盐城 224700)



针对成衣样版特征的裁剪路径优化设计

金爱燕1,2， 高佩佩1， 尚笑梅1

(1. 苏州大学 纺织与服装工程学院， 江苏 苏州 215021； 2. 江苏和鹰机电科技有限公司， 江苏 盐城 224700)

针对针织休闲长裤这一大类成衣裁剪路径优化问题，以裁刀在排料图中衣片外轮廓间移动的空行程距离最短为优化目标，提炼出用于路径优化的样版特征，给出了裁剪衣片的外轮廓几何表达，在此基础上设计了裁剪路径的数学模型，将裁剪路径优化问题归结为旅行商问题，并设定2步算法解决，首先用蚁群算法确定排料图中衣片的裁剪顺序，然后依据特征确定最近邻算法选择裁剪起始点，获得最终裁剪最佳路径。实验验证表明，使用该算法可有效地减少裁刀空行程距离，显著地提高裁剪效率。

休闲长裤； 裁剪路径； 样版特征； 空行程距离

目前，国内众多服装企业使用数控裁剪机进行面料裁剪，数控裁剪机通常都使用同样的裁剪控制系统裁剪不同类型的成衣，裁刀走刀路径没有一一对应性，不同的成衣类型具备不同的样版特征，使得不同类型的成衣之间裁刀走刀路径具有较大的差异，对同一类型的成衣有针对性地优化裁剪路径，可以有效地提高数控裁剪机的裁剪效率和质量。目前国内外学者对服装排料优化问题已做了相当深入的研究，应用遗传算法[1]、组合优化算法[2]、启发式算法[3]等，开发了很多服装排料优化系统，但对如何实现服装裁剪路径优化研究甚少。本文针对针织休闲裤这一大类成衣，运用案例对比分析、数理统计等方法，提炼出针织休闲裤的样版特征，设计了针织休闲裤的裁剪路径优化算法。

1 样版特征

将针织休闲裤生产订单中的款式图和排料图资料作为研究样本，样本容量为8。针织休闲裤造型有宽松型和紧身型2种，穿着合体自如、方便舒适，样版的外形轮廓线由简单的直线与弧线构成，面料具有弹性，无省无褶，结构简单，侧缝处有插袋，分割线较少[4]，样本都是长裤。

1.1 样片特征

依据排料图中衣片面积的大小，将针织休闲裤排料图中的衣片分为2组，衣片面积小于或等于0.3 m2的小衣片组，衣片面积大于0.3 m2的大衣片组。计算得出各个样本排料图中的总衣片数量和大、小衣片数量占总衣片数量的百分比，统计数据见表1。

表1 针织休闲裤衣片统计表Tab.1 Cut-path statistics of knitting leisure trousers

由表1可知，样本排料图中总衣片数量的区间范围在25～50片之间，计算得出总衣片数量的平均值为40片，大衣片数量占总衣片数量百分比的平均值为52%，大于小衣片占总衣片数量百分比的平均值。

数控裁剪机裁剪排料图中的衣片时，选择不同的衣片裁剪顺序，裁刀所走的空行程长度是不一样的，而裁刀所走的最短空行程只对应一种衣片裁剪顺序即最佳裁剪顺序。假设待裁剪排料图中的衣片数量为n，那么这张排料图就有n!种衣片裁剪顺序，电脑程序就要从n!种顺序中找到最佳裁剪顺序，可见衣片数量越多，寻找最佳裁剪顺序的计算量就越大，样本排料图中的衣片总数量变化区间在25～50片之间，电脑程序至少要从25!(1.6×1025)种顺序中找到最佳裁剪路径，程序运算量非常大[5]。

1.2 样版轮廓几何轨迹特征

在数控裁剪机裁剪过程中，排料图中待裁剪的衣片以矢量图形格式在电脑系统中进行数据处理，各片衣片的轮廓线不是实际的曲线，而是由若干个点连接而成的封闭多边形，此封闭多边形设定为裁刀裁剪衣片时所走的有效路径。有效路径分为有效曲线路径和有效直线路径。通过分析、统计得出样本排料图中的曲线裁剪路径占总路径百分比和直线裁剪路径占总路径百分比，统计数据见表2。

表2 针织休闲裤线段统计表Tab.2 Segment statistics of knitting leisure trousers

由表2可知，样本排料图中曲线路径百分比的平均值是78%，直线路径所占百分比的平均值为22%，曲线路径所占百分比的平均值大于直线路径所占百分比的平均值。

在数控裁剪机裁剪服装面料过程中，裁刀走直线路径时，走刀容易保持较高裁剪精度，裁片质量高；裁刀走曲线时，裁刀走刀角度容易偏差，裁刀裁剪精度降低，裁片质量下降。排除服装面料特性的影响，裁片要保证较高裁剪精度主要取决于裁片中曲线的比例高低，曲线越多，衣片裁剪难度越高，对数控裁剪机的裁剪精度要求越高。针织休闲裤的直线路径百分比的平均值小于曲线路径百分比的平均值，裁剪针织休闲裤具有较大难度[6]。

2 裁剪路径优化

2.1 衣片外轮廓几何定义

待裁剪的针织休闲裤排料图中包含若干片独立的衣片，衣片外轮廓构成各个衣片，直线、曲线和圆弧是衣片外轮廓的基本元素，这里，定义衣片外轮廓为环(H)，组成衣片外轮廓的基本元素为边(E)，边的端点为顶点(V)。排料图确定后，每片衣片在排料图中的位置是固定的，而且每片衣片的裁剪路径也是相对固定的，因此可以用每片衣片外轮廓的特征点代替衣片的具体几何信息，衣片外轮廓可以是直线、曲线或圆弧。曲线和圆弧的顶点是曲线和圆弧的起点和终点，直线的顶点是直线的两端。基于以上参数的设定，在本文中做出如下定义：1床针织休闲裤排料图中衣片的总数量为n，第i片衣片记为Hi(i=1,2,3,…,n)，Hi对应的顶点总数记为V(i)，第i片衣片对应的第j个顶点记为Vij(i=1,2,3, …,n;j=1,2,3, …,V(i))，如图1所示。

图1 衣片外轮廓示意图Fig.1 Diagram of cut-parts contours

2.2 蚁群算法

针织休闲裤排料图中的裁剪路径优化问题可简化为一系列点集的最短路径问题，多点的路径优化问题可以归结为旅行商问题即TSP进行求解。旅行商问题直观描述是：旅行家从某城市出发，经过n个城市，希望找到1条既能经过各个城市，又能每个城市仅经历1次最后回到出发城市的最短路径。旅行商问题中的n个城市相当于裁剪路径优化问题中的n片待裁剪衣片，旅行商能够找到的1次不重复走遍所有城市的先后顺序就是裁剪路径优化问题中的衣片的裁剪顺序，而以此顺序获得的各城市间的行走路径相当于裁刀走刀相对优化的路径[8]。

2.2.1 蚁群算法的数学模型

利用蚁群算法求解排料图中裁刀裁剪的TSP问题，蚁群算法主要是确定待裁剪衣片的最佳裁剪顺序，可以把每片裁片的形心看成求解TSP问题中的每座城市，求解的目标是使裁刀所走空行程长度最短，即旅行商所走的城市间的路径之和最短。蚁群算法求解TSP问题包括路径选择、信息素更新2个步骤，信息素是指蚂蚁在所经过的路径上留下的一种挥发性分泌物，其数学模型如下。

式中：Tk(k=1,2,…,m)为蚂蚁k已走过城市的集合；ηij为城市i移动到城市j间的距离因子，通常取值为城市i到城市j之间距离的倒数，即ηij=1/dij；α表示信息素浓度的相对重要程度；β表示启发信息的相对重要程度[9]。

2)信息素更新。设信息素的挥发系数为p(0

2.2.2 蚁群算法实现

采用蚁群算法的针织休闲裤裁剪路径优化的具体流程如图2所示。

注：Nc为迭代步数，Nmax为预定的迭代次数。图2 蚁群算法流程图Fig.2 Flow chart of ant colony algorithm

2.3 裁剪起始点的确定

利用蚁群算法确定针织休闲裤排料图中的衣片裁剪顺序后，再采用改进后的最近邻算法确定各片衣片外轮廓的裁剪起始点，具体步骤如下：

1)以U0为裁剪原点，令Uk=U0,U={U0};

2)根据已确定的裁剪顺序，寻找第1片衣片H1对应的顶点集V1={V11，V12，…，V1V(1)}中距离Uk最近的顶点U1=V1j(对应衣片Hi),令Uk=U1，然后在H集中删掉H1及对应的H1顶点{Vi1，Vi2，…，V1V(1)};

3)按照裁剪顺序遍历剩下的未运算的衣片H对应的顶点集，重新设定在第2步中确定的裁剪起始点为搜索起点，按照第2步的搜索规律，确定剩下裁片的裁剪起始点，同时加入到裁剪起始点集U中，如果H中还有元素继续执行第2步，如果H中元素个数为零程序结束，输出结果U={U0，U1，…，Ui,…，Un}，根据各个裁剪起始点的位置生成裁刀的空行程走刀路径。

3 实验验证

使用该算法对8份针织休闲裤样本的排料图生成模拟裁剪路径，空行程长度比未优化前平均缩短32%。图3为针织休闲裤空行程路径对比示意图，图中粗实线表示裁床裁刀空行程的轨迹。图3(a)为优化前按照一般数控裁剪机的裁剪路径算法获得的空行程裁剪路径图，空行程长度为21 604 mm，图3(b)为经过本文提出的算法优化后得到的空行程裁剪路径图，空行程长度为14 865 mm，将图3(a)空行程距离缩短了6 739 mm。实验结果证明了本文算法的可行性和优越性。

图3 空行程路径对比示意图Fig.3 Comparison diagram of non-cutting path. (a) Original non-cutting path; (b)Optimal non-cutting path

4 结 论

本文针对针织休闲裤这一大类成衣，提出了基于样版特征的裁剪路径优化算法，该算法先用蚁群算法优化衣片裁剪顺序，再采用改进的最近邻算法优化衣片外轮廓裁剪起始点，得到以下结论：基于样版特征进行裁剪路径优化是可行的。本文算法可使空行程路径长度缩短30%左右。本文算法有效地缩短了针织休闲裤裁剪空行程长度，但是该算法是否可推广至其他大类成衣，还有待于进一步研究。

FZXB

[1] 吴娟, 杨兵, 刘达新, 等. 基于Open CASCADE的服装排料系统的研究与开发[J]. 合肥工业大学学报: 自然科学版, 2012, 35(9): 1167-1171. WU Juan, YANG Bing, LIU Daxin, et al. Research and development of open CASCADE based garment layout system[J]. Journal of Hefei University of Technology: Natural Science Edition, 2012, 35(9): 1167-1171.

[2] 王姝, 金福江. 服装矩形样片组合优化模型及其求解算法[J]. 武汉理工大学学报: 信息与管理工程版, 2011, 33(2): 210-213. WANG Shu, JIN Fujiang. Combination optimization model and its solution algorithm for garment rectangular parts[J]. Journal of Wuhan University of Technology: Information & Management Engineering, 2011, 33(2): 210-213.

[3] ALBANO A, SAPUPPO G. Optimal allocation of two-dimensional irregular shapes using heuristic search methods[J]. IEEE Trans Systems Management and Cybernetics, 1980, 10(5): 242-248.

[4] 薛福平. 针织服装设计概论[M]. 2版. 北京: 中国纺织出版社, 2008:3-5. XUE Fuping. Design for Knitting Wear[M]. 2nd ed. Beijing: China Textile & Apparel Press, 2008:3-5.

[5] 吴华锋, 陈信强, 毛奇凰, 等. 基于自然选择策略的蚁群算法求解TSP问题[J]. 通信学报, 2013, 34(4): 165-170. WU Huafeng, CHEN Xinqiang, MAO Qihuang, et al. Improved ant colony algorithm based on natural selection strategy for solving TSP problem[J]. Journal on Communications, 2013, 34(4): 165-170.

[6] 金爱燕. 大类成衣裁剪路径的分析与优化研究:针织休闲裤[D]. 苏州: 苏州大学, 2014: 17-18. JIN Aiyan. Analysis and optimization of garment cutting path:knitting leisure trousers[D]. Suzhou: Soochow University, 2014: 17-18.

[7] 张军, 刘羽, 卢奉良. 蚁群算法解决TSP问题的并行化研究与实现[J]. 计算机技术与发展, 2011, 21(5)：72-74. ZHANG Jun, LIU Yu, LU Fengliang. Parallel research and implementation of ant colony algorithm to solve problem[J]. Computer Technology and Development, 2011, 21(5): 72-74.

[8] THOMAS S, DORIGO M. A short convergence proof for a class of ant colony optimization algorithms[J].IEEE Trans on Evolutionary Computation, 2002,6(4):358-365.

[9] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997(1): 53-66.

[10] 许世杰. 基于过程优化的蚁群算法研究与应用[D]. 济南: 山东师范大学, 2010:11-12. XU Shijie. The research and application of process based ant colony algorithm[D]. Ji′nan: Shandong Normal University, 2010:11-12.

Optimization design of cutting path based on characteristics of garment pattern

JIN Aiyan1,2， GAO Peipei1， SHANG Xiaomei1

(1.CollegeofTextileandClothingEngineering,SoochowUniversity,Suzhou,Jiangsu215021,China；2.JiangsuYinScience&TechnologyCo.,Ltd.,Yancheng,Jiangsu224700,China)

Garment types are different, leading to different pattern characteristics and cutting path. The cutting path optimization problem of knitting leisure trousers is considered. Aiming at finding a minimum non-cutting path tour passing through one node from each cluster, pattern characteristics based on path optimization were sorted out, and geometric expression of cut-parts contours were given. Based on the geometric expression, the mathematical model of cutting path is established. The optimization problem of cutting path can be formulated as a generalized traveling salesman problem. A two-step approach is presented to solve the optimization problem. At first, the cut-parts acquir the best cutting sequence by the ant colony algorithm. Then nearest neighbor algorithm is adopted to determine the piercing point of each contour to obtain the finished cut optimization path. The application result shows that the algorithm can significantly reduce air travel and improve cutting efficient.

leisure trousers; cutting path; pattern characteristic; non-cutting path

10.13475/j.fzxb.20140603705

2014-06-15

2015-05-04

金爱燕(1990—)，女，硕士生。研究方向为数字化服装制造。尚笑梅，通信作者，E-mail：shangxiaomei@suda.edu.cn。

TS 941.62

A