金愛燕， 高佩佩， 尚笑梅

(1. 蘇州大學(xué) 紡織與服裝工程學(xué)院， 江蘇 蘇州 215021； 2. 江蘇和鷹機(jī)電科技有限公司， 江蘇 鹽城 224700)

?

針對(duì)成衣樣版特征的裁剪路徑優(yōu)化設(shè)計(jì)

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

(1. 蘇州大學(xué) 紡織與服裝工程學(xué)院， 江蘇 蘇州 215021； 2. 江蘇和鷹機(jī)電科技有限公司， 江蘇 鹽城 224700)

針對(duì)針織休閑長(zhǎng)褲這一大類成衣裁剪路徑優(yōu)化問題，以裁刀在排料圖中衣片外輪廓間移動(dòng)的空行程距離最短為優(yōu)化目標(biāo)，提煉出用于路徑優(yōu)化的樣版特征，給出了裁剪衣片的外輪廓幾何表達(dá)，在此基礎(chǔ)上設(shè)計(jì)了裁剪路徑的數(shù)學(xué)模型，將裁剪路徑優(yōu)化問題歸結(jié)為旅行商問題，并設(shè)定2步算法解決，首先用蟻群算法確定排料圖中衣片的裁剪順序，然后依據(jù)特征確定最近鄰算法選擇裁剪起始點(diǎn)，獲得最終裁剪最佳路徑。實(shí)驗(yàn)驗(yàn)證表明，使用該算法可有效地減少裁刀空行程距離，顯著地提高裁剪效率。

休閑長(zhǎng)褲； 裁剪路徑； 樣版特征； 空行程距離

目前，國內(nèi)眾多服裝企業(yè)使用數(shù)控裁剪機(jī)進(jìn)行面料裁剪，數(shù)控裁剪機(jī)通常都使用同樣的裁剪控制系統(tǒng)裁剪不同類型的成衣，裁刀走刀路徑?jīng)]有一一對(duì)應(yīng)性，不同的成衣類型具備不同的樣版特征，使得不同類型的成衣之間裁刀走刀路徑具有較大的差異，對(duì)同一類型的成衣有針對(duì)性地優(yōu)化裁剪路徑，可以有效地提高數(shù)控裁剪機(jī)的裁剪效率和質(zhì)量。目前國內(nèi)外學(xué)者對(duì)服裝排料優(yōu)化問題已做了相當(dāng)深入的研究，應(yīng)用遺傳算法[1]、組合優(yōu)化算法[2]、啟發(fā)式算法[3]等，開發(fā)了很多服裝排料優(yōu)化系統(tǒng)，但對(duì)如何實(shí)現(xiàn)服裝裁剪路徑優(yōu)化研究甚少。本文針對(duì)針織休閑褲這一大類成衣，運(yùn)用案例對(duì)比分析、數(shù)理統(tǒng)計(jì)等方法，提煉出針織休閑褲的樣版特征，設(shè)計(jì)了針織休閑褲的裁剪路徑優(yōu)化算法。

1 樣版特征

將針織休閑褲生產(chǎn)訂單中的款式圖和排料圖資料作為研究樣本，樣本容量為8。針織休閑褲造型有寬松型和緊身型2種，穿著合體自如、方便舒適，樣版的外形輪廓線由簡(jiǎn)單的直線與弧線構(gòu)成，面料具有彈性，無省無褶，結(jié)構(gòu)簡(jiǎn)單，側(cè)縫處有插袋，分割線較少[4]，樣本都是長(zhǎng)褲。

1.1 樣片特征

依據(jù)排料圖中衣片面積的大小，將針織休閑褲排料圖中的衣片分為2組，衣片面積小于或等于0.3 m2的小衣片組，衣片面積大于0.3 m2的大衣片組。計(jì)算得出各個(gè)樣本排料圖中的總衣片數(shù)量和大、小衣片數(shù)量占總衣片數(shù)量的百分比，統(tǒng)計(jì)數(shù)據(jù)見表1。

