（服装设计与工程专业论文）服装排料技术的研究[服装设计与工程专业优秀论文].pdf

进行优化，以提高整个排料的利用率和减少程序的运行时间。如设定 按照衣片的面积( 或长度) 先排序，然后再排料等；提出应用正弦曲 线对衣片的各种运动( 如移动、交换、旋转和镜像) 进行动态分配， 减少重叠的计算量，优化程序的运行时间；在排料完成后，由于衣片 之间还存在一些空隙和重叠，因此又对衣片进行了空隙挤压和重叠分 离。( 2 ) 提出应用面积进行多边形的方向的判别和衣片的重叠判断， 这种方法的应用使得程序易于实现，且计算机的运算量较小。 课题的不足是由于对程序不够专业，所以程序有些方面的计算量 较大影响了整个程序的优化。课题暂时还只是局限在服装排料算法的 研究上，在进一步研究中，将考虑服装工艺、文件格式标准化等方面 的要求以增强软件的完整性和实用性。 关键词服装排料，服装c a d ，模拟退火算法、启发式算法 s t u d yo nm a r k i n gt e c h n o l o g yi na p p a r e la r e a a b s t r a c t m a r k i n gi so n eo ft h ei m p o r t a n tt e c h n o l o g i e si na p p a r e lf a c t o r y , t h e m a r k i n gt i m ea n df a b r i c su t i l i z a t i o nr a t ea f f e c tt h ef a c t o r y sp r o f i ta n d c o m p e t ea b i l i t y t h ef a b r i c su t i l i z a t i o nr a t eo f m a r k i n gp r o j e c ti so n eo f t h e i m p o r t a n ts t a n d a r d s t oe v a l u a t et h eq u a l i t yo f t h em a r k i n gs o f t w a r e t h ee x p l o i t u r eo fs o m ec o m m e r c i a la p p a r e lc a ds o r w a r e si sw e l l ， b u tt h em a r k i n gm o d u l es t i l lh a v es o m et e c h n o l o g yp r o b l e m s ，s u c ha st h e a u t o m a r k i n g sf a b r i c su t i l i z a t i o nr a t ei sl o w e rt h a nm a n u a lm a r k i n g ，a n d t h ed u m m ym a r k i n gi sh a r dt or e p r e s e n tt h er e a l i t yp a t t e ma n df a b r i c ，s oi n s o m ef a c t o r i e st h ea u t o - m a r k i n gs y s t e mo n l yu s et of o r e c a s tc o n s u m p t i o n f o rb o o k i n gf a b r i c sa n dq u o t i n gp r i c e ，n o tu s ei ti nr e a lp r o d u c t i o n a p p a r e l m a r k i n ga r i t h m e t i ci st h ec o m m e r c i a ls e c r e t so fa p p a r e lc a ds o f t w a r e c o m p a n y , s ot h i ss t u d yo nm a r k i n gt h e o r ya n de x p l o i t u r ea b o u tm a r k i n g s o f t w a r ea r eb o t hb a s e do ns e l f - d e t e r m i n a t i v ei n n o v a t i o n t h et h e s i s si n n o v a t i o nh a v e2p o i n t s ：( 1 ) u s e dt h es i m u l a t e d a n n e a l i n ga r i t h m e t i ct oc o n t r o lt h ep a t t e r na r r a n g ep r o c e s s ，a d d e dt h e h e u r i s t i ca r i t h m e t i ct ot h ep r o g r a mt oi m p r o v et h ef a b r i c su t i l i z a t i o nr a t e a n dr e d u c et h er u n t i m eo fp r o g r a m s u c ha st h es o f t - w a r ea r r a n g e dt h e o r d e ro f p a t t e m sa c c o r d i n gt ot h ea r e ao rl e n g t h ，a p p l i e ds i n u s o i dt o d y n a m i cd i s t r i b u t ea l lk i n d so fm o v e m e n to fp a t t e r n ( s u c ha sm o v e ，s w a p ， r o t a t ea n dm i r r o r ) ，c u td o w nt h ec o m p u t eq u a n t i t yo fo v e d a p ，o p t i m i z e d r u n t i m eo ft h ep r o g r a m , a n ds q u e e z e dt h ei n t e r s p a c e sa n ds e p a r a t e dt h e o v e d a pa f t e rt h em a r k i n g ( 2 ) t h es o f t w a r ea p p l i e dt h ea r e at od i s t i n g u i s h t h ed i r e c t i o no f p o l y g o n a la n do v e r l a p ，t h i sm e t h o dm a d et h ep r o g r a me a s y t or e a l i z ea n dt h ec o m p u t eq u a n t i t yl e s s t h es h o r t a g eo ft h et h e s i si st h ea u t h o rn o ts p e c i a l i z e di nc o m p u t e r p r o g r a m ，s os o m ep a r t so f t h ep r o g r a m a r en o tv e r yg o o d ，t h a ta f f e c t e dt h e o p t i m i z eo ft h ew h o l ep r o g r a m t h et h e s i si so n l ys t u d yo nt h ea p p a r e l m a r k i n ga r i t h m e t i c i nt h ef u t u r e ，i tw i l lc o n s i d e ra p p a r e lt e c h n o l o g y , f i l e f o r m a ts t a n d a r d i z a t i o ne t c t oe n h a n c et h ei n t e g r a l i t ya n dp r a c t i c a b i l i t yo f t h es o f t w a r e m e i q i nl u ( f a s h i o n1 ) e s i g na n de n g i n e e r i n g ) s u p e r v i s e db ya s s o c i a t ep r o f e s s o ry i s o n gc h e n a n da s s o c i a t ep r o f e s s o ry u a n j im i a o k e yw o r d s ：a p p a r e lm a r k i n g ，a p p a r e lc a d ，s i m u l a t e da n n e a l i n g a r i t h m e t i c ，h e u r i s t i ca r i t h m e t i c i v 附件一： 东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师的指导 下，独立进行研究： 作所取得的成果。除文中己明确注明和引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写过的作品及成果的内容，论文为本人亲自撰写，我对所写的内容负 责，并完全意识到本声明的法律结果由本人承担。 附件二： 学位论文作一：防丛 日期：( 三 ，6 年f1 月i 奇日 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部 门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权东华大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。 保密口，在年解密后适用本版权书。 本学位论文属于 不保密臣r 口 学位论文作者签指导教师签名 ( 冬氆殍 目期：。e 年厶。日 东产大学硕士学垃论文 第一章前言 第一章前言 1 1 本课题的研究背景与意义 1 1 1 本课题的研究背景 2 0 世纪6 0 年代，随着计算机的出现，信息技术的发展，人们很快将计算机 信息技术应用到各行各业，于1 9 5 9 年1 2 月在麻省理工学院召开的一次研讨会上 首次提出了c a d 的概念，随后迅速对c a d 技术展开研究并将它应用在汽车及机械 制造等行业，并在这些行业中取得了显著的效益。进入7 0 年代后，亚洲纺织服装 产品依靠其低廉的成本售价开始闯入欧美等国家市场，欧美等国家的纺织服装业 为了节约成本，提高效率，应对激烈的市场竞争，便产生了将在电子和机械行业 已有成功应用的c a d 技术应用到服装中来。服装c a d 作为现代计算机技术与传统 服装行业相结合的产物便应运而生“1 。目前国外较有影响的服装c a d 软件有法国 力克、美国格柏、德国艾斯特、日本东丽、旭化成；国内有航天、爱科、深圳富 怡、丝绸之路以及智尊宝坊等。 1 1 1 1 传统服装人工排料的缺陷捌 纸样的排料工作，是服装厂重要的技术工艺之一，服装排料的用料率直接对 应着服装的成本及利润。排料的合理性影响面料的利用率，合理的排料可以大大 提高面料利用率，降低产品成本。虽然经验基础上的传统手工排料的面料利用率 比较高，但也存在以下七点不足。 1 ，排料占用空间大，劳动强度大。手工排料是排料人员直接在裁床上反复试 排，若待排纸样的数量很大，则排料人员的劳动强度很大，排料效果也很难保证。 2 、周期长。对于批量服装裁剪，特别是大批量的作业，排料图每节省一点面 料，对企业来说都具有很大的意义，因此企业在确定排料图时很慎重，尤其是对 高档面料。对于每一床排料图，均要通过反复试放，不断修改，再确定最佳的排 科图，因此手工排料占用的时间较长。 3 、容易出现多排、漏排、错排的现象。人工排料时排料技术人员要有耐心和 责任感，否则容易出现多排、漏排和错排现象如对称衣片排料时共同使用一块 纸样，需要技术人员在排料时将纸样正反各排一次。 东。产太学动e 学位论文 第一章前言 4 ，面料估算的精度较低。传统人工排料，往往是先排一件服装估算面料利用 率，这种估算方法的精度较低。裁剪完成后再用公式( 1 - 1 ) 来得出面料的实际利用 率，以验证估算的准确性，如果发现有更大利用率方案时，浪费的面料和多定购 的面辅料的损失已无法挽回。 利用率= ( 原面料重量一废科重量) 原面料重量( i - 1 ) 5 、最佳排料图不便于归档。手工排料是直接在裁床上进行试排，一般是用纸 l ：l 将排科图描下，排料图很大，对于最佳的排料图不便于归档和查看。 6 、排料利用率的依赖性较大。排料利用率依赖排料人员工作经验，经验丰富 则可以较快的找到合适的排料图；若经验不足，寻求最佳排料图时就需要较长的 时间，还易受排料人员的工作时间、情绪等许多不确定性因素的影响。 7 、不能和现代计算机辅助制造设备相衔接。传统手工排料后一般是采用常规 裁剪机( 如直刀式裁剪机) 裁割，无法和自动裁床相连接。如要应用自动裁床， 就必须将手工排料图输入电脑，即采用服装c a d 交互式排料作业方式。 1 i 1 2 服装g a d 排料的优点 服装c a d 自动排料的一般思路是，排料工作人员将经过审核过的纸样调入排 料系统的待排区域，然后设定面料参数( 如面料门幅、缩水率等) 以及实际工艺 对纸样所许可的操作，如纸样的微量旋转和镜像等，再由系统自动地从待排区域 中选取纸样，根据软件事先设定的计算方法自动地配置纸样，让纸样自动寻找合 适的位置靠拢已排纸样或面料边缘。在排料的同时自动报告用料长度，面料利用 率，待排纸样数目，以及所有纸样的排料情况。服装c a d 排料系统具有如下五点 优点。 1 、排料占用空间小。计算机排料就是以计算机屏幕代替大面积的排科工作台 进行纸样排料，与传统的手工排料相比优势很明显，仅需要一台装有排料软件的 电脑就可以。 ， 2 、缩短了生产周期。无需在裁床上进行试排，这样一个排料图方案在裁剪的 时候，仍然可以在电脑上进行其它分床方案的排料，服装c a d 自动排料还可以将 每床待排作业以队列的形式输送到系统中进行自动排料，然后由系统自动地报告 所选择的每床最优排料图，排料的效率较高，减少了人的等待时间，也缩短了生 产周期。 东华犬学硕学位论文第一章前言 3 、误差小。计算机具有较强的记忆和存储功能，它可以自动报告已排纸样和 未排纸样，因此服装c a d 排料不会出现多排、漏排及错排的现象。 4 、快速估科。计算机具有强大的运算功能，自动排料系统可以进行快速的估 料，方便企业向客户报价，预定面料等。 5 、便于保存。计算机可以将较优的排料图进行保存，文件保存方便，占用空 间也很小，如有相同裁剪方案可以直接调用裁剪，或是以原方案为参考，继续排 料以尽可能的节省面科。 1 i 2 本课题的研究意义 尽管市场上有比较成熟的商业服装c a d 软件，如美国的格柏、法国的力克、 德国的埃斯特等等，这些软件的排料系统开发得比较成熟，但这些商业软件的开 发思路、具体采用的算法等等一般作为商业秘密不予以公开。而企业甚至高校仅 仅是将服装c a d 作为应用工具，而很少对软件的开发思路和算法进行研究，作为 高校等科研机构有必要对软件开发的原理及算法等进行研究，这种自主创新的过 程是十分有益而且是十分必要的，将促使服装c a d 软件不断地完善。 虽然市场上的一些商业软件开发得比较成熟，但排料问题仍然存在技术瓶颈， 表现在服装c a d 自动排料的利用率与人工排料相比还有一定的差距。这也是目前 许多服装厂只是将自动排料系统用于估料和报价方面，而很少应用到生产实践中 的原因。 随着优化方法及软件应用技术的发展，将合适豹优化方法运用到排料技术中 去是排料领域的发展趋势。课题尝试将模拟退火算法和启发式算法应用到排料技 术中来，希望能提高自动排料的利用率，节省面料，因此课题的研究对服装业的 发展有一定的意义。它的研究成果对汽车、航空、机械、制鞋等行业也有着很好 的借鉴和参考价值。 i 2 国内外有关服装排料技术的研究历史及现状 服装排料就是在给定的面料宽度和长度上按工艺要求排放所有纸样，纸样之 间不能相互重叠( 为提高面料的利用率可允许少量的重叠) ，要达到用料率最高。 如何摆放纸样最合理，最能节省面料，是服装排料要解决的问题。 3 东华大学硕t 学位论文第一章前言 1 2 1 国内外有关排料研究历史及现状 多年来人们一直在研究排料问题，力图减少材料的损耗。寻找合适的切割图 形( 矩形、规则多边形) 或是将其它复杂的多边形通过组合包络成最小矩形再进 行矩形排料；寻找合适的人工智能优化方法( 启发式搜索方法、遗传算法、模拟 退火算法等) 。排料问题属于n p c ( n o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e ) 问 题“1 ，计算相当复杂，容易产生组合爆炸，对于这类问题即使采用计算机结合现 代优化方法也难以寻找出最优的排料方案，目前只有在可以接受的时间内，寻找 到可以接受的排料方案。 1 2 1 1 矩形排料 排料问题较为复杂，其中矩形排料问题由于其广泛的应用和比较简单的几何 特征，研究工作开展得比较早3 ，六十年代初，g i l m o r e 和g o m o r y 用线性规划的 方法和背包( k n a p s a c k ) 算法研究了矩形图形的二维排样问题”。此后，人们围 绕规则图形排样算法作了大量的工作。目前矩形件在矩形原料上的排料研究得比 较成熟而且应用也较好，许多较复杂的图形也是通过转化成矩形后，再用矩形的方 法进行排料。矩形排料的主要算法有线性规划h 2 3 、动态规划、整数规划m 1 、整 数线性规划、启发式算法渊、遗传算法州、模拟退火算法啪瑚1 等。 1 2 1 2 不规则图形的形排料 7 0 年代以来，由于实际应用的需要，人们开始对不规则零件的排样问题进行 了研究。不规则图形的排料问题比较复杂，其复杂性主要是由图形的不规则形状 和不同的次序组合所引起的。由于待排零件形状不规则，有时材料也可能是不规 则的图形( 如服装排料中的毛皮类排料) ，所以待排样之间的靠接、判交等处理比 较复杂，计算量大。加上不同的次序组合可能出现的若干种不同的排料组合，也 增加了选择的复杂性。对于不规则图形的排料通常有两种方法。 一是求单个或多个不规则图形的最小包络矩形，将不规则图形的排料问题转 化成比较简单、算法成熟的矩形排料问题来实现，如先对待捧样进行单排如图卜l ( a ) ( 将相同的图形按一定的角度和步距排放) 、对排如图卜l ( b ) ( 将完全相同 的图形两两成组，其中一个旋转1 8 0 0 后再与原来的组合) 的方式组合，然后取其 最小包络矩形，再用矩形进行排料。这种方法的优点是使得问题比较简单，缺 点是对于高度不规则的图形会造成很大程度的原料浪费，失去可行性。 4 东毕大学硕士学位论文第一章前言 二是应用数学优化方法直接对任意多边形进行排料。皮献 4 提出了一种多边 形的表示方法( 等距扫描区间表示法) ，并提出了一种高效的多边形判交与定位算 法( 基于b l f 策略的扫描定位启发式算法) ，算法极大地降低了几何复杂度对定位 算法的影响，能够处理任意形状的多边形之间的排科定位，甚至允许存在无效区 域，其不足是多边形的几何表示过程变得更加复杂“1 1 2 2 服装c a d 排料的应用现状 图1 - 1 ( a )单排 图1 - 1 ( b )对排 虽然服装c a d 具有许多优点，在国外应用也很成熟，实际生产中主要是打版 和放码模块应用较多( 尤其是在我国) 。虽然有的服装c a d 排料软件开发得较好， 但其也只是主要应用于一些低档面料服装的加工，对于高档面料服装的加工尤其、 是小批量高档服装的制作，服装企业般还是采用手工排料，这主要是因为( 1 ) 计算机排料是虚拟的纸样在虚拟的面料上排料，且计算机屏幕较小，难以准确地 把握排料的真实情况；( 2 ) 我国的劳动力较低廉，而且我国主要是加工企业，企 业的加工利润本来就很有限，所以企业不会以牺牲面料的成本为代价，这些企业 的c a d 排料模块主要用在海关报价方面，并没有用于实际生产：而国外多数企业 是自有品牌，利润较高，另外他们的工时费用很高，所以国外企业综合情况后采 用服装c a d 排料系统进行服装排料。服装排料模块在我国没有得到很好应用的原 因关键还是其排料的智能性不高，不能达到人工排料的效果。 东华大学硕t 学位论文 第一章前言 1 2 3 与本课题相关的前沿问题 自排料技术研究以来，人们提出了多种优化方法来解决排料问题如人工神经 网络法、遗传算法、启发式算法、模拟退火算法等。其中人工神经网络求解优化 排科问题比较困难，不宜用于非矩形的排料；遗传算法由于其对所求问题的要求 没有特殊的限制，便于将非矩形零件的图形运算与遗传算法有机集成，所以有很 多方案可以求解优化排料问题。遗传算法有着良好的全局搜索能力，在非矩形零 件的布局和排料中有着较好的表现，但遗传算法容易产生早熟现象，局部寻优能 力较差；模拟退火算法具有较强的全局搜索能力。在处理排料问题时，人们一般 采用混合算法，将几种优化方法相互协同，各取所长。 本章小结 本章主要总结了服装人工排料的缺陷( 排料占用空间大，劳动强度大；周期 长；容易出现多排、漏排、错排的现象；面料估算的精度较低；最佳排辩图不便 于归档；排料利用率的依赖性较大；不能和现代计算机辅助制造设备相衔接) ，计 算机排料的优点( 排料占用空间小；缩短了生产周期；误差小；快速估料；便于 保存) ，国内外有关排料技术的研究历史和现状以及服装摊料软件的应用现状并指 出了服装排料技术的研究意义。 6 东+ 大学硕士学位论文 第二章捧科技术发展简介 第二章排料技术发展简介 2 t 排料问题的主要应用领域 社会生产应用中许多行业都涉及到排料问题，只是说法有所不同。如：管材 下料或棒材下料、玻璃切割、钣金切割、报刊排板、服装裁剪，皮革下料、家具 下料、冲裁件排样、集成电路电子元件的布局、造船、运输以及发电设备生产中 都存在大量的排料问题。 2 2 排料问题的分类 排料问题按零件的维数划分为：一维排料( 如管材下料) 、二维排料( 玻璃切 割、钣金切割、报刊排板、服装裁剪、皮革下料、集成电路电子元件的排布) ，三 维( 集装箱装箱、车辆装箱) 等。按照被排零件的形状可分为：规则形状( 如单 一零件等) ，不规则形状( 异形件等) 。 2 3 排料问题的难点与求解难度 算法对时间和空间的需要称为算法的时间复杂性和空间复杂性按照计算复 杂性理论研究问题求解的难易性，把问题分为p 类( 具有多项式时间算法嘲) 、酐 类( 可在多项式时间里检验的问题嘲) 和n p c 类。n p c 类是n p 中最困难的问题， 这类问题的求解时间与问题的规模呈指数级关系增长恻“1 。排料问题已被证明属于 n p c 类问题。1 。 对于一维下料优化问题就是进行不同长度的优化组合以使材料利用率最高， 即将m 种零件，长度为h 。，数量为m ，在长度为l 的原料上排放，使所用原材料 最少? 对于二维排料问题除涉及到长度方向，它还增加了宽度，二维排科问题可描 述为：将一系列待排料p ，p 2 ，p l 合理的排放在原料p 中，使原料的利用率最高， 并满足下列条件： 7 东华大学硕士学位论文 第二章排辜 技术发艇简介 ( 1 ) p - ，p j 互不重叠；i ，j = l ，2 ，n ； ( 2 ) p 必须在p 内：i ，j = 1 ，2 ，n ； ( 3 ) 满足一定的工艺要求。 每一个排料问题，它们的复杂性各不相同，在二维排料问题中最复杂的就是不规 则零件在不规则原料上的排料，如服装中毛皮类的排料。 对于三维装箱问题，就需要在长、宽、高三个方向综合考虑最优，同时还需 考虑箱体本身的承重、平衡、物体搬运的难易等要求。 从以上对三类排料问题的分析可以看出随着维度的增加，排料的复杂度也在 增加，那么排料问题的解决难度也在增加。 2 4 排料问题算法及方法 2 4 1 排料问题的算法 对于排料一类的问题人们提出了许多算法如线性规划，整数规划、动态规划 等。其中线性规划和整数规划在矩形排料中有成功的应用，但不适用于不规则多 边形的直接排料“”。 2 4 1 1 遗传算法 s e g e n r i e c h 和b r a g a 运用遗传算法解决了多件多排问题，即在定宽无限长的 原料上正交排列给定的矩形件，将排样问题转化为排列问题，把问题的解表示成 数字串的形式，然后再对数字串进行选择、交叉和变异操作，从而求得新的解嘲。 在用于解决排料问题的一些复合算法中人们一般将遗传算法用于确定排料元件的 顺序，然后再用其它方法对排料元件进行定位。 2 4 1 2 神经网络法 c i h a n h d a g l i 和p i p a t p o n gp o s h y a n o n d a 运用神经网络解决排料问题洲 他们提出系统有三个模块：神经网络模块、智能排样模块和优化模块。神经网络 模块是用人们排样的实际经验指导计算机自动排样，实际上是提供了选择的规则； 智能排样模块是根据第一个模块提供的选择规则结合技术要求和条件对零件进行 排样；最后由优化模块对排样结果进行优化，求出最优解。该算法较好地结合了 人的智能因素，使排样具有智能性，缺陷是该系统不具备开放性，没有自学习功 东华大学硕上：学位论文第二章摔料技术发展简介 能。后来p o s h y a n o n d a 和d a g l i 结合神经网络和遗传算法对排样问题提出了一种 解决排样系统学习功能的新方法，但并没有考虑不规则件的排样。 2 4 1 3 模拟退火算法 模拟退火算法是从某一个初始点开始在一定的邻近范围内搜索。如果在邻域 内搜索到某状态的目标函数数值比当前状态更优，则用此状态代替当前状态继 续搜索。模拟退火算法的最大特点是它能够以一定概率接受劣质解，即使算法陷 入了局部最优状态，在经过足够长时间后，也能跳出陷阱，从而达到全局最优。 为了验证模拟退火算法的搜索能力，k a d o w n s l a n d ( 1 9 9 3 ) 用模拟退火算法对许多 组合优化问题进行了试验验证。结果表明，模拟退火算法是一种有效的全局搜索 方法，并说明了该算法的基本要求是定义适当的邻域结构。邻域结构是决定在搜 索过程中所产生的新解是被接受还是被放弃的主要参数，所产生解的好坏对此参 数的选取很敏感“。 2 4 1 4 启发式算法 启发式算法是为了提高搜索效率才提出的，它是由直观或经验所构造的算法， 用它来指导计算机在可接受的代价( 一般指接受时间和占用资源) 下给出组合优 化问题每一个实例的一个可行解，但可行解与最优解的偏离程度是不可知的。因 为在一些实际问题中，当问题的规模很大时，最优算法的计算时问和资源消耗是 无法接受的，只能通过启发式算法求出一个可行解。启发式算法的共同特点是放 宽对计算结果与最优解偏离程度的限制，不过分追求一定求出最优解。 启发式搜索法根据实际经验来简化搜索进程，搜索过程一般包括检查搜索空 间、估价可能有解的各种不同路径、记录已经搜索到的各个路径。为了简化搜索 并且减少搜索过程中的大量可选路径，根据所给问题的信息可得到的启发知识或 “经验法则”来确定搜索方向。这种算法的本质就是把与问题相关的具体知识加 进算法中去，以提高算法的效率3 2 4 1 5 降维启发式线性规划算法 降维启发式线性规划算法是在线性规划模型的基础上提出的种新方法，即 通过将二维排料降为一维排料启发式方法，将零件成组看待，使得零件组一个方 向的长度近似于原材料的长( 或宽) 方向的长度，而使零件组另一个方向在原材料 的宽( 或长) 方向套裁，那么板材就变成了”条材，这种零件组就称为扳条。这种 9 东牛大学硕士学位论文第二章持科技术发展商介 算法简化了计算过程，提高了原材料利用率“”。 2 4 2 排料问题的解决方案 2 4 2 1 基于最左最下( b o t t o ml e f t ) 原则的8 l 策略“” b l 条件即如果排样图中任何一个矩形件在不干涉和不超出材料边界的情况 下，均不能向下、向左移动。b l 方法是满足b l 条件的排放法，一般事先会设定 矩形的排列顺序，排列方法为将r 。( i = 2 ，3 ，n ) 置于材料右边最大高度处，交 替向下向左移动r 。，直至r 。无法再向下向左移动为止( 即接触到其它零件( 衣片 等待排样) 或材料边界为止) ，求出此时的最大高度。重复上述过程，直至所有零 件排放完毕，最后所得的高度即为排料图的高度。b l 方法的缺陷在于有些排放方 案无法得到，如图2 - 1 。 图2 - 18 个矩形排成的最优排样图 文献 1 5 中对上述方法进行了改进，在向下向左移动时，采用了向下优先的 原则，按照编码( i = l ，2 ，3 ) 这两种方法的排放过程如图2 2 所示： 噩方法下台阶方法 图2 - 2b l 方法和下台阶方法 分析b l 策略和下台阶方法可以发现，b l 策略除了本身具有的缺陷外，还容 易发生材料左侧排放偏高的情况，而下台阶方法则易发生右侧偏高的情况。这两 种方法主要运用在定长定宽且长度不太长如板材等的排料中，而对于服装排料由 于服装面料的长宽比很大，若用这两种方法，则衣片需要移动的次数比较多，将 东华犬学硕上学位论文第二章排科技术发展赫介 会增加计算机的运算量。 文献 7 提出了最低水平线算法，克服了上述b l 策略的缺陷，对于b l 策略所不 能得到的排料图2 1 ，最低水平线法按照l ，2 ，3 ，4 ，5 ，6 ，7 ，8 的顺序可得到。 2 4 2 2 剩余矩形匹配法( l r f ) o ” 将零件按面积排序，依次按剩余矩形最佳匹配原则排入材料。如图2 3 ，将第 一个零件r 排入材料左下角后，材料剩余的矩形有2 个：( r 。+ r 。) 和( r 。+ r 。) ，两个矩 形含有公共部分r 3 ，从这两个矩形材料中选出一个将下一个矩形零件r ：放入，选择 条件是能排下且零件的长或宽与这两个矩形的某一边最接近。图中r 。的长边与 ( r ：+ r 。) 的短边最接近，故如图2 - 3 放置。 r lr 3 熊骂 r ， ：鬣7j 。1 节i 。j。 毳，鼍= ：， ，一 “r 2 一- 鼯。叠珏。： 一二： 一 图2 - 3 剩余矩形匹配法 选出( r 2 + r 3 ) 这个矩形后，另外一个矩形尺寸根据排入零件占用的矩形面积调 整为r 。或( r 。+ r 。) ，图中为r 。排入r ：后材料的剩余矩形包括r 。和( r ：+ r 0 中排入r 。后 剩余的两个矩形。 依次类推，排入第k 个零件前，扳材剩余了k 个矩形( 其中至少有两个是相互 重叠的) ，从这些矩形中选出一个放入第k 个零件。如果选中的矩形与其它矩形有 重叠部分，则将重叠部分划归选中矩形，调整另外一个矩形的尺寸。 为了提高效率，当剩余矩形的长或宽小于了所有矩形零件中长、宽的最小值 后，该剩余矩形就被从剩余矩形表中去掉。零件的排入顺序同样决定材料的利用 率。 2 4 2 3 多边形边界移动法 轮廓边的匹配方法为按照一组基于零件面积、轮廓周长和复杂性的性能参数 进行排序，选择两个具有最高指标的零件，按照逆时针方向匹配每一边后，以形成 的最小包络矩形确定排放位置，这个过程不断重复直至所有零件排放完毕。由于 零件中存在许多可匹配的边需要进行大量的测试，因此这种算法计算量大，速度 东。产人学硕士学位论文第二章摊料技术发展简介 慢1 “。 2 4 2 4 最小矩形包络法 在二维排样研究中，相对任意多边形排样，矩形排样算法是比较成熟的，因 此对二维任意多边形排样，早期是首先求得任意多边形的最佳包络矩形，然后采 用矩形排样算法进行排样。 一般地，只有当多边形两相邻凸顶点间的边平行于某坐标轴时方可能产生最 佳包络矩形。因此，对于多边形，先求出其所有的凸点，然后依次连接所有凸顶 点形成一个新的凸多边形，最后依次以每条边为基准对该凸多边形进行旋转，使 该基准边平行于某坐标轴，此时多边形的包络矩形为可能的最佳包络矩形。依次 以新凸多边形的每条边为基准，逐一进行计算，比较即可求出多边形的最佳包络 矩形( 面积最小者) “。 以上是单个多边形的最小包络矩，对于多个多边形的最小包络矩可以采用先 将多边形进行边界移动组合，然后再求最小包络矩形，从而将多边形的排料转换 成矩形件排样问题。使用最小包络矩代替外形各异的多边形进行计算，在算法中 不必考虑多边形的具体形状，把复杂的多边形排料问题归结为大小不等的矩形优 化布局问题，显然简化了算法的复杂度，缩短了运行时间。 2 4 2 。5 位图排样法 在以往不转换为矩形件的多边形排样的讨论中，考虑最多的是单一类型多边 形、规则多边形和凸多边形几种情况，对于任意多边形，特别是包含孔洞的形状， 没有很好的方法。文献e 1 7 提出采用位图进行排样，直接采用位图排样，能满足 系统要求，但位图的数据量大，移动时需要比较的次数很多，速度很慢。他又提 出了采用条形图的方法，不用逐行逐列比较，可以迅速定位。在版面很复杂的情 况下，定位扫描次数很少 2 4 2 6 扫描排样法 对于不规则图形的排样尤其是内带孔洞等图形的排样较困难，如采用包络矩 形，则图形内的孔洞容易废料，如果采用扫描法，则可以很方便的区别已排和未 排区域。当进行排料时，每一个待排样的排列相当于在一块没有排任何图形的原 料上任意寻找合适的位置进行放置，不受其它图形的干扰，这种方法的优点是待 排图形肯定会排在一空区域，不存在与其它图形相交问题，而且也能充分利用图 形的孔洞区域。 东乍犬学硕l 。学位论文 第二章捧科技术发展简介 2 5 排样问题的研究趋势 1 、多种算法有效综合。对于n p c 类问题，一般可以设计好几种求解方法，这 些方法都能以一定概率找到最优解，但是不能保证对所有情况都能得到最优解。 各种方法相互协同，相互启发，能找到比任何单独一种方法更好的解。对于如何 综合各种算法以及哪些算法在哪一阶段综合至今是排样问题研究的一个重要方 向。 2 、多目标、多约束条件。有时长时间计算是值得的，因为经过长时间计算后 可以获得很高的材料利用率。但是不同的问题具有不同的情况，在实际应用中究 竟具体需要多长时间的等待可以获得较好的结果，算法设计者很难预料，一方面 是因为排样过程中可能遇到的实际情况是多种多样的；另一方面用户可以接受的 计算时间也各不相同。在这种情况下，最好的解决方法就是将决定权交给用户， 由用户根据实际情况来决定在何时放弃耗时过长的计算过程”1 。现在的研究一般 是结合某一具体行业、具体的应用、结合具体的生产工艺即具体的约束条件来进 行，然后再将研究中的理论推广到其它领域。 3 、从多个角度对排样算法进行研究。在应用领域，对排样问题的研究是寻找 合理时间内的最优解法，目前一些软件在设计时，将这个合理时间交给用户来选 择：在算法分析方面，对算法的时间复杂性、空间复杂性进行分析；对算法性能 表现方面，进行一般情况下、最坏情况下解的质量以及适用的问题类型进行研究； 针对不同的问题特点，如问题的规模( 零件的数量) 、零件的长宽比、零件的差异 变化比，测试和分析算法的性能“” 本章小结 本章主要介绍了排料技术的整体研究情况，叙述了排料问题的主要应用领域、 排料问题的难点与求解的难度，详细介绍了排料问题的各种算法( 如遗传算法、 神经网络、模拟退火、分支定界算法和降维启发式线性规划算法) 和排料问题的 各种解决方案( 如基于最左最下( b o t t o ml e f t ) 原则的b l 策略、剩余矩形匹配法 ( l r f ) 、多边形边界移动法、最小矩形包络法、位图排样法和扫描捧样法) ，最后 指出了排料问题的研究趋势是将多种优化方法相互协同，进行优势互补，在具体 东牛大学硕上学位论文第二帝捧科技术发展简介 问题的研究中，结合具体的生产工艺要求，采用各种约束条件使排料问题更具有 专业性，以及从多角度对排料进行研究。 1 4 东牛人学坝e 学位论立 第三节噩装谗技术的研究 第三章服装排料技术的研究 排料也称排板、套料，是指一个产品排料图的绘制过程，是在满足成衣外观 特点、裁片规恪质量及生产工艺等要求的前提下，将服装各规格的所有纸样在指 定的面料幅宽内进行合理的排列，排出用料所需的最短长度，使面料利用率达到 最高，降低产品成本，同时给铺料、裁剪等工序提供可行的依据“。如何摆放服 装纸样最合理，最能节省面料，是排料要解决的问题，本章主要研究服装排料技 术。 服装排料具有排料范畴的共性也具有服装行业的特殊性。服装是多个衣片的 整合，排料时不能仅仅为了考虑用料率而多排或少排某一纸样，同一件服装的所 有纸样尽可能在一个排料图上完成( 防止出现色差及漏排等情况) ；对于要考虑对 条对格、图案、纹路及倒顺毛影响的服装，排料要求较高，不能随便进行纸样的 旋转、镜像等，因而这类排料的用料率也较低；服装行业的排料可以兼顾纸样组 合和所需面料的长度，再确定最优方案，这是因为一批服装往往有多种号型，排 料是在放码后再进行，可以是同种号型的纸样单排，也可以是多种号型的纸样混 排，寻求最优的排料方案，确定可以接受的所需面料的长度。 服装排料属于异形件排料，因为服装纸样的形状有多种，加上放码后纸样的 形状更是复杂，但由于人体的对称性，服装纸样间的形状又不是完全不同，如常 规服装一般都是左右对称的。毛皮类排料比常规服装的纸样排料复杂，这是因为， 毛皮不像常规面料比较规则，毛皮类面料形状很不规则，而且在毛皮内部存有孔 洞。所以毛皮类的排料比常规面料的排料更为复杂。文献 1 8 中创新地采用离散 化处理方式，同时引进边界约束，使排样过程与毛皮和纸样的几何信息无关，使 用基于顺序的启发式底左布局将纸样顺次布置到毛皮上，纸样的最优布置顺序和 角度依靠随机优化算法来实现。毛皮类的裁剪也与常规面料不同，毛皮的裁剪只 能采用单裁，而不能采用批量裁剪。 3 1 服装车i p ：i - 的原理 东华人学钡上学位论文务三章服数排料技术的研究 3 1 1 服装排料的要求 服装排料问题就是寻找纸样最优布局的优化问题，即将用同匹面料制作的服 装纸样合理地放在面料中，使面料利用率最高，并满足下列要求。 1 、所有纸样在面料之内： 2 、所有纸样互不重叠( 有时为节省面料可以允许纸样的某些部位有一定量的 重叠) ： 3 、纸样排列时，考虑服装工艺的要求( 如纸样的丝绺方向、倒顺毛、对条对 格以及花纹图案的完整性等) 。 3 1 2 服装排料的基本原则 1 、经济性原则，在裁剪时节约用科是排料的基本目的之一。 2 、工艺性原则，无论如何省料，都不能违背排料的工艺性要求。纸样的丝绺 必须严格按照设计要求进行排列，不可为省料丽随意更改。 3 、设计性原则，在实际生产中，有时板型稍作修改，可以节省一些面料，而 不会对设计效果造成影响，这时排料技术人员就需要及时向上级技术部门反映， 以综合考虑造型效果、成本和利润等问题。 3 1 3 影晌服装排料的主要因素 服装排料属于二维不规则任意多边形的排料，影响服装排料的主要因素有： 1 、纸样的几何特征，一般而言，纸样的几何特征比较规则的服装排料比纸样 不规则的服装排料的面料利用率高。 2 、原料的特征，一般来说，采用条格面科及具有定位图案面料制作的服装的 排料利用率不太高，这类服装在裁剪时也具有特殊性，往往是先进行毛裁，然后 再修片。毛皮类面料由于毛皮带有孔洞的不规则性且每块毛皮大小不一，所以其 排料也比较复杂，毛皮面料裁剪时一般是进行单裁，而不是批量裁剪。因此，这 类服装面料的利用率与常规服装面料相比而言较低。 3 、加工工艺的要求，如面料的幅宽、色差，纸样的丝绺方向等。服装企业所 定购的面料并不是在同一织机上完成的，即使是同一织机也不能保证经纬向张力 1 6 东华大学硕士学位论文第三章服装排 技术韵研究 的一致性，因此面料的幅宽存在一定的误差，铺料时需将宽幅和窄幅分开铺料， 这样即可以降低废片率同时也提高了面料的利用率。 3 2 传统人工排料技术的研究n 9 1 删 1 、先长后短，一般情况下，面料的宽度是一定的，企业寻求最高的排料用料 率，最直观的就是使面料的长度最短，由于长的纸样比短的纸样对面料长度的影 响大，所以排料时一股采用先排长纸样后排短纸样。 2 、先大后小，大纸样之间容易产生一些空隙，先排大纸样后排小纸样，就可 以利用大纸样间的空隙放置小纸样，即使部分小片无法在空隙中排下，需直接排， 小纸样也没有大纸样对用料率的影响大。 3 、先主后次，如先排暴露在外面的袋面、领面等，然后再排次要的裁片。外 面的袋面、领面若无特殊的设计要求，一般都是整块不允许拼接，而挂面、领里、 腰头、袋布等部件的纸样通常可采用拼接的方法以节省面料。 4 、对称排料，组成服装的衣片基本上是对称的，如上装的左右前片、后片、 袖片。在制作样板时，这些对称衣片通常只绘出一片纸样。排料时，要特别注意 将样板正、反各排一次，确保裁出的衣片为一左一右对称，并注意避免漏排。 5 、精密排料，纸样与纸样之间要靠近划样，在不影响规格和裁割质量的情况 下，有时可以两片合用一条划线( 一般指直线部位) ，一刀裁开，这样可以省划和 省割一条划线，提高排料和裁割面料的效率。 6 、紧密套排，排料时将大中小号进行混排，并根据纸样的形状，采取直对直、 斜对斜，凸对凹，尽量减少纸样间的空隙，做到排歹i j 紧密。在各个裁片形状相吻 合的情况下，利用一切可以利用的面料，如果两纸样不能紧密套排，不可避免的 出现缝隙时，将具有凹状缺口的纸样摆在一起，使缺口增大以排放其它纸样。对 外观没有影响的衣片可以采用拼接的技术( 如领里片) ，以最大程度的节省面料， 降低服装成本。 3 3 服装c a d 排料的研究 表华大学硕士学位论文第三章服装捧科技术的研究 3 3 】计算