（机械设计及理论专业论文）纸盒件计算机辅助排样系统的研究与实现.pdf

浙江大学硕士学位论文 摘要 摘要 纸盒包装有着众多优点，被广泛应用在各个领域，且需求量越来越大，为了 能够更好地满足这些需要，同时快速响应新产品包装提出的新要求，势必要在纸 盒生产中采用c a d c a m 等相关技术，以提高纸盒生产的自动化水平。 纸盒计算机辅助排样系统c a n ( c o m p u t e ra i d e dn e s t i n g ) 是连接纸盒结构设 计系统和纸盒生产) j i - r 系统的桥梁。因为，排样系统的输入是纸盒结构设计所完 成的展开图，排样系统的输出是纸盒生产加工所要依据的排样图，所以，排样系 统在整个纸盒自动化生产中起着至关重要的作用，其性能的好坏直接关系整个系 统性能的好坏，提高其工作效率有利于保证整个系统运行的顺畅。 纸盒排样系统所起的承自口起后作用，决定了其排样计算必须考虑前后系统的 影响，以使得能够准确的获得纸盒展开图中的相关数据，同时排样的结构满足生 产加工的要求。所以，在进行开发系统时，首先是对纸盒件展丌图的结构特点和 加工工艺特点做了细致的分析，然后，再在此基础上设计相应的功能模块，实现 系统的输入输出以及多种实际生产情况下的排样计算。 本文阐述了纸盒排样系统开发中所涉及的方方面面，其中着重论述两个方 面，一方面是如何保证排样系统同纸盒结构设计系统数据交互的准确和顺畅。系 统采用通用的接口文件来存储数据，然后提出一种有效的针对纸盒件的数掘提取 以及预处理方法，其中包括分析纸盒件展开图的结构特点，各图元数据和生产加 工的关系以及重要程度，特别是在预处理过程中，通过线型分类、圆弧离散、交 点线打断和回溯搜索等系列操作得到纸盒件的精确有序外轮廓边界。 另一方面是纸盒生产系统如何影响排样系统的排样方案设计。针对不同的生 产加工情况，提出了不同的排样解决办法，当实际生产是单个纸盒件或者少量纸 盒件批量生产时，采用了一种基于结构体单元的规则布局排样方式，此种方式所 得的排样图案可以直接用于纸盒模切压痕工艺的加工，具有可连续快速生产的特 点，同时排样时考虑了纸板的尺寸和结构体的优化组合关系，从而保证了此方式 排样的利用率；当实际生产是多种排样件单件生产时，采用基于智能优化的不规 则布局排样，考虑到此方法所得的排样结果采用激光模切加工，排样布局相对自 由，所以，以排样的利用率作为主要的评价标准，同时为了在有效的时间内得到 较满意的解，采用改进所得的启发式排样算法，即两次启发排样，而这样得到的 解依然众多，所以再利用人工智能算法进行搜索，先是在大范围内搜索得到几个 较优解，再在这些解的邻域内搜索得到优解。系统已经投入实际生产应用。 关键词：纸盒，排样，预处理，结构体单元，人工智能 浙江大学硕士学位论文a b s t r a c t a b s t r a c t t h ep a c k a g i n go fp a p e r - b o xh a sm a n ya d v a n t a g e sa n di sw i d e l yu s e di nv a r i o u s d o m a i n s t om e e tt h ei n c r e a s i n gn e e da n dn e wr e q u i r e m e n to fn e wp r o d u c t s p a c k a g i n g , r e l e v a n tc a d c a mt e c h n o l o g yi su r g e n t l yn e e d e dt oi m p r o v et h e a u t o m a t i cm a n u f a c t u r eo f p a p e r - b o x e s p a p e r - b o x sc a n ( c o m p u t e ra i d e dn e s t i n g ) l i k e sab r i d g eb e t w e e np a p e r - b o x s d e s i g n i n gc a d a n dm a n u f a c t u r ec a m 1 1 峙i n p u to f n e s t i n gs y s t e mi st h ee x p a n d e d d r a w i n go ft h ep a p e 卜b o x ，a n dt h eo u t p u to fn e s t i n gs y s t e mi st h ea r r a n g e dp i c t u r e s t h a tt h ep a p e r - b o xm a n u f a c t u r eb a s e so n a sar e s u l t , n e s t i n gs y s t e mh a sac r u c i a l i n f l u e n c eo nt h ew h o l ea u t o m a t i cm a n u f a c t u r eo fp a p e r - b o x e s 1 1 璩p e r f o r m a n c eo f t h en e s t i n gs y s t e md i r e c t l yi n f l u e n c e st h e c a p a b i l i t yo ft h ew h o l es y s t e m , a n d i n c r e a s i n gw o r ke f f i c i e n ti sp r o p i t i o u st oe n s u r i n gt h es y s t e mw o r ks m o o t h l y f o rn e s t i n gs y s t e mh a sa b r i d g ef u n c t i o n , t h ec a l c u l a t i o no f t h en e s t i n gm u s tt a k e b o t hf o r m e ra n dt h el a l t e rs y s t e m i ci n f l u e n c ei u t oc o n s i d e r a t i o n t h e r e f o r e t oe x p l o i t n e s t i n gs y s t e m , w es h o u l df n - s tc a r e f u l l ya n a l y z et h ec h a r a c t e r i s t i c so fp a p e r - b o x s t r u c t u r ea n dm a n u f a c t u r ep r o c e s s ，a n dt h e no nt h eb a s i so ft h a tw ec a nd e s i g n r e l e v a n tf u n c t i o nm o d u l ea n dr e a l i z et h es y s t e m si n p u ta n d o u t p u ta n dc a l c u l a t i o ni n m a n yp r a c t i c a lo c c a s i o n s m a n ya s p e c t si n v o l v e di np a p e r - b o xn e s t i n ga r ew e l le x p l a i n e di nt h i sp a p e r , a n d a m o n gt h e mw ep a r t i c u l a r l yf o c u so nt w oa s p e c t s ：o n ei sh o wt oe u s u r et h ep r e c i s i o n a n ds m o o t ho f t h ed a t ai n t e r a e t i o nb e t w e e nt h en e s t i n gs y s t e ma n ds t r u c t u r ed e s i g n i n g s y s t e m f i r s t l ys t o r ed a t ai nu n i v e r s a li n t e r f a c ef i l e s ，a n dt h e np r o p o s ea ne f f e c f i v e m e t h o do fd a t aa c q u i s i t i o na n dp r e p r o c e s s ，i n c l u d i n ga n a l y z i n gt h es t r u c t u r eo f p a p e r - b o xe x p a n d e dd r a w i n ga n dt h er e l a t i o nb e t w e e nd r a w i n gd a t aa n dd a t ap r o c e s s ， e s p e c i a l l yi nt h ep r e p r o c e s s ，l i n e - t y p ec l a s s i f y i n ga n da r ed i s p e r s i n ga n di n t e r s e c t i o n b r e a k i n ga n db a c ks e a r c h i n gi sa l lu s e dt oo b t a i nt h ee x a c ti n i t i a lo u t l i n eb o u n d a r y t h eo t h e ri sh o wt h ep a p e r - b o xm a n u f a c t u r es y s t e mi n f l u e n c e st h ed e s i g n i n go f t h en e s t i n gs y s t e m v a r i o u sm e t h o d so fn e s t i n ga r eb r o u g h tf o r w a r di nr e s p o n s et o d i f f e r e n tp r o d u c i n gs i t u a t i o n w h e nt h e r ei so n l yas i n g l es h a p eo fp a p e r - b o x e st o p r o d u c e ，s y s t e ma p p l yal a y o u tb a s e do ns t r u c t u r ee l e m e n t , t h ea r r a n g i n gp a t t e r nf r o m w h i c hc a l lb es t r a i g h tu s e di n t op a p e r - b o xm o u l dc u t t i n g t l l i sm e t h o dc a nk e e p m a n u f a c t u r ec o n t i n u a l l ya n dc o n s i d e rt h er e l a t i o nb e t w c g l lp a p e rs i z ea n ds t r u c t u r ea s w e l l ，s oi tc a ne n h a n c et h eu t i l i z a t i o no f m a t e r i a l w h e nt h e r ea r em a n yv a r i e ds h a p e s o fp a p e r - b o x e st op r o d u c e ，s y s t e mu s e si n t e l l i g e n ti r r e g u l a rl a y o u t s i n c et h er e s u l to f t h i sm e t h o di st ou s ei a s e rc u t t i n g , t h ea r r a n g e m e n tc a nr e l a t i v e l yr a n d o m t h u s , t h e u t i l i z a t i o nr a t ei su s e da st h em a i ne v a l u a t i o ns t a n d a r d a tt h es a m et i m e i no r d e rt o g e tm o r es a t i s f a c t o r ya n s w e r , s y s t e mi m p r o v e st h ei l l u m i n a t i o nr a n g i n gm e t h o d n a t n 浙江大学硕士学位论文 a b g n u 岍 i sm e a nt ou s et w i - i l l u m i n a t i n gr a n g i n gm e t h o d b u tt h e 捌删e f sf r o mt h i sm e t h o da r e s t i l le x c e s s i v e , s oa f t e rt h a tw eu s ea r t i f i c i a li n t e l l i g e n c ea r i t h m e t i ct os e a r c h f i r s tw e g e ts e v e r a lr e l a t i v e l ys a t i s f a c t o r ya n s w e r s , a n dt h e nc h o o s et h eb e s ta n s w e rf r o m t h e m k e y w o r d s ：p a p e r - b o x ，n e s t i n g , p r e p r o c e s s , s t m e t u r e ，e l e m e n t , a r t i f i c i a l i n t e l l i g e n c e 学号2 0 4 0 8 1 3 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得逝望盘茔或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对奉研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：- y 勤签字同期：2 而毛年g 月占f 1 学位论文作者签名： 匆签字同期：2 而毛年6 月6 日 学位论文版权使用授权书 本学位论文作者完全了解逝鎏盘鲎有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权逝望盘鲎可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：莒易 导师签名：1 耙 签字f 1 期：2 以年占月6 日签宁日期：a 矾年占月毛开 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 浙扛大学硕士学位论文第一章绪论 第一章绪论 1 1 课题研究的背景与意义 随着现代工业的快速发展和人类环境保护意识的不断增强，纸盒包装的应用 越来越广泛。尤其是折叠纸盒包装，因其具有加工成本低、储运方便、适用于各 种印刷方式、便于销售和陈列、适于自动包装、回收利用性好、有利于环境保护 等诸多特点，需求量不断增加。同时为了方便顾客，要根据不同的目的和要求分 别设计出具有特殊功能结构，如窗口、悬挂、提手、易开封开启撕裂口等结构， 因此折叠纸盒结构日趋复杂。 所以为了适应现代工业发展，缩短产品包装周期，提高产品的市场竞争力， 满足自动化包装及出口商品包装对纸盒的要求，必须在包装印刷企业中普及和推 广纸盒c a d c a m 新工艺，要求纸盒结构设计生产软件除具有交互式图形软件 的基本图形操作功能外，还可满足纸盒设计的特殊要求，如设计纸盒结构展开图、 实现自动排样和纸盒立体图的任意旋转、显示纸盒的开闭过程，以及输出纸盒展 开图模切排样图等【1 、2 】。 其中所提到的自动排样功能是连接纸盒结构设计c a d 和生产加工c a m 的 桥梁，排样前读取的数据是纸盒结构设计的结果，也就是折叠纸盒的展开图，排 样后的结果是纸盒实际生产加工的起始，也就是模切排样图。因此，自动排样功 能的好坏直接影响整个系统的性能。如果排样图的纸板利用率高，那么对于材料 成本主要是纸板的纸盒生产企业来说，将大大减少废料，降低生产成本，提高产 品的竞争力，同样如果排样图能够很好的满足生产工艺，那么又将提高生产的效 率，使得产品开发和生产的周期缩短，有利于快速响应市场的需求推广新产品。 排样问题本身属于n p 问题中最难求解的问题一一n p 完全问题 ( 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 ) 3 ，这类问题的求解时间与问题的规模呈 指数关系增长，所以不能在多项式时间内求解。另外排样问题需要进行复杂图形 运算处理，考虑众多的几何特征和组合关系，难以建立统一、简单的数学优化模 型。在解决实际排样问题中，较通用的方法就是在时间和效率上权衡，借助计算 机快速计算的能力，结合生产加工的一些约束关系，建立能够满足实际需要的排 样计算模型。 折叠纸盒排样从维数上看属于二维排样问题，需要考虑纸盒在平面内的优化 组合关系；从折叠纸盒展开图形( 图1 1 ) 来看，图形较一般的冲压件复杂，属于 很不规则的排样件；从数量上看既有大批量生产，又有小数量加工，都要保证较 高的利用率；从生产方式上看，排样结果要满足模切制版连续加工的特点，如果 浙江大学硕+ 学位论文第一章绪论 是采用特种加工，排样结果也要结合其工艺特点；在系统输入输出方面，要能够 和其它纸盒设计加工系统建立良好的数据交互。可见，折叠纸盒排样问题，在二 维排样问题中具有很好的代表性，研究和解决好此类问题对于解决平面排样问题 中其它实际闯题具有很好的借鉴意义，如冲压件排样、皮革布料排样、玻璃切割 等问题。 穹一 乜工一一一 二? 一 气 一一 7 0 = = 4 耄 哑 荔 图1 1 典型的纸盒及其展开图 项目的开发以校企合作的方式开展，从需求分析、项目开发和测试反馈，各 阶段都与合作企业积极沟通，使得科研成果能够很好地转化为实际生产力。 1 2 国内外技术的发展现状 1 2 1 纸盒c a d ，c a m 技术国内外发展 纸盒计算机辅助设计和加工软件c a d c a m 应具备的功能有：纸盒库 预先存放了常用的标准纸盒类型供用户选用；纸盒结构设计一需要支持基本图 形的生成与操作，如旋转、镜像、复制、倒角、线段分段和截短等；纸盒三维显 示功能一通过屏幕展示三维设计效果；数据交换一能输入和输出其它c a d 软件、通用图形软件能接受的文件格式；纸盒排版将多个包装盒拼到一个大 版上进行印刷和模切，以达到批量生产和节省纸板的目的；纸盒制作c a m w 驱动激光开模机、弯刀机、切割机等设备工作【4 】。 到目前为止，国外已推出了数百种包装纸盒c a d c a m 系统软件。如比利 时b a r c o n 公司的a d t o s c a d 和p a c k e d g e 系统；加拿大的e n g v i e w 系统；德 国l a s e r c o m b 公司的i m p a c tv 2 ；英国a g c a d 公司的k a s e m a k e ；以及荷 兰b c s i s y s t e r o s b v 公司的p a c k d e s i g n 等。国外的纸盒软件产品的优点在于功能 完备，专业性强，其与硬件设备的配合也较好，能部分或全部实现前述的专业功 能，但价格普遍昂贵。 近几年来，我国科研部门及高等院校先后开发了一些功能较好、实用性较好 2 一一一 浙江大学硕十学位论文 第一章绪论 的包装结构设计、包装造型方面的c a d 软件较为著名的有方正包装设计 f o u n d e rp a c k 系统国内第一个商品化的包装纸盒c a d 系统，包括纸盒结构 c a d 、纸盒屏幕3 d 打样、纸盒拼大版等功能；还有天津科技大学开发t u l i - s k h 折叠纸盒结构模板设计软件；西北轻工业学院开发的纸盒自动设计系统w c h 软件以及上海激光研究所开发的激光切割模板系统等。应该说国产纸盒包装软件 尚处于起步阶段，其市场化程度以及市场营销力度均无法与国外巨头相比。而就 目前来说，国内企业对纸盒c a d 软件的要求更趋向于小而专，更加强调实用， 对性价比的要求也越来越高。所以国产软件必定有其广阔的生存空问，其应用必 定有更大发展。也正是基于这一点，国内的学者一直开展相关的研究工作，有针 对性地牙发纸盒专用模块和软件。 文献 5 3 为提高折叠纸盒设计的效率和准确度，设计并实现了一个盒型c a d 系统提出了一个盒型数据描述格式p k s ，运用参数化设计和零件装配技术生成二 维纸盒结构图；同时根据二维数据自动生成包装盒的三维模型；文献【6 】给出了纸 盒组件设计的层次结构模型和实现组件设计的方法，并以盒形拼大版为例加以说 明；文献【刀提出了基于拼合法的折叠纸盒结构c a d 系统( f o l d i n gc a r t o n ) 的总体 方案，详细地介绍了拼合法的基本原理及其在纸盒结构设计中的具体应用；文献【8 】 以a u t o c a d 为平台。利用其二次开发语言o b j e c t a r x 并结合v c ，对常规包装纸 盒进行二维平面图参数化设计，建立了三维立体图参数化设计。 1 2 2 计算机辅助排样( o a n ) 技术国内外发展 前一节所讲到的纸盒排版模块，确切地说是计算机辅助排样技术在纸盒包装 工业中的应用，排样技术作为- f l 学科在很多领域都有应用。由于即使是矩形零 件在一张板材上排放的问题也是n p 完全问题，加上实际的限制条件，问题会更 加复杂，同时排样问题具有多样性特点，至今没有通用的标准方法来解决。也正 是由于排样问题应用的广泛性与其求解难度，吸引了众多学者进行研究，提出了 很多很有实效的算法和计算模型。针对系统开发研究的需要，这里主要探讨二维 排样的国内外研究历史和现状，其也一直是研究的重点，较多的文献对矩形件和 异形件排样提出算法，因为实际生产中，此类问题最多。 1 。2 2 1 国外排样技术的发展和研究现状 国外有关下料排样问题的研究起步比较早，6 0 年代初，g i l m o r e 和 g e m o r y 发表了四篇著名的文章【9 1 2 】，其中就提到了二维排样优化问题。在 1 9 8 8 年的e u r oi x t i m sx x v i i i 国际会议上，专门成立了下料问题兴趣小组 s i c u p ( s p e c i a li n t e r e s tg r o u po l lc u t t i n ga n dp a c k i n gp r o b l e m ) 。 在欧洲该小组为e s i c u p ( e u r os l c u p ) 并有专门的网站其地址为： 浙江大学硕七学位论文 第一章绪论 h t t p ：c t p c 2 2 i n e s c n p t e s i c u p ，近几年的e s i c u p 会议分别是：2 0 0 3 年6 月在土 耳其的伊斯坦布尔( i s t a n b u l ) ，2 0 0 4 年3 月在荷兰的威腾堡( 晰扎e n b e r g ) ，2 0 0 4 年7 月在南非的罗德斯( r h o d e s ) ，2 0 0 5 年4 月在英国的南安普敦( s o u t h a m p t o n ) ， 2 0 0 6 年3 月在葡萄牙的波尔图( p r o m ) 【1 3 】。从会议召开的时间上看，小组的交 流活动一直在开展，而且各次会议的自j 隔也不是很长，差不多一年不到的时间就 召开一次，可见整个小组的科研和交流比较的活跃；从会议的召开地点来看，小 组的交流面也比较广，不仅仅是局限于一个城市，一个地点，因此学习和研究该 小组的一些会议论文集可以大致把握了国外在此类问题的研究方向。 在矩形件排样方面会议论文中有：t a k a s h i 采用分支定界法算法解决矩形条 料排样和最优排样问题 1 4 1 ；e d u a r d a 提出基于图形的多级非切割方式的排样方 法 1 5 1 ；l e el s 等在文献b 6 中归纳了矩形排样几种典型的启发式方法，如最 低最左的b l 算法、下台阶算法、b l 填充算法、周长匹配算法、上下层算法、最 低水平线算法等，同时讨论遗传算法在矩形排样的应用；和以往的从纸板下端开 始排所不同的是文献 1 8 提出从纸板上角落( u p p e ra n g l ea l g o r i t h m ) 开始排 料。 在任意不规则件排样方面会议论文中有；文献 1 8 3 利用遗传算法求解激光 切割不规则排样图的路径优化问题；而在文献 1 9 则对遗传算法和模拟退火算法 在求解排样问题的性能做了比较；在文献 2 0 中采用多阶段的方法布局不规则排 样件，先是排放大的不规则件，然后再将小的排样件填充到大排样件的空隙中， 最后对位置进行调整，以得到更好的结果；另外有学者提出用网格布局的方式对 单一不规则排样件进行大批量排样，效果也不错 2 1 ；文献 2 2 描述了禁忌搜索 算法在矩形排样问题中的应用；在不规则图形的表达方面有学者采用了x m l 文件 来描述，以便于统一图形描述方法 2 3 】；在文献 2 4 中提出不规则排样图的邻 域搜索机制，便于得到更好的排样结果； 2 5 、2 6 、2 t 这三篇文献都是关于中 函数在排样问题中的应用，分别是该函数在二维简单排样图形中的应用，在二维 复杂图形中的应用以及在三维排样问题中的研究应用，其关键的一点就是要为不 同的图形构建中函数，使该函数能够表达图形间碰撞、靠接、相离等多种情况， 从而能够进行不规则排样件的排样。 除了s i c u p 外，国外的众多学者也在各自的领域内应用和推进排样技术的 发展。从整体上看，先设计一种启发式算法得到众多的排样解，再在这些解中寻 找较好的排样是一个研究的热点方向，由此涉及基本的启发式算法设计，搜索方 法的设计，编码的设计等等。其中编码设计有；如文献 2 s - 3 3 中都用到树型编码， 此编码用字符表示排样件问的关系，用数字代表不同的排样件，由此可以表达多 种排样结果：而文献 3 4 、3 5 用前后两个顺序链表来表示排样位置关系，首先用字 母表示不同的排样件，然后通过对比字母在两个顺序链表中的位置变化得到排样 4 浙江大学硕士学位论文 第一章绪论 件排样时的位置关系；文献 3 6 r 用一个顺序链表来表示排样结果，不同的数字 表示不同排样件，对与某个排样件数字，通过比较其邻近数字的大小关系，得到 排放时其上下左右是那些排样件，从而得到排样结果；上面讲到的树型编码、双 链表编码、单链表编码，其基本思想都是用数字或者是字母代表排样件，然后通 过其它字符或者前后数字字母，得到某排样件上下左右是那些排样件，从而确定 各排样件间的位置关系，相对与这三种包含位置关系的编码方式，就是文献 1 6 】 中所提到的b l 算法，其编码的结果是一个排放先后顺序链表，不包含位置关系， 具体的位置关系由先尽量向下排放，再尽量向左排放的启发规则所确定，与此相 类似的方法也很多，如下台阶、最低水平线、c b l 3 7 1 等等。所有的这些编码方 式，有一个共同的特点，就是和排样结果有一个一一对应的关系，变动其中的数 字字母或者是字符，就可得到新的排样方案，所以可得的排样解很多，因此借助 一些搜索算法来得到其中的好的排样编码值，常见的搜索机制有；遗传算法 1 7 、 1 8 、1 9 、3 2 、3 3 、3 7 1 其中包含一些对它的改进方法，如免疫遗传 3 3 ，或者是 加快它的计算速度，如分布式遗传 3 2 1 ，也有将它同其它搜索算法结合，如遗传 模拟退火【1 9 】；另外的优化搜索算法有，禁忌搜索【2 2 】，蚁群算法 3 7 1 等。 在国外，三维的排样也有相关学者在研究，i j 面提到的中函数在该邻域的应 用2 7 、4 3 1 ，其算法用例是基本三维图形，如长方体、球、正三棱锥等，首先建 立这些基本图形的中函数，再由这些基本图形去组成复杂的图形；文献1 3 8 1 其算 法用例是：考虑一组不规则的三维图形，如何在圆柱体内排放；在文献【3 9 】学者 研究集装箱的装箱问题，如何使空间有较高的利用率；文献【4 0 】研究球体在长方 体内的有效排向问题；如果在三维的基础上在考虑时间因素，则排样问题变成四 维，有学者【4 1 】就研究了集装箱在轮船上的有效排放问题，同时考虑时间；又如货 物的配送问题，要考虑装卸货物的方便，以及配送时的路径【4 2 】； 1 2 2 2 国内排样技术的发展和研究现状 国内排样技术的研究，开始于8 0 年代，一方面是工业经济的发展，需要运 用排样技术解决大量的实际排样问题，另一方面国家经济文化的对外开放，使 得外文的一些研究文献和资料进入国内，具有借鉴和参考价值。 在这里重点看一下，2 0 0 0 年后的一些排样研究文献，以了解当前国内排样 技术的研究现状以及重点解决的问题，先看矩形排样技术的研究：矩形件排样可 以分为两类，一类是同一矩形排样，即同一种矩形在板料上排放；另一类是矩形 套捧，即多种矩形在板料上排放。文献 4 5 - - 5 0 1 都是解决第一类问题，有采用 启发式算法【4 5 1 ，动态递归剪切算法【4 6 】，采用和改进a g r a w a l 提出的规范多级 排样方式 4 7 、4 8 1 ，动态规划算法【4 9 】，分枝定界算法 5 0 l 等；文献1 5 1 - 5 7 1 都是研 究第二类问题，这类问题是二维矩形排样问题中相对复杂的问题，研究的学者也 浙江大学硕士学位论文 第一章绪论 相对较多，同样有采用启发式算法 5 l ，5 4 、5 6 1 ，动态规划和启发式结合【5 2 】， 考虑矩形加工工艺的排放 5 3 1 ，考虑板材选择的排放 5 5 1 ，也有基于前面提到的 树型编码 5 7 1 ；另外，值得关注的是文献 5 8 6 4 1 都采用了人工智能加启发式的求解 方法，【5 8 、6 1 遗传模拟退火和最低水平线启发式算法结合，【5 9 遗传算法同剩 余矩形结合，而文献 6 0 1 是模拟退火算法加最小宽度填充，【6 2 1 遗传模拟退火和 填充算法结合求解大批量矩形排样； 6 3 、6 4 则将下台阶算法，b l 算法同遗传 模拟退火算法结合，这种方法和国外的一些研究方法很相似，也是这几年的一个 研究热点；同时也有学者用此方法研究矩形排样后的加工路径的优化问题【4 4 】。 再来看，国内学者在不规则排样件或者说是异形件上的研究工作 6 5 7 3 。不 规则排样值得关注的一点是不规则图形的表达问题。所以，以这点来适当的分类； 有学者用平行线化来表达不规则任意图形 6 5 、7 h ，文献 6 6 、7 0 l q a 采用网格化 来描述，也有采用直接包络矩形或者是组合后包络来表达图形 6 7 、6 9 、7 2 、7 3 1 ， 文献【6 7 】中研究采用位图方式在排样中的应用等等，同时异形件排样计算量较 大，可选的排样解较多，所以往往辅助遗传算法等搜索机f 1 l j 6 5 、6 6 、7 1 、7 3 1 ， 寻找较优的排样结果，采用分布式算法 6 5 1 ，加快计算。总地看，不规则排样问 题在国内的研究起步较晚，查中文万方数据库，2 0 0 0 年到2 0 0 5 ，此类文献在1 5 2 0 篇左右，相对矩形件排样研究要少很多，至于三维的排样研究则基本上还是 空白。 1 2 3 现状分析 分析国内外排样技术的研究现状，可以看出，在一些技术程度上国内的学者 和国外研究者的研究内容和方法还是相当的，可以说处于同一层次，但从研究者 的交流上来看，国内学者间的交流还远远不够，没有相关的会议，主要还是以查 阅其它学者的相关文献为主，同时，专业的研究人员还不是很多，仅有的专业研 究排样技术的几位学者，都只集中在研究少数几个排样方向，但排样的实际问题 相对较多，使得有些研究方向尚未开展，比如三维排样问题、排样和企业资源优 化问题。另外，不同的实际排样问题有着不同的排样约束，排样方法要考虑加工 工艺，目前较多是从理论上进行研究，专门系统的分类研究各种排样问题的约束 还不多。就拿本系统而言，从排样技术的角度来查纸盒排样相应的文献，可查的 中文纸盒排样相关文章只有一篇 7 4 1 ，采用忽略所有圆弧和内部线段包络矩形进 行排样，如果从纸盒c a d c a m 系统开发的角度来查相关文章，则在此类系统 的开发中可以得到有关纸盒排版功能的描述【5 、6 】，但就对比排样技术研究来说， 则又不够深入和具体。所以有必要，将现有相对成熟的排样技术研究理论，应用 到纸盒排样问题中去，同时，分析纸盒设计和加工的特点，结合约束，改进方法， 进行针对性的纸盒排样方案设计，开发相应的系统，这样将有利于推进国内纸盒 6 浙江大学硕士学位论文第一章绪论 c 脒a m 技术的发展，满足企业实际生产的需要。 1 3 工作目标、主要研究内容及技术路线 1 3 1 工作目标 工作的最终目标是开发完成可投入实际生产应用的纸盒件排样系统。此系统 要求有良好的数据接口，使其和其它纸盒c a d c a m 系统数据交互顺畅，包括 从纸盒结构设计结果中获取数据信息，排样结果输出能为加工系统所用；要求排 样方案适应多种情况的纸盒生产，比如一种纸盒批量生产，多种纸盒单件、批量 生产；要求排样的结果满足快速连续生产的要求，即和加工设备的工艺相结合， 如果是特种加工，也要考虑其工艺特点，具有加工可行性；要求排样的利用率较 高，需要考虑各种因素，尽量在满足生产加工的条件下提高利用率，综合考虑排 样纸盒件和纸板之间的关系；要求系统运行稳定，易于使用、维护和升级；要求 系统在有针对性的解决纸盒件排样问题的同时，具有一定的通用性，所采用的方 法和技术经适当改进后可以用于解决同一领域的其它生产实际问题；要求系统具 有保护自身产权的能力，即有些功能需要注册后才能使用；要求系统有相关的帮 助文档，以方便用户的使用。 1 3 2 主要研究内容和技术路线 基于以上的一些要求，主要的研究内容就是要逐步逐项的实现这些功能满足 要求，细化到具体的内容上主要有以下几点： 研究各种文件接口的形式，了解其数据的存放格式，以及如何对这些数据进 行处理。在具体系统实现上，采用d x f 文件存放纸盒结构设计信息，系统输入 模块完成对其数据的提取，同时设计合理的系统内部数据结构存放和管理数据， 然后根据排样计算的需要进行相应的预处理。 研究纸盒件展开图中那些图元信息是比较重要的，各自的功能是什么，应该 怎样对其进行归类。在具体系统实现上，主要根据纸盒生产加工时，各图元的作 用来分类，比如切割线、正折线、反折线等，其中切割线是比较重要的，因为切 割线基本上是外部的一些边界线，用它可以得到纸盒展开图的外轮廓有序边界， 方便排样计算时的判交，方便对纸盒图形进行处理，比如平行线化处理或者是位 图处理。而正反折线基本上都是在内部，主要在图形显示时用到，对排样计算的 影响不大所以，系统设计专门的图元分类模块，根据图元所在图层和线型来进 行分类。 研究纸盒生产加工的工艺特点，这些特点对纸盒设计和生产有什么影响，而 这些影响与进行排样计算有何关系，应当在排样中如何考虑这些因素。分析目前 浙江大学硕士学位论文 第一章绪论 纸盒加工的主要工艺模切压痕工艺，首先是根据排样图案，进行模切版制作， 然后进行排刀，再是切割。实际生产中要求能够连续快速的生产，所以在具体系 统实现上，采用一种基于结构体单元的规则布局排样，其通过相同的图形在纸板 上的扩展得到排样结果，因此只需要进行一次排刀就能切割完所有排样纸盒，满 足连续生产的要求。同时考虑结构体和板料尺寸的优化组合，以得到较高的利用 率。 研究纸盒件生产中所要遇到的各种情况或者是生产需求，在排样计算中怎样 来满足这些需求。实际生产中，除了快速连续批量生产外，还有的就是多种纸盒 件的单件生产。所以，在具体系统实现上，还设计了基于智能优化的不规则布局 排样，主要通过启发式算法和一定的搜索机制的结合，得到较高利用率的排样结 果，其中启发式算法是改进了适用于矩形件的启发式方法，提出两次启发的概念， 而在搜索机制上，则采用分阶段搜索，先是大范围搜索，再是邻域内搜索。 研究如何使排样计算快速。在具体系统实现上，当进行规则布局排样时，在 自动创建结构体时采用平行化平移计算，之后布局扩展时，采用步进方式，有效 地加快了计算速度，基本上是实时得到排样结果。当进行不规则布局时，则采用 矢量和位图结合的方式，矢量计算用于包络矩形的快速排样，位图边界采样简化 以及根据需要分区提取颜色等方法则用在进行外轮廓边界靠接时，目的都在于减 少计算量，加快计算速度。 研究如何有效的管理和维护系统中复杂的数据关系，怎样才能使开发工作有 序的进行，在保证开发速度的同时，保证系统运行的质量。 总体看，系统开发技术路线大致为：先是和系统应用的企业联系，进行针对 性地调研，分析纸盒排样技术具体需要那些功能，要达到怎样的目标；在此基础 上，查阅相关文献，了解国内外纸盒排样c a d c a m 系统的开发现状，了解国 内外对排样技术研究的进展，研究和掌握对纸盒件排样系统开发有利的技术，比 如c a d 开发技术、图形图像技术、计算机辅助排样技术、人工智能优化算法等 等，制定开发计划，分阶段完成研究和开发任务。 1 4 本文内容安排 系统开发和研究工作从第二章的纸盒c a n 系统总体设计和开发环境开始， 此章主要明确了系统的总体框架以及系统的各部分功能所要具体实现的目标、各 功能的必要性和重要性、开发过程中所会遇到的难点，解决的大概思路。并介绍 系统所用的开发环境及相关问题。 第三章主要是为排样计算作准备以及如何输出保存排样结果，针对性的分析 了纸盒排样件的结构特点，其加工的工艺特点，并据此提出了一系列保证最终有 8 浙江大学硕士学位论文第一章绪论 效提取纸盒件图元信息的操作，并对这些数据作相应的预处理，以方便后续的排 样计算。作为排样输入的对应，排样输出也在这章一起介绍，虽然相对排样输入 其功能实现过程要简单，但十分重要。 第四章是为了满足排样生产中相同纸盒件或者是几个纸盒件大批量排样时 所设计的一种排样方式，称为规则布局排样。提出了结构体单元的概念，统一了 以往单排，对排等概念，更便于理解和计算，其组成也十分的自由，最小可以是 一个排样件，最大可以是整个排样结果。其主要通过横纵扩展的方式在纸板上排 样，为了有效利用纸板，引入结构体和纸板的优化组合机制。 第五章是为了满足多种排样件单件生产的需要，所提出的一种排样方式，称 为不规则布局排样。先是通过改进一些适用于矩形件排样的启发式算法，使之满 足纸盒异形件的排样需要，得到一些可行性解，然后通过智能优化算法在这些可 行解中搜索优解。因为，此过程中包含众多的参数，方法也各有不同，所以对这 些方法的优劣进行了一定的比较，并通过实验对相关参数进行调整，以利于得到 较好的排样解。同时，也提出了一些加快排样计算的有效方法。 第六章是纸盒排样系统的实际应用 第七章是总结和展望。 9 浙江大学硕士学位论文 第二章纸盒c a n 系统总体设计与开发环境 第二章纸盒c a n 系统总体设计与开发环境 2 1 引言 纸盒排样c a n 系统总的设计出发点，就在于如何很好的满足实际生产的需 要，通过分析纸盒结构件的特点，加工工艺的特点，设计相应的模块。首先足解 决系统和其它纸盒相关c a d c a m 系统的数据交互，即输入输出模块；再是如 何有效提取、处理、和保存纸盒件图元信息和数据，即图形预处理模块；然后设 计合理的排样方案，满足大批量连续生产和小批量定制的需要，要求排样结果合 理同时利用率高，即排样计算模块；在排样计算和输入输出的时候，要对有关信 息进行统计，以提供给使用者作为参考，便于调整相关参数，选择新的排样方案， 即信息统计模块；在排样计算时，对很多相关参数要进行设定，即参数设置模块； 另外还有数据管理模块、图形显示模块以及人机交互模块等。作为整个系统，要 有效的整合各个模块，使得系统有效的工作，保证其稳定，易修改和维护，所以 开发的过程中，应用软件工程的相关知识，在保证质量的同时，也使得开发过程 合理有序。选用功能强大的v c + + 开发环境。 2 2 系统总体框架设计 图2 1 系统总体框架 2 3 系统主要功能分析 图2 2 系统数据处理流程图，表明系统处理相关数据的大致过程，其最基本 地体现纸盒c a n 所要解决的问题，即将待排样的纸盒件在一定的纸板上按照一 定的排样方案进行布置，最后将结果输出。本小节将按照此处理流程分析系统主 l o 浙江大学硕十学位论文 第二章纸盒c a n 系统总体设计与开发环境 要模块所要完成的功能，将会遇到的难点以及解决方案 柞样计算； 设定搭边值等相关 参数，进行排样计 算得到排样图 形，输出综台信息 图2 2 系统数据处理流程 2 3 _ 1 排样模式选择 在排样模式选择上，系统提供三种可选方案：相同件大批量排样；几种排样 件小批量排样；多种排样件单件排样。 图2 3 排样模式 i l 圄圄 浙