船体零件自动排料及优化问题的研究
|
摘要
排料问题,简单的说,是指在给定的区域内,排放几何形状的零件,使零件不重叠,并且尽可能的节省材料,是一个二维优化问题。排料问题在工业生产中应用十分广泛,如造船工业、汽车工业、服装生产、皮革加工、纸张及木材加工工业等都需要处理排料问题。
目前,我国的船舶工业处在一个飞速发展的黄金时期,然而,船体零件外形复杂,不规则,而且数量巨大,传统的手工排料方法,不仅需要耗费大量的人力,而且存在着耗时长,钢材利用率不高等缺点,严重制约了我国船舶工业的发展。因此,如何提高排料的效率以及钢材的利用率就显得尤为重要;同时,在提倡“科学发展观”,“建设节约型社会”的背景下,排料及优化问题也有着很强的现实意义。
本文首先比较了几种常用的解决优化问题的方法,如动态规划方法,模拟退火算法和遗传算法,分析了它们各自的特点;然后在日本的自动排料计算模块“FINEST”的基础上,开发了船体零件自动排料系统,分为数据输入、排料计算和结果输出三个模块,实现了零件信息和钢板信息的自动输入、零件的检索、输入文件的自动生成、自动排料计算、以及排料结果和排料图纸的输出等功能;随后应用该自动排料系统对一批船体零件进行排料,大大提高了排料的时间效率和钢板的利用率,验证了排料系统良好的应用性能;同时在计算机图形学的基础上,对自动排料的算法进行了一些研究,已经通过Visual C++实现了基于BL策略的船体零件自动排料,并通过遗传模拟退火算法对结果进行了优化,有一定的效果。
Nesting is about how to arrange geometric parts in specified areas. We should not overlap parts and save raw materials as much as possible. So we can make a conclusion that nesting is a two-dimensional optimization problem. Nesting is widely used in industrial areas, such as shipbuilding industry, automobile industry, fashion producing, leather processing, paper making and so on.
Now, China’s shipbuilding industry is in full flower. However, this industry is influenced by two key factors: traditional manual nesting which is labor and time consuming and inefficient, and numerous parts which are shaped complicated and irregularly. So in a society advocating developing in a scientific way and thrift, it is very crucial to promote the efficiency of nesting and the yield rate of raw steel materials.
Firstly the author compares several common nesting ways such as dynamic programming, simulated annealing algorithm and genetic algorithm, and analyses their characteristics. Then the author designs automatic nesting system on the basis of Japan’s computing modules. This system includes three modules: data entry, nesting computing and results outputting which achieves several functions, such as automatic entry of information about parts and steel plates, parts searching, automatic generation of files, nesting computing and outputting results and blueprints of nesting. Practical application has proven that this system can cut the nesting time and promote the yield rate of steel plates greatly. The author also studies the nesting algorithm on the basis of computer graphics, has implemented automatic nesting through Visual C++ and BL tactics, and optimized results through genetic annealing algorithm which turns out positive.
目前,我国的船舶工业处在一个飞速发展的黄金时期,然而,船体零件外形复杂,不规则,而且数量巨大,传统的手工排料方法,不仅需要耗费大量的人力,而且存在着耗时长,钢材利用率不高等缺点,严重制约了我国船舶工业的发展。因此,如何提高排料的效率以及钢材的利用率就显得尤为重要;同时,在提倡“科学发展观”,“建设节约型社会”的背景下,排料及优化问题也有着很强的现实意义。
本文首先比较了几种常用的解决优化问题的方法,如动态规划方法,模拟退火算法和遗传算法,分析了它们各自的特点;然后在日本的自动排料计算模块“FINEST”的基础上,开发了船体零件自动排料系统,分为数据输入、排料计算和结果输出三个模块,实现了零件信息和钢板信息的自动输入、零件的检索、输入文件的自动生成、自动排料计算、以及排料结果和排料图纸的输出等功能;随后应用该自动排料系统对一批船体零件进行排料,大大提高了排料的时间效率和钢板的利用率,验证了排料系统良好的应用性能;同时在计算机图形学的基础上,对自动排料的算法进行了一些研究,已经通过Visual C++实现了基于BL策略的船体零件自动排料,并通过遗传模拟退火算法对结果进行了优化,有一定的效果。
Nesting is about how to arrange geometric parts in specified areas. We should not overlap parts and save raw materials as much as possible. So we can make a conclusion that nesting is a two-dimensional optimization problem. Nesting is widely used in industrial areas, such as shipbuilding industry, automobile industry, fashion producing, leather processing, paper making and so on.
Now, China’s shipbuilding industry is in full flower. However, this industry is influenced by two key factors: traditional manual nesting which is labor and time consuming and inefficient, and numerous parts which are shaped complicated and irregularly. So in a society advocating developing in a scientific way and thrift, it is very crucial to promote the efficiency of nesting and the yield rate of raw steel materials.
Firstly the author compares several common nesting ways such as dynamic programming, simulated annealing algorithm and genetic algorithm, and analyses their characteristics. Then the author designs automatic nesting system on the basis of Japan’s computing modules. This system includes three modules: data entry, nesting computing and results outputting which achieves several functions, such as automatic entry of information about parts and steel plates, parts searching, automatic generation of files, nesting computing and outputting results and blueprints of nesting. Practical application has proven that this system can cut the nesting time and promote the yield rate of steel plates greatly. The author also studies the nesting algorithm on the basis of computer graphics, has implemented automatic nesting through Visual C++ and BL tactics, and optimized results through genetic annealing algorithm which turns out positive.
引文
[1] 刘善德.提高钢材利用率是降低造船成本的重要途径.造船技术.2005(04):15~17.
[2] 计华,刘弘.优化排料算法的研究与实现.小型微型计算机系统.2001(22):345~346.
[3] Paull.A.E..Linear programming: A key to optimum newsprint production. Pulp Paper Mag Can,1956: 57.
[4] Eisemann.K..The trim problem. Management Sci, 1957, 3(4): 279~284.
[5] Vajda.S..Trim loss reduction. In: Readings in Linear Programming. New York: Wiley, 1958, ch21, 78~84.
[6] Gilmore.P.C., Gomory.R.E..A linear programming approach to the cutting-stock problem-Part 1.Oper Res, 1961,9: 849~859.
[7] Haims.M.J, Freeman.H..A multistage solution of the template-layout problem. IEEE Trans Syst Sci Cybem, 1970, SSC6(4): 145~151.
[8] Herz.J.C..A recursive computing procedure for two-dimensional stock cutting. IBM J Res Develop, 1972, 16: 462~469.
[9] Christofides.N., Whitlock.C..An Algorithm for Two-Dimensional Cutting Problem. Oper Res, 1977, 14:30~44.
[10] Albano.A..A method to improve two-dimensional layout. Computer-Aided Design, 1979, 9(1): 48~52.
[11] Cheok.B.,Nee.Y..Algorithm for nesting and ship/offshore structural plates. Advances in Design Automation, 1991, DE32(2):221~226.
[12] Yuzu.C.,Lujun.L.,Wang.W.,etc. An expert system for automatic allocation of 2D irregular shapes. In: Proc Expert System in Computer-Aided Design Conference. Int Federation for information Processing, 1987,407~423.
[13] Sriram.M., Kang.S.M..A modified hop-field network for two-dimensional modual placement. Proceedings of IEEE International Symposium on Circuits system, 1990, 16641667.
[14] Zhang.C., Mlynski.D.A.. VLSI-placement with a neural network model. Proceedings of IEEE International Symposium on Circuits system, 1990, 475~478.
[15] Kim.S.S., Kyung.C.M..Circuit placement on arbitrarily shaped regions using the self-organization principle. IEE Trans on Computer Aided Des, 1992, 11(7): 844~854.
[16] Ismail.H.S, Hon.K.K.B..New approach for the nesting of two-dimensional shapes for press tooldesign.Int J Prod Res, 1992,30(4):82583.
[17] Downsland.K.A..Some experiments with simulated annealing techniques for packing problems. European J Opl Res, 1993,68:389~399.
[18] Shahookar.K., Mazumber.P..VLSI cell placement techniques. ACM Computing Surv, 1991, 23(2): 143~164.
[19] Heragu.S.S.,Alga.A.S..Experimental analyses of simulated annealing based algorithms for the layout problem. European J Opl Res,1992, 57: 190202.
[20] Jain.P.,Fenyes.P.,Richer.R..Optimal blank nesting using simulated annealing.Trans ASME J Mesh Des, 1992, 114: 160~165.
[21] Cho.K.H..Integrated CAD/CAM system for fabrication of sheet metal parts:[PhD thesis], Seoul National University, 1993
[22] 夏萼辉,卞铭甲,刘汉培,等.任何形状冲裁件最优排样法.模具技术,1983(3):1628.
[23] 李新军,熊火轮,胡世光.点阵判交——一种计算机自动排样系统设计的新方法,锻压技术,1992(5):22~25.
[24] 林好转.平行线分割一步平移法排样算法的研究,锻压技术.1994(2):37~41.
[25] 董社勤,洪先龙,黄钢,顾均.A Non-Slicing Floorplanning and Placement Algorithm using A New Constraint Graph Based Model,软件学报,2001, 12(11): 11~16
[26] 陶献伟,王华昌,李志刚.矩形件优化套料模拟退火算法求解.锻压技术.2003, 02 8(0 03):24~27.
[27] 陈勇,唐敏,童若锋,董金祥.基于遗传模拟退火算法的不规则多边形套料.计算机辅助设计与图形学学报.2003,05,15(5):598-609.
[28] 方辉,罗阳.分布式并行遗传算法在板材套料优化中的应用.四川大学学报:工程科学版.2003,01,35(1):85~88.
[29] 杨威,罗阳等.大规模矩形零件优化套排的遗传算法.四川大学学报:工程科学版.2001, 033(005):59~62.
[30] 陈迎春,吴晓平,宋业新.约束装箱问题的混合遗传算法求解,运筹与管理,2002,08,11(4):21~25.
[31] 王爱虎,戴佐,查建中.一种基于二叉树结构表达的矩形物体布局的启发式方法.软件学报,1996,6:252~257.
[32] 戴佐,查建中.三维实体布局的八叉树语言及优化算法,计算机辅助设计与图形学学报.1996,1,8(1):61~67.
[33] 李满江,孟祥旭,王志强.矩形件和任意多边形排样问题的算法及应用,贵州工业大学学报自然科学版.2002,8,31(4):126~130.
[34] 谢金星,刑文训.网络优化.清华大学出版社,2000:1~65.
[35] 孙彧．智能排料优化系统及实现．[硕士论文].南京:南京航空航天大学.2000.
[36] 段国林等.模拟退火法在钟手表机芯布局中的应用[J],计算机辅助设计与图形学学报,1999(3):276~279.
[37] Szykman.S.,Cagan.J..A simulated annealing-based approach to three-dimensional component packing[J]. Transaction of the ASME, 1995,117: 308~314.
[38] 张海藩.面向对象程序设计实用教程.清华大学出版社,2002.
[39] [美]Davis Chapman.学用 Visual C++6.0.清华大学出版社,2001.
[40] 黄维通.Visual C++程序设计习题解析与编程实例.清华大学出版社,2001.
[41] [美] Donald Hearn.计算机图形学.第三版,电子工业出版社,2005.
[42] 陈勇、唐敏、董若锋等.基于遗传模拟退火算法的不规则多边形排样.计算机辅助设计与图形学学报,2003,05,15(5):599~603.
[43] A Ramesh Babu, N Ramesh Babu. A genetic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms[J]. Computer-Aided Design, 2001,33(12):879~891.
[2] 计华,刘弘.优化排料算法的研究与实现.小型微型计算机系统.2001(22):345~346.
[3] Paull.A.E..Linear programming: A key to optimum newsprint production. Pulp Paper Mag Can,1956: 57.
[4] Eisemann.K..The trim problem. Management Sci, 1957, 3(4): 279~284.
[5] Vajda.S..Trim loss reduction. In: Readings in Linear Programming. New York: Wiley, 1958, ch21, 78~84.
[6] Gilmore.P.C., Gomory.R.E..A linear programming approach to the cutting-stock problem-Part 1.Oper Res, 1961,9: 849~859.
[7] Haims.M.J, Freeman.H..A multistage solution of the template-layout problem. IEEE Trans Syst Sci Cybem, 1970, SSC6(4): 145~151.
[8] Herz.J.C..A recursive computing procedure for two-dimensional stock cutting. IBM J Res Develop, 1972, 16: 462~469.
[9] Christofides.N., Whitlock.C..An Algorithm for Two-Dimensional Cutting Problem. Oper Res, 1977, 14:30~44.
[10] Albano.A..A method to improve two-dimensional layout. Computer-Aided Design, 1979, 9(1): 48~52.
[11] Cheok.B.,Nee.Y..Algorithm for nesting and ship/offshore structural plates. Advances in Design Automation, 1991, DE32(2):221~226.
[12] Yuzu.C.,Lujun.L.,Wang.W.,etc. An expert system for automatic allocation of 2D irregular shapes. In: Proc Expert System in Computer-Aided Design Conference. Int Federation for information Processing, 1987,407~423.
[13] Sriram.M., Kang.S.M..A modified hop-field network for two-dimensional modual placement. Proceedings of IEEE International Symposium on Circuits system, 1990, 16641667.
[14] Zhang.C., Mlynski.D.A.. VLSI-placement with a neural network model. Proceedings of IEEE International Symposium on Circuits system, 1990, 475~478.
[15] Kim.S.S., Kyung.C.M..Circuit placement on arbitrarily shaped regions using the self-organization principle. IEE Trans on Computer Aided Des, 1992, 11(7): 844~854.
[16] Ismail.H.S, Hon.K.K.B..New approach for the nesting of two-dimensional shapes for press tooldesign.Int J Prod Res, 1992,30(4):82583.
[17] Downsland.K.A..Some experiments with simulated annealing techniques for packing problems. European J Opl Res, 1993,68:389~399.
[18] Shahookar.K., Mazumber.P..VLSI cell placement techniques. ACM Computing Surv, 1991, 23(2): 143~164.
[19] Heragu.S.S.,Alga.A.S..Experimental analyses of simulated annealing based algorithms for the layout problem. European J Opl Res,1992, 57: 190202.
[20] Jain.P.,Fenyes.P.,Richer.R..Optimal blank nesting using simulated annealing.Trans ASME J Mesh Des, 1992, 114: 160~165.
[21] Cho.K.H..Integrated CAD/CAM system for fabrication of sheet metal parts:[PhD thesis], Seoul National University, 1993
[22] 夏萼辉,卞铭甲,刘汉培,等.任何形状冲裁件最优排样法.模具技术,1983(3):1628.
[23] 李新军,熊火轮,胡世光.点阵判交——一种计算机自动排样系统设计的新方法,锻压技术,1992(5):22~25.
[24] 林好转.平行线分割一步平移法排样算法的研究,锻压技术.1994(2):37~41.
[25] 董社勤,洪先龙,黄钢,顾均.A Non-Slicing Floorplanning and Placement Algorithm using A New Constraint Graph Based Model,软件学报,2001, 12(11): 11~16
[26] 陶献伟,王华昌,李志刚.矩形件优化套料模拟退火算法求解.锻压技术.2003, 02 8(0 03):24~27.
[27] 陈勇,唐敏,童若锋,董金祥.基于遗传模拟退火算法的不规则多边形套料.计算机辅助设计与图形学学报.2003,05,15(5):598-609.
[28] 方辉,罗阳.分布式并行遗传算法在板材套料优化中的应用.四川大学学报:工程科学版.2003,01,35(1):85~88.
[29] 杨威,罗阳等.大规模矩形零件优化套排的遗传算法.四川大学学报:工程科学版.2001, 033(005):59~62.
[30] 陈迎春,吴晓平,宋业新.约束装箱问题的混合遗传算法求解,运筹与管理,2002,08,11(4):21~25.
[31] 王爱虎,戴佐,查建中.一种基于二叉树结构表达的矩形物体布局的启发式方法.软件学报,1996,6:252~257.
[32] 戴佐,查建中.三维实体布局的八叉树语言及优化算法,计算机辅助设计与图形学学报.1996,1,8(1):61~67.
[33] 李满江,孟祥旭,王志强.矩形件和任意多边形排样问题的算法及应用,贵州工业大学学报自然科学版.2002,8,31(4):126~130.
[34] 谢金星,刑文训.网络优化.清华大学出版社,2000:1~65.
[35] 孙彧．智能排料优化系统及实现．[硕士论文].南京:南京航空航天大学.2000.
[36] 段国林等.模拟退火法在钟手表机芯布局中的应用[J],计算机辅助设计与图形学学报,1999(3):276~279.
[37] Szykman.S.,Cagan.J..A simulated annealing-based approach to three-dimensional component packing[J]. Transaction of the ASME, 1995,117: 308~314.
[38] 张海藩.面向对象程序设计实用教程.清华大学出版社,2002.
[39] [美]Davis Chapman.学用 Visual C++6.0.清华大学出版社,2001.
[40] 黄维通.Visual C++程序设计习题解析与编程实例.清华大学出版社,2001.
[41] [美] Donald Hearn.计算机图形学.第三版,电子工业出版社,2005.
[42] 陈勇、唐敏、董若锋等.基于遗传模拟退火算法的不规则多边形排样.计算机辅助设计与图形学学报,2003,05,15(5):599~603.
[43] A Ramesh Babu, N Ramesh Babu. A genetic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms[J]. Computer-Aided Design, 2001,33(12):879~891.