（机械制造及其自动化专业论文）皮革智能排样系统的开发.pdf

摘要 皮革工业的持续发展依赖于皮革加工生产技术不断改善。自动化、智能化和节约化是皮 革工业发展的重要目标本论文结合浙江省科技计划重大项目( 2 0 0 3 c 1 1 0 2 3 ) ，在现有排样 算法的基础上，将启发式优化算法和皮革排样的实际情况相结合，提出了启发式边长匹配算 法，并以该算法为基础，成功开发了皮革智能捧样系统。最后，对排样算例进行了分析比较， 并对该系统的性能作出了客观的评价。 第一章，分析了皮革智能排样系统的背景和意义，并介绍了皮革智能排样问题的基本概 念和相关问题，最后对国内外皮革智能排样技术的发展现状进行了细致的分析 第二章，对二维不规则皮革排样问题进行分析研究。皮革排样是属于带约束二维排样型、 不规则样片不规则母板型的组合，是属于排样问题中最难的一种。在分析皮革排样问题的难 点的基础上，总结出了常用皮革排样的策略，并结合皮革排样的特性，提出了基于启发式边 长匹配的构想。 第二章，先对传统的矩形包络法进行了分析，并指出其中的不足，即会造成大鼍的原料 浪费。因此，提出了用g r a h a m ss c a n 算法来求解凸包，该方法避免了传统矩形包络法的缺 点，一方面有利于样片外轮廓的表达，另一方面有利于后续排样的进行。 第四章。根据皮革排样的特点，将启发式算法原理和与边长匹配策略相结合，提出了一 种基于启发式边长匹配算法的皮革排样模型。该模型涉及到样片轮廓的离散、样片的分组排 序、初始样片置中、样片的融合、匹配边对的寻优、试探性放置、碰撞检测和终止原则。文 中详尽了介绍了该模型的具体过程和它们的数学描述。 第五章，前面的章节为皮革排样提供了数学模型和排样算法，本章则利用这些模型和算 法，利用计算机编程的方法，来实现皮革排样的具体功能。本章介绍了系统的六个功能模块、 系统的流程图、程序的数据结构，以及它们具体功能的实现过程 第六章，指出智能排样系统是属于计算机数控裁剪系统的子系统。它在整个计算机数控 裁剪系统中发挥重要的作用。本章具体介绍该子系统的作用，然后对系统排样算例进行了细 致的分析最后对该系统的运行情况进行性能评价。 第七章，对本论文的研究工作和研究成果进行了总结，展望了未来的研究工作。 关键词：皮革排样；边长匹配：碰撞检测；凸包；启发式算法；不规则样片 a b s t r a c t t h es u s t a i n a b l ed e v e l o p m e n to fl e a t h e ri n d u s t r yv i t a l l yd e p e n d so nt h ec o n t i n u o u s i m p r o v e m e n to fp r o c e s s i n gt e c h n o l o g y a u t o m a t i z a t i o n i n t e l l i g e n t i z i n ga n de c o n o m i z i n ga mt h e m o s ti m p o r t a n tg o a l so ft h el e a t h e ri n d u s t r y s u p p o s e db yt h et e c h n o l o g yp l - 1 0 9 r a mo fz h e j i a n g p r o v i n c e ，t h i sp a p e ra n a l y z e st h ee x i s t i n ga d v a n c e dn e s t i n gt e c h n o l o g y , a n dc o m e su pw i t ht h e a l g o r i t h mo f l l e u r i s t i ce d g e m a t c h i n ga ni n t e l l i g e n tn e s t i n gs y s t e mh a sb e e nd e s i g n e db a s i n go n t h i sa l g o r i t h m ，a n dt h en e s t i n gr e s u h sa r ed i s p l a y e da n dc o m p a r e d ，f i n a l l y , t h ef u n c t i o no ft h e i n t e l l i g e n tn c s t i n gs y s t e mi sa s s e s s e d c h a p t e r1 ，a n a l y z e st h eb a c k g r o u n da n ds i g n i f i c a n c eo f t h ei n t e l l i g e n tn e s t i n gs y s t e m ，a n d i n t r o d u c e st h eb a s i cc o n c e p t i o na n dr e l e v a n tp r o b l e m sf i n a l l y , t h em o d e m n e s t i n gt e c h n o l o g i e so f h o m ea n da b r o a da r ca n a l y z e d c h a p t e r2 ，c l a s s i f i e st h en e s t i n gp r o b l e mi nd i f f e r e n ta s p e c t sa n dp o i n t so u t t h a tt h el e a t h e r n e s t i n gp r o b l e mi so n eo f t h em o s td i f f i c u l tt y p e s t h es p e c i a ld i f f i c u l t yo f t h el e a t h e rn e s t i n gh a s b e e na n a l y z e d b a s i n go nt h ec o n v e n t i o n a ls t r a t e g i e s ，ac o n c e p t i o no f h e u r i s t i ce d g e m a t c h i n gi s p r o p o s e d ， c h a p t e r3 ，a n a l y z e st h et r a d i t i o n a lr e c m n g l e e n v e l o p em e t h o d ，p o i n t so u ti nd e f i c i e n c y , w h i c hw i l lr e s u l ti np l e n l yo fw a s t e st h e r e f o r e ，t h eg r a h a m ss c a na l g o r i t h mi sp r o p o s e dt o s o l v et h i st r o u b l e t h ec o n v e xh u l ly i e l d e db yt h i sm e t h o di sc o n v e n i e n tf o rt h ee x p r e s s i o no f p a r t sc o n t o u ra n dt h ef o l l o w i n gn e s t i n go p e r a t i o n c h a p t e r4 ，a n a l y z e st h ef e a t u r e sa n dp u t sf o r w a r d st h en e s t i n gm o d e lb a s e do i lt h ea l g o d t h m o f h e u r i s t i ce d g e - m a t c h i n g , w h i c hc o n t a i n st h ep r o c e s s i o n so f c o n t o u r _ c l i s e r e t i z a t i o n ，t h em e r g i n g o ft h ep a r t s ，o p t i m i z a t i o no ft h em a t c h i n ge d g e s ，h e u r i s t i co p e r a t i o n ，c o l l i s i o nt e s t i n g , a n dt h e p r i n c i p l eo f t e m d r m t i o n t h ec o u c r e t ep r o c e s sa n dt h e i rm a t h e m a t i c a ld e s c r i p t i o n sa r ei n t r o d u c e d c h a p t e r5 ，t h ep r e v i o u sc h a p t e r sh a v ep r o v i d e dt h em a t h e m a t i c a lm o d e la n dn e s t i n ga l g o r i t h m w h i l et h i sc h a p t e rw i l lu s et h e mt or e a l i z et h et a n g i b l ef u n c t i o nb yp r o g r a m m i n gi nc o m p u t e r s i x m o d u l e s ，f l o wc h a r t d a t as t r u c t u r ea n dt h ep r o c e s sd e t a i l sa r ei n t r o d u c e d c h a p t e r6 ，p o i n t so u tt h a tt h ei n t e l l i g e n tn e s t i n gs y s t e md e s i g n e di nt h i sp a p e rb e l o n g st ot h e n u m e r i c a lc o n t r o ls y s t e ma n dt a k e sa ni m p o r t a n tp a r ti ni tl h cn e s t i n gr c s a l t sh a v eb e e nd i s p l a y e d a n dc o m p a r e d a i s ot h e c u t t i n gr e s u l t st h a ip r o c e s s e d b y t h ec o m p u l e r i cn u m e r i c a lc o n t r o l m a c h i n ea r es h o w nf i n a l l y , t h er e s u l t sa r ea s s e s s e d c h a p t e r7 t h es t t m yc o n t e n t sa n dc o n c l u s i o n so ft h ed i s s e r t a t i o na r es u m m a r i z e d ，a n dt h e f u n h e rr e s e a r c hw o r k sa r ef o r e c a s t e d k e y w o r d s ：l e a t h e rn e s t i n g ，e d g em a t c h i n g ，c o l l i s i o nd e t e c t i o n ，c o n v o xh u l l ，h e u r i s t i ca l g o r i t h m i r r e g u l a rp a r t 学号2 0 4 0 8 0 4 2 独创性声明 本人声明所呈交的学位论文是本人在导师梅德庆副教授指导下进行的研 究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得浙江大 生或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：旃守苏彩：l 签字日期：工n6 年夕月二日 学位论文版权使用授权书 本学位论文作者完全了解逝江盘堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅。本人授权逝鎏盘堂可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后适用本授权书。 学位论文作者签名：t 泰钕试 导师签名 签字日期：- 叼0 年7 月善n 学位论文作者毕业后去向： l - 作单位 通讯地址 殇i 址 签1 期：孙彩年7 月毋日 电话 第一章绪论 第一章绪论 1 1 皮革智能排样系统开发的背景和意义 中国是皮革制品生产大国、消费大国和出口大国，皮革制品加工业是皮革工 业的一部分，素有投资少、见效快等特点，是我国轻工业的支柱产业之一1 1 1 。近 几年来，国内外皮革工业发展高潮迭起，市场竞争日益激烈，为了使皮革工业在 国内外保持领先地位，占领市场份额，则必须以皮革制品作为市场竞争依托，大 力发展皮荸制品加工业，对内既能繁荣市场，满足人民生活需求，提高人民生活 水平，又能积累建设资金；同时，皮革制品加工业与对外贸易有着密切关系，可 扩大出口，为国家创汇。因此，皮革制品工业在满足人们的需求，参与国际竞争， 起着十分重要的作用。 近些年来，世界皮革工业的发展重心已转向亚洲，中国已成为世界皮革大国。 从世界皮车工业的整个发展历程及其总的发展趋势来看，2 1 世纪中国皮革工业 面临的主要挑战足皮革工业自身发展过程中所面临的劳动成本的提高、皮草原料 的匮乏、新型材料的竞争及科技含量的增加等问题。这些因素不仅阻碍着中国皮 革工业的可持续发展，而且直接威胁着中国皮革工业的生存i l l 。 我国的皮革业生产技术与发达国家相比，还处于比较低级的水平，高科技含 量远远不够【2 1 。现在皮革制品生产过程是典型的劳动密集型的加工业，明显与先 进技术的要求不符，与智能化、自动化的加工技术的推广应用存在着很大的差距， 其主要的加工方法是采用人工和机械半自动相结合，其生产过程为：人工配色、 人工标注瑕疵、纹理的手工分类、手工排样、裁剪、分类包装、缝纫、组装成品。 如图1 1 所示，这样的生产过程表现为：人工劳力付出巨大，消耗的时间很长， 效率极其低下。同时也可以看出，在皮革的自动分类自动排样、数控裁剪技术 方面的应用还几乎是窄自。 图1 - 1 目前皮革制品制造过程i 序 另外，自动数控裁剪设备也只有极个别的大犁氽妙拥有一两台引，且利用率 第一章绪论 也较低，而且部是国外进口的。我国尚无自主研发生产的皮革智能裁剪机。这样， 致使进口产品的价格在进入中国市场之后大幅提升。 为了改变以上现状，以适应社会和市场的发展需求，提高皮革产品的科技含 量、产量及生产效率，需要结合目前国内的实际情况，开展皮革制品的准柔性生 产技术研发。采用计算机皮革检测方法与分类系统对成批皮革的颜色及纹理进行 在线检测、特征值提取及快速分类，从而逐步代替传统的靠人眼观察的手工操作。 因此，开发适合皮革复杂颜色与纹理特征，能与现有c a d 辅助设计系统相配合 的智能排样和自动裁剪控制软件，研制自动分类、排样和裁剪于一体的皮革制品 准柔性制造系统显得 乍常必要1 4 i 。 皮草智能排样系统是皮革智能裁剪系统的重要组成部分。智能排样是指在满 足质量要求的条件下，将样板尽可能合理地布置在原料皮革上，并且互不重叠。 目的是当按照所有排布的样板的轮廓进行裁剪时，可以获得最大的皮革利用率。 1 2 皮革智能排样的基本概念及相关问题 为了能够得到一个更加简单直观的摹本观念，对优化排样问题有一个基本 的认识，先来看一个简单的一维排样问题。先看下面这个问题：切割1 0 米的钢 条成3 米、4 米、5 米的小单元钢条，如图1 - 2 所示。 长1 0 米 切割损耗 e 三丑e 三三三三珂 、，、， 4 米5 米 圈l - 2 钢条切割问题 原料钢条及定制的小单元钢条构成了切割问题的基本数据，切刮问题的一方 面町以看成是用原科钢条来7 l 三产小单元钢条，使得原科的浪费最少：另一个方面 问题也町以看作足生产这些小单元钢条，最少需要使用多少数最的原料钢条。在 这个例f 中，若选3 米与4 米组合，那么切割损耗为3 米；若选4 米与5 米的组 合，则切割损耗为l 米。所以选取后肯电优。 2 第一章绪论 钢条切割属于比较简单的一维排样，因为问题只需要考虑长度方向上的优 化组合。但它同样也具备了排样问题的基本要素。 一般而言，排样问题具有下列几个共同特征： ( 1 ) 有两组基本数据，数据元素定义了一维或者多维空间下确定形体的几何 表达：大尺寸几何原材料对象和小尺寸几何样片列表。 ( 2 ) 排样过程实现小尺寸对象的几何组合在大尺寸对象上排放的布局图案。 残余的小块，例如，布局图案中无法容纳小尺寸对象的小块区域，通常称之为“切 割损耗”。 下面的图例1 2 通过典型的二维矩形排样图示直观地说明排样问题的基本构 成。 口口 ( a ) 人尺寸几何原材科对象 口r - - - 1 一f - - 7 口吕i - 7 口 口 二 一一il ( b ) 小尺寸几何样片对象 目团 ( c ) 排样方案图示 图l 3 排样j 题的摹本构成 智能优化摊样的目的在f 寻求某种优化的布局方式，使平面区域的面积利 用率较商。许多工业问题如钢板、玻璃、卷纸等的切割、服装剪截、货物装箱等 均属此类排料问题，足典犁的组合优化问题，具有很高的计算复杂性( n p 完全问 题) 。因此对规模较大的排料，小但f - l 排样不r 能做到真正的优化，即使采用 计算机也必须，f 发商效的算法才能实现利用率相对商的优化切割。 例如，在块力形暾材科母扳f ：排敏图l - 4 所永的样片图案，要求排放塔町 第章绪论 能多的样片图案，同时保证图案之间没有相互重叠。现在利用两种不同的排样算 法进行自动排样，分别为六边形近似法、矩形凸包法。这两种算法所排出来的布 局不同，但不能果断的评价哪一种算法更好，因为在不同的场合它们排样的优点 发挥的程度也是各异的。 喾0 囹 气弋j 飞八处 l l l l l 鲥飞八八处 l l lll 烈夕气5 飞八j 飞 l j 飞了n八祭 l l 图1 4 矩形凸包与六边形凸包的排样效果比较 1 3 皮革智能排样技术的发展现状分析 为解决智能排样的优化问题，使得智能优化算法能够在实际生产和实践中得 到运用和推广，国内外科研、工程技术人员提出了各种理论及算法，为智能化排 样提供了许多值得借鉴的优化方案，使得智能排样技术f j 趋成熟。 1 3 1 国外研究现状 国外有关f 料排样问题的研究起步比较早。k a n t o r o v i c h l 6 1 于1 9 3 9 年就提出 了一维下料i u j 题；2 0 世纪6 0 年代韧，g i l m o r e 等p 4 圳发表了4 篇著名的文章，提 出了一维下料方案和二维排样优化问题：7 0 年代至今，众多学者针对排样问题 的一个或几个方面提出算法和解决方案。由f 即使是矩形零件在一张板材上：的排 放问题也是n p 完全问题，加上实际的限制条件问题会更加复杂，因此排样问题 j 有多样性特点，至今没有通1 1 j 的 ，j 、准疗法柬解决。1 9 8 8j f t - ，在e u r o i x t i m s 第一章绪论 x x v i i i 国际会议上，专门成立了下料问题兴趣小组s i c u p ( s p e c i a li n t e r e s t g r o u p o nc u t t i n ga n dp a c k i n gp r o b l e m ) 。 下科问题的研究可以分为三大类：一维下科方案、二维排样和三维布局。 1 3 i 1 一维下料问题优化研究现状 从一维下抖问题的数学模型看，这是一个整数规划问题。常用的下料优化方 法是将整数变量进行松弛，视为线性规划，采用单纯形方法求解，然后对结果进 行圆整。但这样做并不能保证得到最优解，而且圆整之后会产生一种或几种零件 过量生产或不足量，需要对其进一步处理；或采用针对整数规划求解的分支定界 法与割平面求解，但这只在变量数目较少时适用。当零件的尺寸相对于原材料尺 寸较小且种类数量较多时，零件的组合搭配数目增大，列生成问题从组合角度看 是一个背包问题f l l i ，背包问题也是一个n p 完全问题。 从组合优化角度看，一维下料方案优化问题还可视作装箱问题。2 0 世纪 7 0 - - 8 0 年代研究人员提出多种近似算法，如首次适应降序算法( f i r s tf i t d e c r e a s i n g ，f f d ) 、下次适应降序算法( n e x tf i td e c r e a s i n g ，n f d ) 、最优适应降 序算法( b e s t f i t d e 2 c r e a s i n g ，b f d ) 等。近两年的研究倾向于采用多种方法复合 1 1 2 - 1 7 ，并将下料方案与加工的生产环管相联系，对一维下料问题进行求解。 1 3 1 2 二维下料问题 4 0 年来，二维排样问题一直是众多学者研究的热点，有大量的文献对矩形 件、异形件排样提出算法和改进。 矩形件排样既町以解决如玻璃切割这样的矩形件f 料问题，也可以通过提取 包络矩形用于异形件排样，很多学者针对剪切下料和正交下料提出了多种算法， 这两种方式的选择取决于切割设备、图案设计和成本冈索。 2 0 世纪9 0 年代以前，对矩形件排样的求解以各种近似方法为主i l 引。如基于 一维装箱的f f d 算法、b f d 算法；基f 最左最下原则的算法( b o t t o ml e f t ，b l ) ； 双向背包算法；相近图肜组合算法、动态规划算法等。文献1 1 9 2 0 1 对基于装箱的 各种算法的性能进行了分析。二维f 料问题可以归结为以零件排放状态为结点、 以废料增加为权值的、带权有向图的最短路径问题，属f 集覆盖问题，d a g l i i 引i 提出了一个基f 图案f 集的启发式算法，该算法适合于图形组合的图案较少的情 况。这些近似算法的特点足针对某类或某些排样问题的结果较好。 启发式方法因其易f 融合各种限制条件和具体目标，存实际生产排样中起着 莺要的作用。文献1 2 2 1 结合人工智能与运筹学方法，提出了馨f 知识求解知形件、 异形件排样问题的系统概念模型。文献【2 3 】采用来自肯经验的排样师的启发式规 则以及冲孔、剪床f 料等限制条件存储在知识库中的方式，指导模型生成图案组 合。文献1 2 4 2 6 1 从方便装卸、优化板科尺寸及减少订荦乍产周期等不同角度讨论 了排样问题。 第一蕈绪论 2 0 世纪9 0 年代后，随着智能优化算法( 如模拟退火算法、遗传算法、禁忌搜 索，神经网络等方法) 的日益成熟及其在t s p ( t r a v e l l i n g s a l e s m a n p r o b l e m 问题、 空间分配、任务调度等组合优化问题方面的成功应用，这些算法与排放算法相结 合被用于排样问题的求解。文献1 2 7 给出了模拟退火算法( s i m u l a t e d a n a e l i n g ， s a ) 、遗传算法( g e n e f i c a l g o r i t h m ，g a ) 、随机搜索法( r a n d o m s e a r c h ，r s ) 、进化 算法( n a i v e e v o l u t i o n ，n e ) 与不同排放算法结合，对不同问题实例的综合性能评 价的结果，有两点主要结论：( 1 ) 复合算法的结果优于单纯排样算法的结果，并 且排样算法效果越好，复合算法在同等条件下的效果也越好；( 2 ) 任何算法都有 效果不佳的问题实例，即对矩形件排样目前还没有完全有效的方法。 在对矩形件进行研究的同时，人们也对不规则零件的排样进行研究。对异形 件排样问题的求解方法可以分为三大类：( 1 ) 以矩形件排样为基础的算法；( 2 ) 侧重于图形运算、基于规则的方法；( 3 ) 采用智能优化算法。这三类方法分别侧 重于异形件排样问题的不同侧面进行求解，相互联系，共同反映了排样问题的几 何特性与组合特性。 一些学者以矩形件排样算法为基础进行异形件排样。通过对同种类型零件进 行组块，根据单个或组合的不规则零件的矩形包络面积，再用启发式算法对矩形 块进行排样i 嚣l 。文献1 2 9 1 采用三步方法对造船厂的零件排样进行了求解：第一步 是形状处理，通过去除圆角、倒角等局部小特征并用多边形对排样零件进行简化 近似处理，。然后对这些简化的图形进行归类为：板类、矩形支架、异形支架等； 第二步对分类的图形按照排样的经验进行分组，生成紧密排列的矩形块；第三步 采用矩形件的排样方法进行排样。文献 1 9 ，2 9 1 也提出了求解矩形件排样、异形 件排样的启发式算法。h e i s t e r m a n n 等1 3 0 1 讨论了皮革下料问题。 一些学者通过对零件的形状进行推理，采用启发式规则的方法研究异形件排 样，通常是将零件图形简化处理为多边形，如基f 临界多边形的方法，通过零件 问的图形运算、拼合推理的方法，基丁二争l 描碰撞的方法等。 文献 3 1 1 采用轮廓边的匹配方法，按照一组基f 零件面积、轮廓周长和复杂 性的性能参数进行排守，选择两个具有最高指标的零件，按照逆时针方向匹配每 条边之后，以形成的最小包络矩形确定排放位置。这个过程不断重复，直到所 有的零件排放完唪。由_ f 存在许多町匹配的边部需要进行大肇的测试，因此这种 算法计算最大，速度慢。通过固定一个零件不动，让另一个零件围绕着固定零件 的边移动一豳，形成临界多边形( n o tf i tp o l y g o n ，n f p ) ，文献 3 2 1 将n f p 用j 二异 形件排样。文献 3 3 1 探讨了r 临界多边形的乍成方法与位置状态评估。 y a z u 等1 3 4 嗡甚f 舰则的方法用r 服装友片排样。h e n r y 等1 3 5 l 模拟入- f 工排 样的方法，基f 推理技术来选择和排放f 一个零件。由f 实酾：排样中完令吻合的 “犬牙交错”几乎小存在，所以判断最佳旺配边的难度很大。 6 第一章绪论 文献【3 6 】讨论了通过碰撞将图形“压实”的方法。文献 3 7 3 8 1 研究单一零件 在条料上排放；文献 3 9 】讨论了同一多边形在板材上的排放。文献 4 0 】将 l a g r a n g i a n 方法与改进的启发式规则相结合，研究了服装裁剪中大衣片的缝隙中 插入小衣片的问题。 2 0 世纪9 0 年代后，一些学者将智能优化算法用于异形件排样问题。文献【4 1 】 采用s a 算法通过减少能量函数来确定图形的排样。能量函数表明了图形之间的 重叠程度，即图形之间的重叠面积之和与零件图形间重心距离的加权和。尽管模 拟退火算法给出了令人满意的结果，但由于能量函数中的参数与待排放零件的形 状复杂程度相关，该方法需要的时间较长，而且有得到不可行解的可能。文献1 4 2 1 采用禁忌搜索方法来减少n p 完全问题的优化搜索空间。 1 3 1 3 三维布局问题 对三维布局问题的研究开始于2 0 世纪8 0 年代中期。三维布局的目标足使材 料利用率和重量利用率最高。实际排样时还应考虑如下问题：( 1 ) 箱体本身的承 重性；( 2 ) 箱体搬运的难易性；( 3 ) 最大载熏量；( 4 ) 稳定性；( 5 ) 某些货物之间 的隔离。找到满足这些条件的最优解或近似最优解是一项极具挑战性的工作。 文献 4 3 1 利用序列二次规划和广义简约梯度法对三维布局问题进行求解，但 其求解的质量过分依赖于初始位置的选择；文献【4 4 1 通过惩罚因子将布局约束优 化转化为目标函数惩罚项，然后用无约束优化方法来求解；文献【4 5 】针对多种尺 寸物体排放问题应用启发式方法求解；g e 晡n g m l 采用启发式过程对单一集装箱、 多种不同货箱问题进行求解；文献【4 7 1 采用遗传算法、图搜索方法进行了求解； 文献【4 8 1 采用几何模型减少搜索空间。 虽然人们对排样问题进行了大量的研究，但限于n p 完全问题的复杂性，从 理论上依然没有彻底的解决的方法，它依然是人们研究的热点问题之一。 l _ 3 2 国内研究现状 国内对于排样问题的研究始f2 0 世纪8 0 年代，主要集中在高等院校和研究 所。对冲裁件排样从2 0t 吐纪8 0 年代开始研究，以华中科技大学、上海交通大学 的工作最有代衷性，主要有人机交互法、边界加密方法和不相交判别法等 4 9 1 ， 借助人机交互方式进行图形的旋转和平移以达到优化排样的目的。围绕着冲裁件 自动排样，文献 4 9 - 5 1 1 采用将零件处理为多边形的方法或采用碰撞算法卣陵对零 件进行排样。文献1 5 2 1 对一维f 料问题进行求解。 对矩形件排样的研究始f2 0 世纪9 0 年代， 要采用启发式算法，动态规划、 整数规划方法，g a ，s a 算法进行求解。文献1 5 3 研究了单一尺寸矩形件的排布， 文献f 5 4 】对特定设备l - ：f ：l f l l ：样进行了分析。 近几年来，困内学告j f 始对肆彤件排样问题进行研究。从算法香， 要是采 第一章绪论 用一定规则将异形件处理为矩形，按矩形件排样方法进行排放；采用基于图形运 算的移动算法、碰撞算法，基于规则、样图的方法、神经网络方法、基于学习的 遗传算法等进行求解；文献1 5 5 采用模拟细胞长大自然生成布局结构的膨胀算法 求解矩形空闯中等圆的布局问题。 国内学者对于三维排样问题主要采用启发式算法及遗传算法进行求解。文献 【5 6 5 7 1 以八叉树为基础设计启发式算法；文献 5 8 】以相同尺寸的物体布局为研究 对象，将约束处理加入启发式规则中，提出关于约束底盘装载问题的启发式方法； 文献1 5 9 - 6 0 l 采用遗传算法对装箱问题进行求解。 众多学者在研究排样算法的同时也开发了一些排样软件，从早期的交互排样 到自动排样，排样系统也在随着排样算法研究的深入而发展。华中科技大学最早 开发了冲裁件排样系统；曹炬推出了一维优化、矩形件排样、异形件排样的优化 排样系统软伊嘲；滕弘飞等对航天器舱布局方案设计f 6 l l ，查建中等5 8 对集装箱 装运问题进行研究和开发。 与国外相比，国内关于排样问题的研究无论是在深度上和广度上都有差距， 好在很多学者已经意识到该问题的研究价值，目前排样问题已成为国内学者研究 的一个热点。 1 4 本文的主要工作 本文在现有排样算法的基础上，将启发式优化算法和皮孳排样的实际情况相 结合，提出了启发式边长匹配算法，并以该算法为基础，成功开发了皮革智能排 样系统。最后，对排样算例进行了分析比较，并给出了智能排样系统在计算机数 控系统中的割切效果。详细工作如下： 第一章，论述了皮摹智能排样系统开发的背景和意义，并对智能排样技术的 国内外发展情况进行了详细论述和分析。 第二章，在排样分类的基础七，指出皮革样片足属f 二维不规则多约束剪切 排样问题，其中不规则包含了样片形状的不规则和母板形状的不规则，多约 束包含瑕疵约束、纹理约束和质肇分区约束等，属于排样问题中最难的u 】题。 具体分析皮革排样的难点，并对常用排样策略进行了分析，提出了基f 启发 式边长匹配算法。 第三章，基fg r a h a l n ss c a n 算法，对排样轮廓进行凸包求解。这部分内容 是为启发式边长匹配算法中的样片提供具体的样片几何表达。那么，后续的 启发式边长匹配锋法就叮以根据此算法计算出的凸包束进行边k 匹配的工 作。 第四嚣，构建基f 启发式边长匹配算法的皮革智能排样模型。这搴属f 论文 第一章绪论 的核心工作，它实现了皮荸智能排样系统的启发式边长匹配算法的具体设 计，建立了智能排样算法的数学模型。其中涉及排样算法的关键技术如分组 排序、样片融合、匹配边寻优和碰撞检测等。 第五章，介绍了皮革智能排样系统的软件实现。前面章节的论述只是提出排 样模型的方案和构想，是属于数学描述的范畴，而第五章则为这些数学描述 进行具体的编程实现，使这些方案能在计算机中得到具体的实现。 第六章，为皮荸智能排样系统的应用研究。首先阐述了智能皮革排样系统在 整个皮革裁剪系统中所处的位置和所发挥的作用；然后详细展示了系统的工 作流程和排样的结果，并且展示了根据排样轨迹输出文件进行工业实际切割 的效果：在算例分析的基础对系统性能进行了评价。 第七章对本文的研究内容进行了总结，并对排样系统的今后发展进行了展 望。 9 第二章二维不规则皮革捧样口】题的研究 第二章二维不规则皮革排样问题的研究 2 1 排样问题的分类 2 1 1 按维数分类 2 1 1 1 一维捧样问题 一维排样问题，又称线材排样问题1 7 4 1 ，是指在排样时只需要考虑一个方向的 尺寸。例如，将较长的型材、管材、棒材等，分割成各种较短的毛坯。一维排样 问题的典型应用领域：门窗、金属结构、金属制品、普通机械、专用设备、交通 运输设备、电器机械等制造行业。这些行业所属企业在制造过程中，需要将线材 分割成较短的毛坯，用于生产产品。 2 1 1 2 一维半排样问题 一维半排样问题，又称卷材排样问题1 7 4 1 ，是指被分割的材料宽度较小，长 度很大，排样时可以将长度看作无限长。生产中利用卷材形式提供的材料有布匹、 纸张、人造皮革、塑料、金属网、金属薄板等。 一维半排样问题的典型应用领域：服装、人造皮革制品、纸制品、塑料制品、 电机等制造行业。当金属薄板的厚度在o 5 m m 以下时，经常以卷材的形式供应， 例如生产电机铁心用的硅钢卷材，生产空调器时采用的镀锌钢板等。在分割过程 中，通常先沿着卷材的长度方向，将其分割成很长的条带，然后再将条带分割成 较小的毛坯。 2 1 1 3 二维排样问题 二维排样问题，又称板材排样问题i 川，是指将板材分割成各种形状的毛坯。 这些毛坯可以足矩形、圆形、扇形等规则形状，也町以足不规则形状。二维排样 问题的典型应用领域：木材制品业、家具制造业、金属制品业、普通机械制造业、 专用设备制造业、交通运输设备制造业、电气机械制造业等行业。 2 1 1 4 三维排样问题 三维排样问题，又称宅间装箱问题1 7 4 l ，足指在有限空间中合理排放零件， 此时材料和毛坯为蕾体形状。三维排样问题的典掣应用领域：木材加 业( 将圆木 分割成尺寸较小的方木) 、卡车或集装箱装货、仓库中货物堆放、制造业中的产 品内部构件南局设计等。 除一维、一维半、二维、二i 维排样问题外，若考虑到排样零件的质肇等因 素，则排样的维数还将进一步增加，不过生产中般只涉及前面四种类型。 o 第二牵二维不规则皮革捧样问题的研究 2 1 2 按规则度分类 2 1 2 1 规则样片捧样问题 不规则形样片是指可以用很少的数学参数就可以确定其形状的样片，如矩 形，圆、椭圆。而在实际工业生产中，用得最多的是矩形件的排样，所以，讨论 矩形件排样的文献也就相对较多1 5 1 。 规则形样片的排样算法比较简单，当然这也是相对于不规则样片的排样而 言。因为规则形样片排样的算法是不规则样片排样算法的基础，许多不规则样片 的排样通过特殊的处理之后就可以转化为规则形样片的排样。由于规则样片的数 学参数相对较少，所以，在使用同样的算法处理的时候，计算机所承受的计算量 也必将较少。 在待排样片中，如果这些样片是单一样片，即每个样片的形状都是相同的， 那么就可以用简单的循环来处理它们，而不用对它们中的每个样片挨个分析并且 定位。 而对于矩形件排样而占，又可以根据样片切割轨迹是否平行于母扳的边而 分为正交切割排样和非正交切割排样，如图2 1 为非正交切割排样。而正交切割 又可以分为一刀切问题和非一刀切问题。 一刀切问题，也可称直线贯通问题是矩形物体布局中较常见的一个问题1 7 ”； 它在扳材下誊4 行业应用十分广泛。所谓“一刀切”问题是指在布局模式中，在矩 形板材上切割的每一刀都平行于矩形板材的一组平行边，端点从矩形板材的另一 组平行边的一条延伸到另一条，将矩形板材分为两部分。简单地说，一刀切约束 条件下的每一刀都会把当前i f 在剪切的板材一刀两段。 如图2 2 为一刀切模式，它可以按图中所标记的切割顺序进行一刀切加 工，而图2 3 为非一刀切模式，它无法用如剪板机等有一刀切工艺要求的设备进 行加工，一般要使用比较昂贵的激光切割等方式。 图2 - l1 e 正变切割的排样问题 第一：章二维不规则皮革丰| 样问题的研究 图2 - 2 一刀切问题 图2 - 3 非一刀切问题 2 1 2 2 不规则样片捧样问题 不规则样片足指样片形状复杂、参数繁多、不能用简单的数学表达式来描 述。对这类样片的排样是比较复杂的，而且排样结果的随机性也较高，如图2 - 4 。 l f i2 - 4 小雠! l ! i i 扦片的持样 第：章二维不规则皮革捧样问题的研究 由于其形状不可预计，所以，想用一种算法来解决所有的不规则样片的排 样问题是没有意义的。 另外，不规则样片的排样结果相对于规则样片的排样来说，板料的利用率 会比较低。 2 1 3 按加工方式分类 2 1 3 i 剪切方式 剪切排样方式是针对剪切的加工特点而设计的排样方式1 7 4 l 。剪切加工常作 为冲裁加工的前处理，给冲裁加工提供条带料。它一般采用普通剪床或滚剪床来 进行加工。根据不同的板料情况，剪切排样方式呵细分为：卷材剪切排样、板材 剪切排样。这里不再详述。 2 1 3 2 冲裁方式 所谓冲裁，就是利用冲模在压力机上使扳料分离的一种冲压工艺i7 4 】。冲裁 排样方式是针对冲裁的加工特点而设计的排样方式。 冲裁加工中，工件轴线一般处于互相平行的位置，这一先决条件使这类排样 问题得到简化。在实际生产中，一般可以根据生产的实际需要( 如材料贵重程度、 加工难易要求等) 选择不同的冲裁排样方式。常见的冲裁排样方式有四种：普通 单排，普通双排，对头单排，对头双排。 ( 1 ) 普通单排 普通单排是将工件一个接一个地排布在一条直线上，如图2 5 所示，条带宽 和步距仅是图形与条料夹角的单值函数。因此，只需要将图形旋转、求出图形之 问的距离、平移即可进行普通单排的寻优计算。 、 i 芒 f 图2 - 5 普通单排 ( 2 ) 普通双排 普通双排足将两个相同工件合成为一组看成一个图形，且两【件与条料夹角 相同，然后按普通单排方式排样，如图2 - 6 所示。 第二章二维不规则皮革排样问题的研究 图2 - 6 普通双排 ( 3 ) 对头单排 对头单排与普通单排相似，也是将工件一个切一个地排布在一条直线上， 不同的是冲裁件是按头对头、尾对尾的方式排列的，如图2 7 所示。 2 8 。 、 一一 之 i l l 厂一i 厂j 图2 7 对头单排 ( 4 ) 对头双排 对头双排与普通双排相似，但冲裁件是按头对头、尾对尾的方式排列，如图 图2 - 8 对头取排 2 2 二维不规则皮革排样问题的难点分析 2 2 1 样片和母板的复杂性 在一维排样问题中，样片和母扳的形状对排样算法的选取、排样方式的确定 和最终排样结果部具有决定件的影响。二维排样| u j 题根据样片和母板的形状特 1 4 第二章二维不规则皮革捧样问题的研究 征，可以分为三大类：规则样片规则母板型、不规则样片规则母板型、不规则样 片不规则母板型。其中，皮革排样问题属于不规则样片不规则母板型，是三种排 样类型中最为复杂的一种。 规则样片规则母板是三种类型中最简单的一种，如图2 - 9 。它们所需的参数 简单，可以用简洁的数学表达式加以描述，在运算中的复杂度也大为降低。如图 2 - 9 所示为一个矩形样片矩形母板型的排样，只需要四个顶点坐标即可确定一个 样片的轮廓和母板的轮廓。在检测碰撞的时候，判断样片之间或样片和母板之间 是否重叠相交都比较简单。 图2 - 9 规则样片规则母板型 不规则样片规则母板是三种类型中复杂度介于中间的一种，如图2 1 0 。母板 所需的参数简单，可以用简洁的数学表达式加以描述：但样片的形状却极为复杂， 所需的参数繁多，有可能是凹形也有町能是凸形，这给确定排样算法带来极大的 困难，在运算中的复杂度也大为提高。如图2 1 0 所示为一个不规则多边形样片 和矩形母板型的排样，母板的轮廓只需要四个顶点坐标即可确定，但样片的轮廓 则需要许多顶点坐标来表示。由于样片的不规则，样片之间存在空隙是在所难免 的。 图2 一1 0 不规则样片娥则母板型 不规则样片不规则母板是三种类犁中最复杂的。种，如图2 8 。母板和样片 的形状部极为复杂，所需的参数繁多，小f i 样片的形状有町能足凹形也有町能是 凸形，而且母板的形状也宵町能是凹形也有町能足凸形，排样时不仅要考虑到样 片之问的匹配，而且还要考虑到样片与母扳之间的匹配问题，算法的复杂度也大 为增加。如图2 1 1 所示为一个不规则多边形样片和不规则多边形母扳型的排样， 样片的轮廓和母扳的轮廓鄙需要许多顶点啦标来衷乐。要得到利用率比较高的排 样方案显得更加困难。 第二章二雏不规则皮革捧样问题的研究 图2 1 1 不规则样片不规则母板型 2 2 2 肄样约束条件的复杂性 皮革排样除了受到其本身形状不规则度的影响之外，还受到其它约束条件的 影响。这些约束条件进一步增加了排样的难度，是选取排样策略时必须要考虑的 问题。约束条件的增加限