二维不规则图形的排样算法
|
摘要
优化排样问题是指寻求二维图形在特定长度,宽度区域内的摆放尽可能多,以使区域的利用率达到最优。它在服装、皮革制品、体育用品、机械等制造行业中都有应用。国内有成千上万家这样的企业,大部分企业仍处于手工排样下料阶段,下料利用率较低,造成原材料的浪费。因此有效提高原材料的利用率,降低生产成本,是增加企业效益的有效途径之一。二维不规则图形的优化排样问题是一个在许多生产实践中有关键应用的重要问题,也是一个计算机科学和运筹学中的基本问题。在理论上属于NP--完全(困难)问题,因为存在实际形状的复杂性和计算上的复杂性,求解十分困难。
目前研究较多的是规则零件(如矩形)的排样问题,对不规则件的研究较少。对不规则件的处理基本上是基于规则零件排样处理的矩形近似方法和对不规则零件直接处理两种方法。本文应用一种名为挤压算法的近优算法。它是一种基于对不规则零件直接处理的方法。使用该算法能提高材料的利用效率,它通过在排样过程中对相邻的两个和两排的图形进行向左,向下的移动,通过减少它们之间的空隙来实现此目的。在排样计算的过程中,如何找到零件之间在什么位置靠接紧密并且不重叠是一个关键的问题。此外,它会利用到一些与图形学相关算法。以下为它的基本步骤:
1、通过预处理,将所有的待摆放的多边形分别绕它们的重心旋转一个角度,从而可以得到它们最佳包络矩形。
2、计算相邻的两个和两排的图形的最小距离。
3、根据这个最小距离,移动它们,从而减少它们之间的空隙。
但仅有此算法不能对整个排样问题进行优化处理。因为它要求在实际的摆放前必须得到一个多边形的摆放序列。它必须和某种具有全局搜索能力能提供这种摆放序列的算法相结合运用,才能达到我们所需的效果。遗传算法是一种很好的全局优化算法。它以达尔文的生物进化论为启发而创建,借助选择、交叉、变异等操作逐步逼近最优解。具有隐含并行机制和自适应性。本文对遗传算法的发展现状进行分析。在对基本遗传算法的优缺点进行分析后,主要针对它的局部搜索能力差,全局搜索速度较慢和早熟现象提出改进。主要是针对遗传算法进行遗传算子(选择算子、交叉算子和变异算子)的改进。通过以上分析,将两种算法混合
Optimizing nesting generally refers to arranging as many as possible needed geometrical graphic in some plane regions with constrained length and width.,which appears in many industries, such as the industries of rag trade, leather, sports goods, mechanical manufacturing, and so on. There are thousands of enterprises ,which have Optimizing nesting problems in our country, but the majority of them use hand-generated cutting patterns in the nesting process. As a result, the material usage is low and the amount of waste is large. Improving material usage may reduce the costs of production and it is an efficient way to increase the profits of the enterprises. The optimization of two-dimensional irregular graphic layout is a basic problem in computer science and operational research, and has root key applications in many industries. But the current results from traditional methods do not satisfy real applications. In theory, the nesting problem of two-dimensional irregular shapes belongs to the NP-hard problems. It is very difficult to find the optimal solution for such a problem because of the complexity of shapes and computation.
Currently, most of the papers published in the area are concerned with the cutting problem of regular shapes (such as rectangular), only few is about the irregular shapes. One method about irregular shapes nesting is approximately rectangle solution method based on regular shapes, the other method is to deal with the irregular shapes directly. This paper presents a new approximation optimal method, named collision algorithm, about the packing space based on the latter method. Using this algorithm, we can improve the efficiency of cutting through colliding left and down in the processing of placement. So it undoubtedly decrease interspaces between two neighbor graphics and two chains of graphics. How to find the positions where shapes are not overlapping and are contacted is one of crucial technologies of optimization problem in the courses. It involves with some graphic algorithms . Following is its
目前研究较多的是规则零件(如矩形)的排样问题,对不规则件的研究较少。对不规则件的处理基本上是基于规则零件排样处理的矩形近似方法和对不规则零件直接处理两种方法。本文应用一种名为挤压算法的近优算法。它是一种基于对不规则零件直接处理的方法。使用该算法能提高材料的利用效率,它通过在排样过程中对相邻的两个和两排的图形进行向左,向下的移动,通过减少它们之间的空隙来实现此目的。在排样计算的过程中,如何找到零件之间在什么位置靠接紧密并且不重叠是一个关键的问题。此外,它会利用到一些与图形学相关算法。以下为它的基本步骤:
1、通过预处理,将所有的待摆放的多边形分别绕它们的重心旋转一个角度,从而可以得到它们最佳包络矩形。
2、计算相邻的两个和两排的图形的最小距离。
3、根据这个最小距离,移动它们,从而减少它们之间的空隙。
但仅有此算法不能对整个排样问题进行优化处理。因为它要求在实际的摆放前必须得到一个多边形的摆放序列。它必须和某种具有全局搜索能力能提供这种摆放序列的算法相结合运用,才能达到我们所需的效果。遗传算法是一种很好的全局优化算法。它以达尔文的生物进化论为启发而创建,借助选择、交叉、变异等操作逐步逼近最优解。具有隐含并行机制和自适应性。本文对遗传算法的发展现状进行分析。在对基本遗传算法的优缺点进行分析后,主要针对它的局部搜索能力差,全局搜索速度较慢和早熟现象提出改进。主要是针对遗传算法进行遗传算子(选择算子、交叉算子和变异算子)的改进。通过以上分析,将两种算法混合
Optimizing nesting generally refers to arranging as many as possible needed geometrical graphic in some plane regions with constrained length and width.,which appears in many industries, such as the industries of rag trade, leather, sports goods, mechanical manufacturing, and so on. There are thousands of enterprises ,which have Optimizing nesting problems in our country, but the majority of them use hand-generated cutting patterns in the nesting process. As a result, the material usage is low and the amount of waste is large. Improving material usage may reduce the costs of production and it is an efficient way to increase the profits of the enterprises. The optimization of two-dimensional irregular graphic layout is a basic problem in computer science and operational research, and has root key applications in many industries. But the current results from traditional methods do not satisfy real applications. In theory, the nesting problem of two-dimensional irregular shapes belongs to the NP-hard problems. It is very difficult to find the optimal solution for such a problem because of the complexity of shapes and computation.
Currently, most of the papers published in the area are concerned with the cutting problem of regular shapes (such as rectangular), only few is about the irregular shapes. One method about irregular shapes nesting is approximately rectangle solution method based on regular shapes, the other method is to deal with the irregular shapes directly. This paper presents a new approximation optimal method, named collision algorithm, about the packing space based on the latter method. Using this algorithm, we can improve the efficiency of cutting through colliding left and down in the processing of placement. So it undoubtedly decrease interspaces between two neighbor graphics and two chains of graphics. How to find the positions where shapes are not overlapping and are contacted is one of crucial technologies of optimization problem in the courses. It involves with some graphic algorithms . Following is its
引文
[1] 杨彩、顾海明、史俊友、郑桂荣. 不规则件最优排放布局的实现[J]. 青 岛 科 技 大学 学 报,2005, 26(2): 146-149.
[2] 曹炬,胡德彪.大规模矩形件优化排样的遗传算法[J].锻压机械,1999,34(4):17-20.
[3] 陶献伟,王华昌,李志刚.基于填充算法的矩形件排样优化求解[J].中国机械工程,2003,14(13):1104-1107.
[4] Hopper E,Turton B.A genetic algorithm for a 2D industrial packing problem[J]. Computer and Industrial Engineering,1999,37(1):375-378.
[5] 贾志欣,殷国富,罗阳.二维不规则零件排样问题的遗传算法求解[J].计算机辅助设计与图形学学报,2002,14(5):467-470.
[6] 周建华,赵建军,吴铺 . 不规则形状零件优化排样的关键技术 [J]. 现代机械,1998,5(2):29-31
[7] 李明, 宋成芳, 周泽魁. 一种二维不规则零件优化排样算法[J]. 四川大学学报(工程科学版),2005,37(4):134-138
[8] 宋亚男 ,邓飞其 ,叶家玮 基于改进免疫遗传算法的不规则图形排样[J].计 算 机 工程(Computer Engineering),2005,31(9):170-172.
[9] 林海鹏. 二维不规则图形排样算法的优化[J] .煤矿机械,2003,12(3):39-41.
[10] 李明, 宋成芳, 周泽魁. 一种二维不规则零件优化排样算法[J]. 四川大学学报(工程科学版),2005,37(4):134-138
[11] 王小平,曹立明 遗传算法理论与应用[M].西安:西安交通大学出版社,2001:4-9
[12] 黄红兵,蒋望东.二维不规则零件优化排样问题的研究[J].广西科学院学,2004,20(4):225-227
[13] 周明,孙树栋 遗传算法原理及应用[M].北京:国防工业出版社,2005:13-17
[14] 贾 志 欣 . 排 样 问 题 的 研 究 现 状 与 趋 势 [J]. 计 算 机 辅 助 设 计 与 图 形 学 学报,2004,16(7):890-896
[15] Venugopal V, Narendran T. Genetic algorithm approach to the machine component grouping problem with multiple objectives[J].Computers &Industrial Engineering,1992,19(4): 469-480
[16] Dagli CH.Tatoglu M Y. An approach to two dimensional cutting stock problem[J].International Journal of Production Research,1987,25(2):175-190
[17] Berkey J O,Wang P Y. Two dimensional finite bin packing algorithms[J].Journal of Operational Research,1987,38(5):423-429
[18] Coffman EG,Shor P W. Average case analysis of cutting and packing in two dimensions[J].European Journal of Operation Research,1990,44(2):134-144
[19] Dagli C. Cutting stock problem Combined use of heuristics and optimization methods{A}.In: Proceedings of the 9th International Conference on Production Research,1987.843-849
[20] Gilmore P. C,Gomory R. E. A linear programming approach to the cutting stock problem[J].European Journal of Operations Research, 1961,9: 849-859
[21] 李建勇,鄂明成,曹月东.利用混沌人工神经元网络进行布局优化计算[J].制造业自动化, 2000, 22(1): 21-22
[22] Beasley 1E .An exact two-dimensional non-guillotine cutting tree search procedure[J].Operations Research , 1985,33:49-64
[23] Dagli C H. Knowledge based systems for cutting stock problems[J].European Journal of Operational Research,1990,44(2):160-166
[24] Schollmeyer M, Lin JQ ,Krishnamurthy K. Hybrid expert system and operations research for solving nesting problems {A}.In: Proceedings of the World Congress Expert System[C].New York: Pergamon Press,1991.1223-1231
[25] Downsland K A. Efficient automated Pallet loading[J].European Journal of Operational Research,1990,44(2):232-238
[26] Farley A. Selection of stock plate characteristics and cutting style for two dimensional cutting stock situations[J].European Journal of Operational Research,1990,44(2):239-246
[27] Adsen B G. An application of traveling-salesman routines to solve pattern allocation problems in glass industry[J].Journal of the Operational Research Society,1988,39(3):249-256
[28] Hopper E.Turton B C H. An empirical investigation of heuristic and heuristic algorithm for a 2D packing problem[J]. European Journal of Operational Research,2001,128(1):34-57
[29] 李明, 宋成芳, 周泽魁.二维不规则零件排样问题的粒子群算法求解[J].江南大学学报(自然科学版),2005,4(3):266-269.
[30] 王小平,曹立明 遗传算法理论与应用[M].西安:西安交通大学出版社,2001:4-9
[31] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2005:18-25
[32] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2005:21-29
[33] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2005:32-54
[34] 孙家广.计算机图形学[M]:北京:清华大学出版社,1998:369
[35] 数学手册编写组:《数学手册》,高等教育出版社,1984.6,332 页。
[36] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2005:13-17
[37] Defu Zhang,Yan Kang,Ansheng Deng.A new heuristic recursive algorithm for the strip rectangular packing problem[J].Computer&Operations Research 33(2006):2209-2217
[38] 宋亚男等.不规则图形排样系统中靠接算法研究[J].计算机工程.2004,30(19):7-9
[2] 曹炬,胡德彪.大规模矩形件优化排样的遗传算法[J].锻压机械,1999,34(4):17-20.
[3] 陶献伟,王华昌,李志刚.基于填充算法的矩形件排样优化求解[J].中国机械工程,2003,14(13):1104-1107.
[4] Hopper E,Turton B.A genetic algorithm for a 2D industrial packing problem[J]. Computer and Industrial Engineering,1999,37(1):375-378.
[5] 贾志欣,殷国富,罗阳.二维不规则零件排样问题的遗传算法求解[J].计算机辅助设计与图形学学报,2002,14(5):467-470.
[6] 周建华,赵建军,吴铺 . 不规则形状零件优化排样的关键技术 [J]. 现代机械,1998,5(2):29-31
[7] 李明, 宋成芳, 周泽魁. 一种二维不规则零件优化排样算法[J]. 四川大学学报(工程科学版),2005,37(4):134-138
[8] 宋亚男 ,邓飞其 ,叶家玮 基于改进免疫遗传算法的不规则图形排样[J].计 算 机 工程(Computer Engineering),2005,31(9):170-172.
[9] 林海鹏. 二维不规则图形排样算法的优化[J] .煤矿机械,2003,12(3):39-41.
[10] 李明, 宋成芳, 周泽魁. 一种二维不规则零件优化排样算法[J]. 四川大学学报(工程科学版),2005,37(4):134-138
[11] 王小平,曹立明 遗传算法理论与应用[M].西安:西安交通大学出版社,2001:4-9
[12] 黄红兵,蒋望东.二维不规则零件优化排样问题的研究[J].广西科学院学,2004,20(4):225-227
[13] 周明,孙树栋 遗传算法原理及应用[M].北京:国防工业出版社,2005:13-17
[14] 贾 志 欣 . 排 样 问 题 的 研 究 现 状 与 趋 势 [J]. 计 算 机 辅 助 设 计 与 图 形 学 学报,2004,16(7):890-896
[15] Venugopal V, Narendran T. Genetic algorithm approach to the machine component grouping problem with multiple objectives[J].Computers &Industrial Engineering,1992,19(4): 469-480
[16] Dagli CH.Tatoglu M Y. An approach to two dimensional cutting stock problem[J].International Journal of Production Research,1987,25(2):175-190
[17] Berkey J O,Wang P Y. Two dimensional finite bin packing algorithms[J].Journal of Operational Research,1987,38(5):423-429
[18] Coffman EG,Shor P W. Average case analysis of cutting and packing in two dimensions[J].European Journal of Operation Research,1990,44(2):134-144
[19] Dagli C. Cutting stock problem Combined use of heuristics and optimization methods{A}.In: Proceedings of the 9th International Conference on Production Research,1987.843-849
[20] Gilmore P. C,Gomory R. E. A linear programming approach to the cutting stock problem[J].European Journal of Operations Research, 1961,9: 849-859
[21] 李建勇,鄂明成,曹月东.利用混沌人工神经元网络进行布局优化计算[J].制造业自动化, 2000, 22(1): 21-22
[22] Beasley 1E .An exact two-dimensional non-guillotine cutting tree search procedure[J].Operations Research , 1985,33:49-64
[23] Dagli C H. Knowledge based systems for cutting stock problems[J].European Journal of Operational Research,1990,44(2):160-166
[24] Schollmeyer M, Lin JQ ,Krishnamurthy K. Hybrid expert system and operations research for solving nesting problems {A}.In: Proceedings of the World Congress Expert System[C].New York: Pergamon Press,1991.1223-1231
[25] Downsland K A. Efficient automated Pallet loading[J].European Journal of Operational Research,1990,44(2):232-238
[26] Farley A. Selection of stock plate characteristics and cutting style for two dimensional cutting stock situations[J].European Journal of Operational Research,1990,44(2):239-246
[27] Adsen B G. An application of traveling-salesman routines to solve pattern allocation problems in glass industry[J].Journal of the Operational Research Society,1988,39(3):249-256
[28] Hopper E.Turton B C H. An empirical investigation of heuristic and heuristic algorithm for a 2D packing problem[J]. European Journal of Operational Research,2001,128(1):34-57
[29] 李明, 宋成芳, 周泽魁.二维不规则零件排样问题的粒子群算法求解[J].江南大学学报(自然科学版),2005,4(3):266-269.
[30] 王小平,曹立明 遗传算法理论与应用[M].西安:西安交通大学出版社,2001:4-9
[31] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2005:18-25
[32] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2005:21-29
[33] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2005:32-54
[34] 孙家广.计算机图形学[M]:北京:清华大学出版社,1998:369
[35] 数学手册编写组:《数学手册》,高等教育出版社,1984.6,332 页。
[36] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2005:13-17
[37] Defu Zhang,Yan Kang,Ansheng Deng.A new heuristic recursive algorithm for the strip rectangular packing problem[J].Computer&Operations Research 33(2006):2209-2217
[38] 宋亚男等.不规则图形排样系统中靠接算法研究[J].计算机工程.2004,30(19):7-9