表1 針織休閑褲衣片統(tǒng)計(jì)表Tab.1 Cut-path statistics of knitting leisure trousers

由表1可知，樣本排料圖中總衣片數(shù)量的區(qū)間范圍在25～50片之間，計(jì)算得出總衣片數(shù)量的平均值為40片，大衣片數(shù)量占總衣片數(shù)量百分比的平均值為52%，大于小衣片占總衣片數(shù)量百分比的平均值。

數(shù)控裁剪機(jī)裁剪排料圖中的衣片時(shí)，選擇不同的衣片裁剪順序，裁刀所走的空行程長(zhǎng)度是不一樣的，而裁刀所走的最短空行程只對(duì)應(yīng)一種衣片裁剪順序即最佳裁剪順序。假設(shè)待裁剪排料圖中的衣片數(shù)量為n，那么這張排料圖就有n!種衣片裁剪順序，電腦程序就要從n!種順序中找到最佳裁剪順序，可見衣片數(shù)量越多，尋找最佳裁剪順序的計(jì)算量就越大，樣本排料圖中的衣片總數(shù)量變化區(qū)間在25～50片之間，電腦程序至少要從25!(1.6×1025)種順序中找到最佳裁剪路徑，程序運(yùn)算量非常大[5]。

1.2 樣版輪廓幾何軌跡特征

在數(shù)控裁剪機(jī)裁剪過程中，排料圖中待裁剪的衣片以矢量圖形格式在電腦系統(tǒng)中進(jìn)行數(shù)據(jù)處理，各片衣片的輪廓線不是實(shí)際的曲線，而是由若干個(gè)點(diǎn)連接而成的封閉多邊形，此封閉多邊形設(shè)定為裁刀裁剪衣片時(shí)所走的有效路徑。有效路徑分為有效曲線路徑和有效直線路徑。通過分析、統(tǒng)計(jì)得出樣本排料圖中的曲線裁剪路徑占總路徑百分比和直線裁剪路徑占總路徑百分比，統(tǒng)計(jì)數(shù)據(jù)見表2。

表2 針織休閑褲線段統(tǒng)計(jì)表Tab.2 Segment statistics of knitting leisure trousers

由表2可知，樣本排料圖中曲線路徑百分比的平均值是78%，直線路徑所占百分比的平均值為22%，曲線路徑所占百分比的平均值大于直線路徑所占百分比的平均值。

在數(shù)控裁剪機(jī)裁剪服裝面料過程中，裁刀走直線路徑時(shí)，走刀容易保持較高裁剪精度，裁片質(zhì)量高；裁刀走曲線時(shí)，裁刀走刀角度容易偏差，裁刀裁剪精度降低，裁片質(zhì)量下降。排除服裝面料特性的影響，裁片要保證較高裁剪精度主要取決于裁片中曲線的比例高低，曲線越多，衣片裁剪難度越高，對(duì)數(shù)控裁剪機(jī)的裁剪精度要求越高。針織休閑褲的直線路徑百分比的平均值小于曲線路徑百分比的平均值，裁剪針織休閑褲具有較大難度[6]。

2 裁剪路徑優(yōu)化

2.1 衣片外輪廓幾何定義

待裁剪的針織休閑褲排料圖中包含若干片獨(dú)立的衣片，衣片外輪廓構(gòu)成各個(gè)衣片，直線、曲線和圓弧是衣片外輪廓的基本元素，這里，定義衣片外輪廓為環(huán)(H)，組成衣片外輪廓的基本元素為邊(E)，邊的端點(diǎn)為頂點(diǎn)(V)。排料圖確定后，每片衣片在排料圖中的位置是固定的，而且每片衣片的裁剪路徑也是相對(duì)固定的，因此可以用每片衣片外輪廓的特征點(diǎn)代替衣片的具體幾何信息，衣片外輪廓可以是直線、曲線或圓弧。曲線和圓弧的頂點(diǎn)是曲線和圓弧的起點(diǎn)和終點(diǎn)，直線的頂點(diǎn)是直線的兩端。基于以上參數(shù)的設(shè)定，在本文中做出如下定義：1床針織休閑褲排料圖中衣片的總數(shù)量為n，第i片衣片記為Hi(i=1,2,3,…,n)，Hi對(duì)應(yīng)的頂點(diǎn)總數(shù)記為V(i)，第i片衣片對(duì)應(yīng)的第j個(gè)頂點(diǎn)記為Vij(i=1,2,3, …,n;j=1,2,3, …,V(i))，如圖1所示。

