（计算机应用技术专业论文）基于临界多边形的二维排样算法研究.pdf

上海交通大学博1 ：学但论文 摘要 im _iii l =鼍 基于临界多边形的二维排样算法研究 摘要 本文研究二维排样问题。二维排样是一个平面布局优化问题，目的是在平面板材 上尽可能多的布置不同形状的零件，并满足以下约束条件：( 1 ) 零件布置于板材内部； ( 2 ) 各零件之间互不重叠；( 3 ) 满足一定的工艺要求。它的优化目标是：寻求一个零件 布局方案，使得浪费的板材面积为最小，亦即材料利用率为最大。排样问题对船舶、 服装、模具等行业有重要意义。针对目前二维排样问题中的难点和关键问题，本文进 行了广泛而深入的理论研究，包括二维排样问题中的几何计算、矩形排样、二维不规 则形状排样以及智能优化算法在排样问题中的应用等，提出了一系列解决方案和算法。 研究成果和创新点可概括如下： ( 1 ) 临界多边形n f p 算法研究：提出了一种新的基于轨迹线计算的临界多边形快速求 解算法，解决了n f p 求解的准确性问题，并在n f p 的计算速度上有了较大的提 高( o ( 小船) ) 。 n f p 算法是二维排样问题中的基础性几何计算问题，也是目前限制二维排样 算法发展的瓶颈问题。由于长期以来缺乏准确、稳定、快速的n f p 算法，使得零 件定位优化、多角度旋转、板材带孔洞等问题得虾到很好的解决，而n f p 算法的 计算速度也限制了排样问题往智能优化方面发展。基于n f p 算法的重要性和基础 性，本文提出了一种新的临界多边形快速求解算法，力求比较彻底地解决n f p 计 算问题。该算法将多边形滑动碰撞问题转化为顶点和边之间的轨迹线计算，从而 可引入几何图形索引算法降低时间复杂度，并可统一处理边界空腔和内部靠接 n f p 等特殊情况。算法的基本步骤是：( 1 ) 求解多边形顶点相对于另一多边形的轨 迹线；( 2 ) 求解轨迹线集合所形成的逆时针外包多边形和内部顺时针环，得到的多 边形即为临界多边形。算法采用了基于网格的线段索引方法来加快线段之间的求 交计算，进一步提高了n f p 求解的计算速度。理论分析和实验结果表明新的n f p 算法可以同时处理内靠接n f p 计算、边界空腔、板材孔洞等特殊情况，其计算速 度较优化移动碰撞法有较大提高( 算例2 - 1 2 - 2 ) 。 ( 2 ) 二维矩形排样算法研究：分析了矩形零件的现有定位策略，提出了一个基于临界 多边形的矩形件定位算法，算法具有较高的定位点搜索能力和较低的时间复杂度 。即2 ) 。 研究了矩形排样问题的零件定位算法及启发式排样算法。研究了已有的矩形 排样问题的数学模型，针对矩形排样中的两个关键问题零件定位策略和启发 式排样算法进行了分析和改进：在零件的定位策略上提出了基于临界多边形n f p 第l 贞 卜海交通大学博十学位论文摘要 的矩形件定位策略，在求解得到n f p 的基础上，将零件定位于n f p 的最低最左 点。与已有定位算法相比，n f p 定位算法的时间复杂度较低( o ( 刀) ) ，并且可对定位 点进行全面搜索，有效减少了排样过程中形成的内部空腔面积浪费；在启发式求 解排样算法方面，提出了基于最佳适应度优先的启发式排样规则，综合考虑待排 零件定位后的材料利用率、面积以及最低y 坐标等评价指标，选择具有最佳适应 度的零件作为优先排样零件。此外，本文还将单板材n f p 定位算法推广到多板材 n f p 定位算法，得到了多板材矩形排样算法( 算例3 1 、3 - 2 ) 。 ( 3 ) 不规则形状排样算法研究：提出了基于重心n f p 的不规则形状零件定位算法和启 发式排样算法。通过选择多角度重心n f p 中的最低重心位置来确定零件的排样位 置，从而达到提高零件分布密度的目的。 在不规则形状零件的定位策略上，本文利用n f p 计算并通过零件的旋转，提 出了基于重心n f p 的不规则形状零件定位策略。利用零件重心作为n f p 的参考点 计算出重心n f p ，通过选择多角度重心n f p 中的最低重心位置来确定零件的排样 位置。在异形件的启发式排样算法上，针对异形件排样方案中容易出现孔洞的问 题，提出了顺序递归排样算法，当出现较大孔洞浪费时通过动态调整零件排样次 序来减少孔洞的形成，使排样利用率明显提高( 算例4 1 4 4 ) 。 ( 4 ) 智能排样算法研究：结合排样问题的具体特点，研究了模拟退火算法( s a ) 和遗传 算法( g a ) 等智能排样算法，使排样具有较强的全局优化能力，取得比启发式算法 更好的排样效果。 研究了s a 、g a 等智能优化算法在二维排样问题中的应用。使上述智能优化 算法也适用于本文提出的矩形件和不规则件的排样。在模拟退火算法方面：阐述 了模拟退火优化算法的基本原理、技术特点及算法过程，根据排样问题的特点设 计退火算法的实现过程及关键参数，如排样方案的编码及解码、领域函数、初温 的设定、降温速率设置等内容，最后运用退火排样算法进行了实例计算并和现有 排样算法的最好计算结果进行了对比( 算例5 1 5 2 ) 。在遗传算法方面：研究了个 体的编码和解码、适应度的计算、个体复制过程的设计、交叉变异过程的设计以 及交叉变异概率的设置等内容，最后进行了实例计算和对比( 算例5 - 3 5 ，5 ) 。实验 表明智能排样算法的计算时间较长，但是具有较强的全局优化能力，能够取得比 启发式算法更好的排样效果。 关键词：排样，临界多边形，启发式排样，模拟退火算法，遗传算法 第1 1 负 一卜海交通大学博十学位论文 a b s t r a c t r e s e a r c ho ft w od i m e n s i o n a ln e s t i n ga l g o r i t h m b a s e do nn of i tp o l y g o n a b s t r a c t r e s e a r c ho nt w od i m e n s i o n a l ( 2 d ) n e s t i n gp r o b l e m sw a sp r e s e n t e di nt h i st h e s i s 2 d n e s t i n gi sal ( i n do fp l a n a rl a y o u to p t i m i z a t i o np r o b l e mw i t ho b j e c to fa r r a n g i n gan u m b e ro f p i e c e si n s i d eag i v e np l a t e ，a n di nt h es a m et i m e ，f o l l o w i n gr e s t r i c t i o n sm u s tb es a t i s f i e d ：( 1 ) p i e c e ss h o u l db en e s t e di n s i d et h ep l a t e ；( 2 ) e a c hp i e c es h o u l dn o to v e r l a p 丽t l la n o t h e r ；( 3 ) c e r t a i nr e s t r i c t i o n so nm a n u f a c t u r es h o u l db ef u l f i l l e d 1 1 1 eo p t i m i z a t i o no b j e c to f2 d n e s t i n gp r o b l e mi st of i n da na r r a n g e m e n tf o rp i e c e s ，a n dm i n i m i z et h ew a s t e dm a t e r i a l ，i n o t h e rw o r d s ，t h em a t e r i a l u s a g er a t i os h o u l db em a x i m i z e d n e s t i n gp r o b l e mh a sa s i g n i f i c a n t i n f l u e n c eo nt h ei n d u s t r i e ss u c ha s s h i p b u i l d i n g ，c o s t u m em a k i n g ，a n d m o l d - m a n u f a c t u r e a c c o r d i n gt o t h e k e yp r o b l e m sa n dd i f f i c u l t i e s e x i s t e di nn e s t i n g p r o b l e m ，t h et h e s i sp r e s e n t e daf u n d a m e n t a lr e s e a r c h i n ga n dp r o p o s e dc o r r e s p o n d i n g a l g o r i t h m sa n dr e s o l u t i o n s t h em a i nr e s e a r c ho b j e c t so f2 dn e s t i n gp r o b l e mi n c l u d e g e o m e t r i cc a l c u l a t i o n , r e c t a n g u l a rn e s t i n g ，2 di r r e g u l a rn e s t i n ga n dt h ea p p l i c a t i o no f i n t e l l i g e n to p t i m i z a t i o no nn e s t i n gp r o b l e m d e t a i l e dr e s e a r c ha c h i e v e m e n t sa n dc r e a t i v e i d e a sa r el i s t e db e l o w ： ( 1 ) r e s e a r c ho nn of i tp o l y g o na l g o r i t h m ：t h eb a s i cg e o m e t r i cc a l c u l a t i o np r o b l e m s w e r ed e t a i l l ya n a l y s i s e da n dr e s e a r c h e d ，e s p e c i a l l yf o rt h ek e ya l g o r i t h mo fn e s t i n g p r o b l e m n of i tp o l y g o nf n f p ) a l g o r i t h m 。n f pa l g o r i t h mi st h en e c kf a c t o rf o rt h e d e v e l o p m e n to f2 dn e s t i n ga l g o r i t h m s ，d u et ot h el a c ko fp r e c i s e ，s t a b l ea n df a s tn f p a l g o r i t h mf o ral o n gt i m e ，s o m ep r o b l e m ss u c ha so p t i m i z a t i o no fp i e c e sl o c a t i o n ， p i e c e sr o t a t i o na n dh o l e si np l a t ea r es t i l ln o tp e r f e c t l yr e s o l v e d o nt h eo t h e rh a n d d e f e c t so fe x i s t i n gn f pa l g o r i t h m sh a v eb e e nt h em a i no b s t a c l ef o rt h ed e v e l o p m e n to f i m p l e m e n t a t i o no fi n t e l l i g e n ta l g o r i t h mo nn e s t i n gp r o b l e m d u et ot h ei m p o r t a n c ea n d f u n d a m e n t a lf u n c t i o no fn f p , t h i st h e s i sp r e s e n t e dan e wf a s tn f pa l g o r i t h m ，t h a t c o n v e m e dt h ep r o b l e mo fc o l l i s i o nb e t w e e nt w op o l y g o n st ot h ec a l c u l a t i o no ft r a c e1 i n e s e g m e n tf o rv e r t i c e sa n de d g e s a n di tc a l ld e a lw i t ht h es p e c i a lc o n d i t i o n ss u c ha si l i n e r c a v i t yh o l e sa n di n n e rc o n t a c t i n gn f p t h eb a s i cp r i n c i p l eo ft h en e wn f pa l g o r i t h mi s ： ( 1 ) c o m p u t i n gt h et r a c el i n es e g m e n tb e t w e e nv e r t i c e so fo n ep o l y g o na n de d g e so f a n o t h e rp o l y g o n ；( 2 ) f i n d i n go u tt h ee n c l o s u r ep o l y g o na n di n n e rc l o c k w i s el o o p s f o r m e db ya l lt r a c el i n es e g m e n t s ，t h e nt h er e s u l t e de n c l o s u r ep o l y g o na n di n n e rl o o p s a r et h ef i n a ln f p ，n l en e wn f pa l g o r i t h ma d o p t e do n eg r i d b a s e di n d e xa l g o r i t h mf o r l i n es e g m e n t st os p e e d u pt h ec o m p u t a t i o no ni n t e r a c t i o nb e t w e e nl i n es e g m e n t s e x p e r i m e n tr e s u l t ss h o wt h a tt h en e wn f pa l g o r i t h mc a np e r f e c t l yr e s o l v et h ep r o b l e m s s u c ha si n n e rn f p , c a v i t yo ne d g e s h o l e si n s i d ep l a t ea tt h es a r l l et i m e a tt h es a m e 第1 l i 负 一卜海交通大学博十学佗论文 a b s t r a c t t i m ei t sc a l c u l a t i o ns p e e di su pt oh u n d r e d st i m e sf a s t e rt h a ne x i s t i n gn f p a l g o r i t h m s i na d d i t i o n ，2 dn e s t i n gr e l a t e d g e o m e t r i ca l g o r i t h m s ，s u c ha sp o l y g o nb o o l e a n o p e r a t i o n sw i t ht o l e r a n c ea n dd e t e r m i n a t i o no np o l y g o n sw i s e ，a r ea l s oa n a l y z e da n d e n h a n c e di nt h i st h e s i s ( 2 ) r e s e a r c ho n2 dr e c t a n g u l a rn e s t i n ga l g o r i t h m ：m a i n l yi n c l u d et h ep i e c ep l a c e m e n t a l g o r i t h ma n dh e u r i s t i cn e s t i n ga l g o r i t h m f i r s t l yt h em a t h e m a t i cm o d e lo fr e c t a n g u l a r n e s t i n gp r o b l e mw a sa n a l y z e d ，a n dt h e nt h et w ok e yt e c h n o l o g yo fr e c t a n g u l a rn e s t i n g p r o b l e m p i e c ep l a c e m e n tp o l i c ya n dh e u r i s t i ca l g o r i t h mw e r er e s e a r c h e d p r i n c i p l e a n dt e c h n i c a lc h a r a c t e ro fe x i s t i n gp l a c e m e n ta l g o r i t h mw e r ea n a l y z e d ，a n dn f p b a s e d r e c t a n g u l a rp l a c e m e n tp o l i c yw a sp r o p o s e d b a s e do nt h ea c h i e v e dn f p , t h ep i e c ew a s p l a c e do nt h el e f ta n db o t t o mp o i n to fn f p c o m p a r e dw i t ho t h e rp l a c e m e n tp o l i c y , t h e t i m ec o m p l e x i t yo fn f pb a s e dp l a c e m e n ta l g o r i t h mi sl o w ( o c 7 v ) ) ，a n di tc a ng l o b a l l y s e a r c ht h ef e a s i b l ep l a c e m e n tp o i n t s ，h e n c ei t e f f e c t i v e l yr e d u c e dt h em a t e r i a lw a s t e c a u s e db yi n n e rc a v i t y , t h e r e f o r et h em a t e d a lu s a g er a t i oi s i n c r e a s e d s e c o n d l yo nt h e h e u r i s t i ca l g o r i t h mf o rn e s t i n gp r o b l e m ，t h i st h e s i sp r o p o s e dah e u r i s t i cn e s t i n g a l g o r i t h mb a s e do nf i t n e s se v a l u a t i n g ，i nt h i sh e u r i s t i ca l g o r i t h m ，m a t e r i a lu s a g er a t i o ， a r e ac h a n g i n ga n dl o w e s tyc o o r d i n a t e sw e r ei n t e g r a t e dt oe v a l u a t et h ef i t n e s sw h i c hb e u s e da sah e u r i s t i cr u l e ，a n db a s e do nt h i sh e u r i s t i cr u l e ，t h ep i e c e sw a sn e s t e di no r d e r w h i l ep i e c ew i t hh i g h e rf i t n e s sw a sn e s t e df i r s t o nt h eo t h e rh a n d ，t h i st h e s i sp r o p o s e d am u l t i 。p l a t e sn e s t i n ga l g o r i t h m ，i ta d o p t e dar e v i s e dn f p p l a c e m e n ta l g o r i t h mb a s e d o ns i n g l ep l a t en f pa l g o r i t h m ，a n da c h i e v e da ni d e a lr e s u l t n l ee x p e r i m e n tr e s u l t s s h o wt h a tt h en f pb a s e dr e c t a n g u l a rp l a c e m e n ta l g o r i t h mc a n o b v i o u s l yi n c r e a s et h e n e s t i n gq u a l i t yw h i l ei t st i m ec o m p l e x i t yi sl o w ( n e s t i n gq u a l i t yi n c r e a s eb ya b o u t2 0 i nd a t a s e t3 1a n d3 2 ) ( 3 ) r e s e a r c ho ni r r e g u l a rn e s t i n ga l g o r i t h m ：p i e c ep l a c e m e n ta l g o r i t h ma n dh e u r i s t i c a l g o r i t h mi ni r r e g u l a rs h a p e dn e s t i n gp r o b l e mw e r er e s e a r c h e d d u et ot h ei r r e g u l a ri n s h a p eo fp i e c e sa n dp l a t e ，s p e c i f i cp l a c e m e n tp o l i c ya n dh e u r i s t i ca l g o r i t h ms h o u l db e r e s e a r c h e d f i r s t l yi nt h ep l a c e m e n tp o l i c yf o ri r r e g u l a rs h a p e dp i e c e s ，t h i st h e s i su s i n g an f pa n dm u l t i - r o t a t i o nh y b r i dm e t h o d ，a n dp r o p o s e dan e wp i e c ep l a c e m e n tp o l i c y w h i c hb a s e do nl o w e s tc e n t e ro fg r a v i t yr u l e w i t l lg r a v i t yc e n t e ro fp i e c ea st h e r e f e r e n c ep o i n t ，t h eg r a v i t yc e n t e rn f pc a nb ec a l c u l a t e d ；s e c o n d l yf r o ma l lt h eg r a v i t y c e n t e rn f p sw h i c hc a u s e db yd i f f e r e n tr o t a t i o n ，t h el o w e s tg r a v i t yc e n t e rc a nb ef e n d s e c o n d l yo nt h eh e u r i s t i ca l g o r i t h mf o ri r r e g u l a rn e s t i n g ，i no r d e rt or e d u c et h ew a s t e c a u s e db yh o l e s ，t h i st h e s i sp r o p o s e da no r d e r - b a s e dr e c u r s i v en e s t i n ga l g o r i t h m ，i nt h e p r o c e d u r eo fr e c u r s i v en e s t i n ga l g o r i t h m ，t h en e s t i n go r d e ro fp i e c e sw a sa d j u s t e dw h e n l a r g eh o l e sw a sd e t e c t e d f i n a l l ye x p e r i m e n t so nt h eb e n c h m a r kd a t a s e tw a sp r e s e n t e d t o c o m p a r et h en e wa l g o r i t h ma n de x i s t i n go n e s ，t h ee x p e r i m e n tr e s u l t ss h o w s i g n i f i c a n ti m p r o v e m e n ti na l g o r i t h m sp r o p o s e db yt h i st h e s i s ( d a t a s e t4 1 4 4 ) ( 4 ) r e s e a r c ho n i n t e l l i g e n tn e s t i n ga l g o r i t h m ：g e n e t i ca l g o r i t h ma n da n n e a l i n g 第1 v 页 卜海交通火学博i 学位论文 a b s t r a c t m _i _ 一 i 鼍量曼曼曼葛 a l g o r i t h mi m p l e m e n t a t i o ni nn e s t i n gp r o b l e mw e r er e s e a r c h e d a d o p t e di n t e l l i g e n t a l g o r i t h m sc a nw o r kf o rb o t hr e c t a n g u l a rn e s t i n gp r o b l e ma n di r r e g u l a rn e s t i n gp r o b l e m n e s t i n gp r o b l e mi s at y p i c a lc o m b i n a t i o no p t i m i z a t i o np r o b l e m ，s oi ti ss u i t a b l et o i n t r o d u c ei n t e l l i g e n ta l g o r i t h ms u c ha ss a ，g aa n dt ae t c i n t on e s t i n gp r o b l e m t h i s p a p e ra d o p t e dg a a n ds aa l g o r i t h mi nn e s t i n gp r o b l e m i nt h ea s p e c to fs a ：f i r s t l yt h e b a s i cp r i n c i p l e ，t e c h n i c a lc h a r a c t e r sa n dp r o c e d u r ew e r ed e s c r i b e d ，t h e na c c o r d i n gt o t h es p e c i a l t yo fn e s t i n ga l g o r i t h m ，t h ei m p l e m e n t a t i o na n dk e yp a r a m e t e r sw e r e d e s i g n e d ，s u c ha se n c o d ea n dd e c o d ef o rn e s t i n gp a a e m ，d e s i g nf o rd o m a i nf u n c t i o n a n di n i t i a lt e m p e r a t u r e ，d e s i g nf o rt e m p e r a t u r ed e c r e a s i n gr a t e ，a n de x p e r i m e n t so n b e n c h m a r kd a t a s e t sw e r ec o n d u c t e dt oc o m p a r et h en e wa l g o r i t h m s 、析t l lt h ee x i s t i n g b e s tk n o wn e s t i n ga l g o r i t h m s ( d a t a s e t5 1 - 5 2 ) i nt h ea s p e c to fg a ：i n d i v i d u a le n c o d e a n dd e c o d e ，f i t n e s sc a l c u l a t i o n ，t h es e l e c t i o no fi n d i v i d u a l s ，c r o s s o v e ra n dm u t a t i o n o p e r a t i o n sa n dt h ep r o b a b i l i t yf o rc r o s s o v e ra n dm u t a t i o nw e r er e s e a r c h e d a tt h ee n d ， c o m p a r i n ge x p e r i m e n t so nb e n c h m a r kd a t a s e t sw e r ec o n d u c t e d ( d a t a s e t5 - 3 - 5 - 5 ) t h e e x p e r i m e n t sr e s u l t ss h o w t h a tt h er u n t i m eo fi n t e l l i g e n ta l g o r i t h mi sl o n g e rt h a nt h a to f h e u r i s t i ca l g o r i t h m s ，b u ti n t e l l i g e n ta l g o r i t h m sa c h i e v e dm o r ee f f e c t i v en e s t i n gp a a e m t h a nh e u r i s t i ca l g o r i t h m s k e y w o r d s ：n e s t i n g ，n on i tn o l y g o n , h e u r i s t i cn e s t i n g ，g a ，s a 皇= 暑鼍皇皇i _ i 一一一一一= i 詈= 皇! 昌= = = ! = = = 詈! 皇詈! 暑! = 詈鼍皇= 皇= 皇= = 皇詈= ! 皇= 詈= = 第v贝 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：年月日 上海交通大学上海父逋大字 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“4 ) 学位论文作者署名：指导教师署名： 日期：年月 日日期：年 月日 卜海交通人学博f 1 学何论文第一章绪论 第一章绪论 本章概述了课题的研究背景及研究意义，简述了国内外的研究现状和发展趋势， 最后给出了课题的主要研究内容、技术路线和本文的组织结构。 1 1 课题的研究背景及研究意义 1 1 1 排样问题的研究背景 排样问题( n e s t i n gp r o b l e m s ) 又称为下料问题( c u t t i n ga n ds t o c kp r o b l e m s ) 或填充问 题( p a c k i n gp r o b l e m s ) u 】，其目标是在材料切割过程中寻求一个较高的材料利用率。对 排样问题的研究始于2 0 世纪7 0 年代1 2 ，该问题的产生主要是现代加工制造业的发展 和市场经济竞争所产生的推动结果。随着经济的发展和对资源需求的增长，提高原材 料的利用率可有效节约资源和降低成本，同时自动化排样技术的应用也有利于提高生 产效率和降低人力成本，对企业的经济效益有着较大的影响。排样问题可定义如下： 定义l - l 在给定的几何空间e ( c o 为空间维数) 内，寻求多个空间子集( r l d ，r 2 a ，焉加砒 的优化布局，优化目标是使得排样后所有子集占用的空间最小，即总体空间利用率为最大。其约 束条件为排样后各子集位于给定空间以力内，r l a e e a ，且各子集互不相交，即足门局f 咖，f ， 歹 1 埘 ，同时满足一定的排样要求( 例如对冠的旋转角度等空间变换有一定的限制) 。 根据空间维数和具体应用来划分，排样问题可以划分为一维排样问题( 线性排样问 题) 、二维排样问题以及三维填充和装箱问题，其中涉及面比较广的主要是一维和二维 排样问题，亦即线性及平面材料的分割问题。在实际工程应用中，排样问题的核心目 标是在满足工艺条件的基础上，寻求一个合理的零件排样方案，并尽量提高材料的利 用率，以期达到节约材料和降低成本的目的。 上世纪7 0 8 0 年代以来由于计算机软硬件技术和智能计算技术没有得到充分发 展，自动排样技术尚处于理论研究的初始阶段，各行业主要采用手工方式进行排样， 随着计算机软硬件技术的发展，尤其是最近一、二十年以来，计算机硬件和计算智能 技术得到了长足进步，现代p c 机的运算能力已经可以支持智能算法的运行，从而为 智能算法在排样问题中的普遍应用创造了条件。 排样问题作为一个典型的优化问题，主要涉及到信息和计算机软件科学、运筹学、 数学、工程管理等学科。从2 0 世纪7 0 年代以来，世界上许多研究机构和研究人员都 投入了对优化排样问题的研究，不同研究人员从不同的学科角度，结合不同的应用需 求，在相关会议和期刊上发表了许多论文 3 1 ，提出了多种算法，并出现了相关的专著 和软件产品。 第1 页 j j 海交通人学博f j 学位论文第一帝绪论 排样问题广泛存在于许多行业当中，和实践应用密切相关，因此具有很高的研究 价值，然而从目前的研究进展来看，排样问题( 尤其是不规则形状排样问题) 尚处在基 础性的理论研究方面，例如几何计算、排样定位规则以及智能优化算法的应用等问题 等还需要进一步的探索，从总体发展现状来看，对排样问题的研究较为分散，尚未形 成系统化的理论和成熟的排样应用系统架构。 1 1 2 排样问题的应用领域 排样问题广泛存在于在现代经济社会的多个行业中，例如机械制造、印刷包装、 服装、皮革、玻璃、木材加工、建筑业、微电子等多种行业。表1 1 列举了排样问题 的主要应用范围： 表1 - 1 排样问题的主要应用领域 行业名称主要应川领域 钢板、卷材线切割，板金零件加：l 型材、管材切割，电机硅钢片 机械制造业 下料，造船、高压容器的板材下料 印刷包装业纸张裁剪和分割、版面布局、包装材料切割，报纸杂志的版面布局 服装制造业服装、鞋袜、装饰品、皮革等布料的切割下料，标牌放样 玻璃和木材加工玻璃、木材的切割，木制品制造中的木材排样 建筑业钢筋下料、门窗型材的裁剪、建筑板材和模板的切割和放样 微电子电路板的布局、p c b 板的切割放样 航空航天航天器舱室静态布局和动平衡布局 1 1 3 排样问题的分类 c o f f m a n e 4 】等将排样问题称为g e o m e t r i cc o m b i n a t o r y 问题，根据是否涉及到空间布 局问题划分为狭义排样问题和广义排料问题。根据空间划分，排样问题可分为一维排 样( 线材排样) 问题；二维排样( 平面排样) 或下料问题；三维排样( 三维装填) 问题。对于 应用最为广泛的二维排样问题，国内有学者专门对其分类进行了研究1 5 】，按照被排样 零件特点、排样区域、优化标准和工艺要求进行了划分。按照排样问题在空间特征上 的分类，以下分别对一维、二维、三维排样问题的定义进行阐述： 1 1 4 排样问题的定义 ( 1 ) 一维排样问题的定义 一维排样问题的定义为：给定一定数量和长度规格的管材，要求从管材中切割出 一定数量和种类的毛坯( 各类毛坯的长度不一，数量要求也不同) ，目标函数为消耗的 管材总长度为最少。在线性排样问题中，所给定的管材数量和长度已知，管材的长度 可以有多种，不同长度的管材，其数量也可以不同。排样的要求就是利用给定库存管 第2 页 j j 淘交通人学博i j 学位论文第一帝绪论 材，切割出一定数量要求的零件( 毛坯) ，毛坯的长度可以不同，同时不同毛坯长度对 应的毛坯数量也可以不同。一维排样问题的定义较为简单，但是能够反映出排样问题 的共同特征：既在给定空间内寻求一种优化组合方式，在满足空间和工艺等约束条件 的情况下，使零件占用的空间为最小，亦即浪费的空间为最小。 例如：给定数量不限的线材，线材长度均为l o ，需要从线材中切割出长度分别为 4 、3 、2 的3 种毛坯，各种毛坯的数量分别为1 0 、2 0 、3 0 ，要求消耗的总线材数量( 长 度) 为最少，如下图1 1 所示： 三! !詈詈吕 星 2 0 _ = 盖砌 口3 0 口匕- 3 鲨当“ 图1 - 1 线性型材的排样问题示意图 f i g 1 - 1l i n e a rn e s t i n gm a t e r i a lp r o b l e m 根据以上原材料的长度和各种毛坯的长度，对单根线材，我们可以得到多种排样 方案，下表1 2 列举了所有针对图1 1 的排样方式： 表1 - 2 对应于图1 1 的所有排样方式 排样方式 1234567 长度为4 的毛坯数量 2jj口口口口 长度为3 的毛坯数量 口j口，2 j口 长度为2 的毛坯数量 jj3口235 剩余废料长度 0l01o10 设排样方式f 切割的线材根数为而，则对于图1 1 中的排样问题，自动排样系统的 任务就是综合考虑表1 2 中的所有排样方式，在原料线材上切割出满足数量要求的毛 坯零件，目标函数为消耗的原料线材总根数( 亦即消耗的线材总长度) 为最小，同时满 足以下不等式方程组： f2 x l + l x 2 + l x 3 + 0 x 4 + 0 x 5 + 0 x 6 + 0 x 7 1 0 o + l x 2 + 0 x 3 + 3 x 4 + 2 x 5 + l x 6 + o x 7 2 0 【l z l + 1 砭+ 3 x 3 + o 毛+ 2 工5 + 3 + 5 x 7 3 0 其中不等式右边的1 0 ，2 0 ，3 0 表示3 种不同类型的毛坯数量需求分别不少于1 0 个，2 0 个，3 0 个。按照整数规划模型的求解