圖1 衣片外輪廓示意圖Fig.1 Diagram of cut-parts contours

2.2 蟻群算法

針織休閑褲排料圖中的裁剪路徑優(yōu)化問題可簡(jiǎn)化為一系列點(diǎn)集的最短路徑問題，多點(diǎn)的路徑優(yōu)化問題可以歸結(jié)為旅行商問題即TSP進(jìn)行求解。旅行商問題直觀描述是：旅行家從某城市出發(fā)，經(jīng)過n個(gè)城市，希望找到1條既能經(jīng)過各個(gè)城市，又能每個(gè)城市僅經(jīng)歷1次最后回到出發(fā)城市的最短路徑。旅行商問題中的n個(gè)城市相當(dāng)于裁剪路徑優(yōu)化問題中的n片待裁剪衣片，旅行商能夠找到的1次不重復(fù)走遍所有城市的先后順序就是裁剪路徑優(yōu)化問題中的衣片的裁剪順序，而以此順序獲得的各城市間的行走路徑相當(dāng)于裁刀走刀相對(duì)優(yōu)化的路徑[8]。

2.2.1 蟻群算法的數(shù)學(xué)模型

利用蟻群算法求解排料圖中裁刀裁剪的TSP問題，蟻群算法主要是確定待裁剪衣片的最佳裁剪順序，可以把每片裁片的形心看成求解TSP問題中的每座城市，求解的目標(biāo)是使裁刀所走空行程長(zhǎng)度最短，即旅行商所走的城市間的路徑之和最短。蟻群算法求解TSP問題包括路徑選擇、信息素更新2個(gè)步驟，信息素是指螞蟻在所經(jīng)過的路徑上留下的一種揮發(fā)性分泌物，其數(shù)學(xué)模型如下。

式中：Tk(k=1,2,…,m)為螞蟻k已走過城市的集合；ηij為城市i移動(dòng)到城市j間的距離因子，通常取值為城市i到城市j之間距離的倒數(shù)，即ηij=1/dij；α表示信息素濃度的相對(duì)重要程度；β表示啟發(fā)信息的相對(duì)重要程度[9]。

2)信息素更新。設(shè)信息素的揮發(fā)系數(shù)為p(0

2.2.2 蟻群算法實(shí)現(xiàn)

采用蟻群算法的針織休閑褲裁剪路徑優(yōu)化的具體流程如圖2所示。

注：Nc為迭代步數(shù)，Nmax為預(yù)定的迭代次數(shù)。圖2 蟻群算法流程圖Fig.2 Flow chart of ant colony algorithm

2.3 裁剪起始點(diǎn)的確定

利用蟻群算法確定針織休閑褲排料圖中的衣片裁剪順序后，再采用改進(jìn)后的最近鄰算法確定各片衣片外輪廓的裁剪起始點(diǎn)，具體步驟如下：

1)以U0為裁剪原點(diǎn)，令Uk=U0,U={U0};

2)根據(jù)已確定的裁剪順序，尋找第1片衣片H1對(duì)應(yīng)的頂點(diǎn)集V1={V11，V12，…，V1V(1)}中距離Uk最近的頂點(diǎn)U1=V1j(對(duì)應(yīng)衣片Hi),令Uk=U1，然后在H集中刪掉H1及對(duì)應(yīng)的H1頂點(diǎn){Vi1，Vi2，…，V1V(1)};

3)按照裁剪順序遍歷剩下的未運(yùn)算的衣片H對(duì)應(yīng)的頂點(diǎn)集，重新設(shè)定在第2步中確定的裁剪起始點(diǎn)為搜索起點(diǎn)，按照第2步的搜索規(guī)律，確定剩下裁片的裁剪起始點(diǎn)，同時(shí)加入到裁剪起始點(diǎn)集U中，如果H中還有元素繼續(xù)執(zhí)行第2步，如果H中元素個(gè)數(shù)為零程序結(jié)束，輸出結(jié)果U={U0，U1，…，Ui,…，Un}，根據(jù)各個(gè)裁剪起始點(diǎn)的位置生成裁刀的空行程走刀路徑。

3 實(shí)驗(yàn)驗(yàn)證

使用該算法對(duì)8份針織休閑褲樣本的排料圖生成模擬裁剪路徑，空行程長(zhǎng)度比未優(yōu)化前平均縮短32%。圖3為針織休閑褲空行程路徑對(duì)比示意圖，圖中粗實(shí)線表示裁床裁刀空行程的軌跡。圖3(a)為優(yōu)化前按照一般數(shù)控裁剪機(jī)的裁剪路徑算法獲得的空行程裁剪路徑圖，空行程長(zhǎng)度為21 604 mm，圖3(b)為經(jīng)過本文提出的算法優(yōu)化后得到的空行程裁剪路徑圖，空行程長(zhǎng)度為14 865 mm，將圖3(a)空行程距離縮短了6 739 mm。實(shí)驗(yàn)結(jié)果證明了本文算法的可行性和優(yōu)越性。

圖3 空行程路徑對(duì)比示意圖Fig.3 Comparison diagram of non-cutting path. (a) Original non-cutting path; (b)Optimal non-cutting path

4 結(jié) 論

本文針對(duì)針織休閑褲這一大類成衣，提出了基于樣版特征的裁剪路徑優(yōu)化算法，該算法先用蟻群算法優(yōu)化衣片裁剪順序，再采用改進(jìn)的最近鄰算法優(yōu)化衣片外輪廓裁剪起始點(diǎn)，得到以下結(jié)論：基于樣版特征進(jìn)行裁剪路徑優(yōu)化是可行的。本文算法可使空行程路徑長(zhǎng)度縮短30%左右。本文算法有效地縮短了針織休閑褲裁剪空行程長(zhǎng)度，但是該算法是否可推廣至其他大類成衣，還有待于進(jìn)一步研究。

FZXB

[1] 吳娟, 楊兵, 劉達(dá)新, 等. 基于Open CASCADE的服裝排料系統(tǒng)的研究與開發(fā)[J]. 合肥工業(yè)大學(xué)學(xué)報(bào): 自然科學(xué)版, 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] 王姝, 金福江. 服裝矩形樣片組合優(yōu)化模型及其求解算法[J]. 武漢理工大學(xué)學(xué)報(bào): 信息與管理工程版, 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] 薛福平. 針織服裝設(shè)計(jì)概論[M]. 2版. 北京: 中國紡織出版社, 2008:3-5. XUE Fuping. Design for Knitting Wear[M]. 2nd ed. Beijing: China Textile & Apparel Press, 2008:3-5.

[5] 吳華鋒, 陳信強(qiáng), 毛奇凰, 等. 基于自然選擇策略的蟻群算法求解TSP問題[J]. 通信學(xué)報(bào), 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] 金愛燕. 大類成衣裁剪路徑的分析與優(yōu)化研究:針織休閑褲[D]. 蘇州: 蘇州大學(xué), 2014: 17-18. JIN Aiyan. Analysis and optimization of garment cutting path:knitting leisure trousers[D]. Suzhou: Soochow University, 2014: 17-18.

[7] 張軍, 劉羽, 盧奉良. 蟻群算法解決TSP問題的并行化研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 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] 許世杰. 基于過程優(yōu)化的蟻群算法研究與應(yīng)用[D]. 濟(jì)南: 山東師范大學(xué), 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—)，女，碩士生。研究方向?yàn)閿?shù)字化服裝制造。尚笑梅，通信作者，E-mail：shangxiaomei@suda.edu.cn。

TS 941.62

A