临界多边形法在二维不规则零件排样中的研究与实现
|
摘要
二维零件的优化排样技术广泛的应用于制造工业、服装、皮革以及建筑行业中，同时也是一个具有最高计算复杂度的NP完全问题。长期以来，一直是自动化领域的研究热点之一。
任意形状优化排样问题集中体现了两个关键性问题：①．确定参与排样零件之间的位置关系以及最优排放位置。②．确定一个优化的排样序列。本文结合国内外的研究现状和排样问题的自身特点，针对任意形状的二维不规则零件排样问题的关键算法进行了深入的研究，提出了一系列解决优化排样问题的算法。本文的主要研究包括以下内容：
临界多边形是判别两个多边形相互关系的一个非常有效的方法。但是由于直接求解两个凹多边形的临界多边形比较困难，长期以来限制了它的应用。本文提出了多边形凸化分割的方法，将求解两个凹多边形的NFP问题转化为求解两个凸多边形的NFP问题，并加以理论证明，成功地解决了这一问题。
研究了多边形的各种分割方法：三角形化、无Steiner点分割、有Steiner点分割。并且在角平分线分割法的基础上，提出了延长线分割法。
基于CGAL的平面图，讨论了多边形合并算法：排列合并算法、增量合并算法以及divide与conquer算法。
讨论了排样过程中的其它关键性算法，包括曲线的离散化算法、多边形的合成算法、以及多边形的面积算法。
采用遗传算法来优化排样过程的零件调度问题，以材料的利用率为目标函数，产生一个优化的零件排样序列。
论文的算法基于计算几何算法库CGAL(Computational Geometry Algorithms Library)，在Visual C++平台上开发完成。本论文中使用的临界多边形算法不但为排样系统的进一步研究提供了很好的工具，同时对计算机辅助装配、机器人路径规划等研究都有很好的参考价值。
Two-dimensional irregular shape nesting system is widely used in manufacturing industry, garment, leather and architecture industry. It is a one of the NP-complete problem and has been a hot research area for a long time.
Irregular shape nesting problem concerns two key problems: (1). Deciding the relative position of two polygons and calculating the optimal position to place the part. (2). Calculating the optimal nesting sequence. This article, based on the current research status and characteristic of nesting problem, made a profound research in the nesting algorithms and brought out a set of algorithms to solve nesting problem. Specifically, the research contained:
No-Fit Polygon is an effective method to judge the relative position of two polygons. However, the difficulty to derive the No-Fit Polygon of two non-convex polygons limited its application. In this thesis, I simplified this problem into the problem to calculate the NFP of two convex polygons by decomposing the non-convex polygon into convex polygon.
Many polygon decomposition methods are discussed in this thesis: triangulation, decomposition without Steiner point, decomposition with Steiner point. The thesis also brought forward a new method, "edge extending decomposition".
Discussing the polygon union algorithms on the CGAL and Planar Map platform. They are Arrangement Algorithm, Incremental Union Algorithm and Divide and Conquer Algorithm.
Discussing other key algorithms which are used in the nesting process, such as curve digitization algorithm, polygon joining algorithm and polygon area algorithm.
The article employed genetic algorithm to optimize nesting sequence so as to maximize the stock usage efficiency.
Algorithms in this thesis, based on CGAL(Computational Geometry Algorithms Library), are realized on the Visual C++ platform. The method to construct No-Fit Polygon in this thesis is not only a very good tool to make further research in the nesting problem but also a valuable addition to the researches of Computer Aided Assembly, robot path planning, etc.
任意形状优化排样问题集中体现了两个关键性问题：①．确定参与排样零件之间的位置关系以及最优排放位置。②．确定一个优化的排样序列。本文结合国内外的研究现状和排样问题的自身特点，针对任意形状的二维不规则零件排样问题的关键算法进行了深入的研究，提出了一系列解决优化排样问题的算法。本文的主要研究包括以下内容：
临界多边形是判别两个多边形相互关系的一个非常有效的方法。但是由于直接求解两个凹多边形的临界多边形比较困难，长期以来限制了它的应用。本文提出了多边形凸化分割的方法，将求解两个凹多边形的NFP问题转化为求解两个凸多边形的NFP问题，并加以理论证明，成功地解决了这一问题。
研究了多边形的各种分割方法：三角形化、无Steiner点分割、有Steiner点分割。并且在角平分线分割法的基础上，提出了延长线分割法。
基于CGAL的平面图，讨论了多边形合并算法：排列合并算法、增量合并算法以及divide与conquer算法。
讨论了排样过程中的其它关键性算法，包括曲线的离散化算法、多边形的合成算法、以及多边形的面积算法。
采用遗传算法来优化排样过程的零件调度问题，以材料的利用率为目标函数，产生一个优化的零件排样序列。
论文的算法基于计算几何算法库CGAL(Computational Geometry Algorithms Library)，在Visual C++平台上开发完成。本论文中使用的临界多边形算法不但为排样系统的进一步研究提供了很好的工具，同时对计算机辅助装配、机器人路径规划等研究都有很好的参考价值。
Two-dimensional irregular shape nesting system is widely used in manufacturing industry, garment, leather and architecture industry. It is a one of the NP-complete problem and has been a hot research area for a long time.
Irregular shape nesting problem concerns two key problems: (1). Deciding the relative position of two polygons and calculating the optimal position to place the part. (2). Calculating the optimal nesting sequence. This article, based on the current research status and characteristic of nesting problem, made a profound research in the nesting algorithms and brought out a set of algorithms to solve nesting problem. Specifically, the research contained:
No-Fit Polygon is an effective method to judge the relative position of two polygons. However, the difficulty to derive the No-Fit Polygon of two non-convex polygons limited its application. In this thesis, I simplified this problem into the problem to calculate the NFP of two convex polygons by decomposing the non-convex polygon into convex polygon.
Many polygon decomposition methods are discussed in this thesis: triangulation, decomposition without Steiner point, decomposition with Steiner point. The thesis also brought forward a new method, "edge extending decomposition".
Discussing the polygon union algorithms on the CGAL and Planar Map platform. They are Arrangement Algorithm, Incremental Union Algorithm and Divide and Conquer Algorithm.
Discussing other key algorithms which are used in the nesting process, such as curve digitization algorithm, polygon joining algorithm and polygon area algorithm.
The article employed genetic algorithm to optimize nesting sequence so as to maximize the stock usage efficiency.
Algorithms in this thesis, based on CGAL(Computational Geometry Algorithms Library), are realized on the Visual C++ platform. The method to construct No-Fit Polygon in this thesis is not only a very good tool to make further research in the nesting problem but also a valuable addition to the researches of Computer Aided Assembly, robot path planning, etc.
引文
[1]. Julia A. Bennell, Kathryn A. Dowsland, William B. Dowsland. The irregular cutting-stock problem—a new procedure for deriving the no-fit polygon. Computer & Operations Research 28(2001) 271-287.
[2]. Kathryn A. Dowsland. Solution approaches to irregular nesting problems. European Journal of Operational Research 84(1995) 506-521.
[3]. Henry Lamousin. Practice & Experience—Nesting of two-dimensional Irregular Parts Using a Shape Reasoning Heuristic. Computer Aided Design. Vol. 29, No. 3 pp 221-238, 1997.
[4]. Burke E. and Kendall G. "Evaluation of Two Dimensional Bin Packing Problem using the No Fit Polygon", Proceedings of the 26th International Conference on Computers and Industrial Engineering, Melbourne, Australia, 15-17 December 1999, pp 286-291
[5]. Li Z, Milenkovic V. Compaction and Separation Algorithms for Non-convex Polygons and Their Application. European Journal of Operations Research 1995; 84: 539-61.
[6]. Burke E. and Kendall G. "Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem", Proceeings of 12th Australian Joint Conference on Artificial Intelligence, Sydney, Australia, 6-10 December 1999, Lecture Notes in Artifcial Intelligence (1747), Foo, N. (Ed), pp 453-464
[7]. Burke E. and Kendall G. "Applying Simulated Annealing and the No Fit Polygon to the Nesting Problem", Proceedings of WMC '99: World Manufacturing Congress, Durham, UK, 27-30 September, 1999, pp 70-76
[8]. Burke E. and Kendall G. "Applying Evolutionary Algorithms and the No Fit Polygon to the Nesting Problem", in proceedings of IC-AI'99 : The 1999 International Conference on Artificial Intelligence, Las Vegas, Nevada, USA, 28 June-1 July 1999, pp 51-57
[9]. Milenkovic V, Daniels K, Li Z/ Placement and Compaction of Non-convex Polygonsfor Clothing Manufacture. Fourth Canadian Conference on Computational Geometry, St John's, Newfoundland, 1992.
[10]. Ramkumar GD. An Algorithm to Compute the Minkowski Sum Outer-face of Two Simple Polygons. Proceedings of the 12th Annual Symposium on Computational Geometry FCRC 96, 1996.
[11]. Stoyan YG. Ponomarenko LD. Minkowski Sum and Hodograph of the Dense Placement Vector Function. Reports of the SSR Academy of Science. SER.A 10, 1977.
[12]. J. Mark Keil. Polygon Decomposition. Department of Computer Science, University of Saskatchewan, Canada. 1996.
[13]. G.T. Klincsek. Minimal triangulations of polygonal domains. Discrete Math., 9:121-123. 1980
[14]. H.Y.F. Feng and T. Pavlidis. Decomposition of polygons into simpler components: feature generation for syntactic pattern recognition. IEEE Trans. Comput., C-24:636-650, 1975.
[15]. D.H. Greene. The decomposition of polygons into convex parts. In E P. Preparata, editor. Computational Geometry, volume 1 of Advances in Computing Research, pp235-259. 1983.
[16]. J. Mark Keil. Decomposing a polygon into simpler components. Ph.D. thesis, Univ. of Toronto, Toronto, Canada. Report 163/83.
[17]. J.M. Keil and J. Snoeyink. On the time bound for convex decomposition of simple polygons. In Proc. 10th Canad. Conf. Comput. Geom.,1998.
[18]. B. Chazelle and D. P. Dobkin. Optimal convex decompositions. In G. T. Toussaint. Computational Geometry, pp63-133. North-Holland, Amsterdam, Netherlands, 1985
[19]. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry Algorithms and Applications. Springer-Verlag, Berlin, 1997
[20]．张维锦，张新系，任意多边形的面积计算及在造价分析中的应用。华东交通大学学报，第十七卷第一期，2000年3月。
[21]. Graham Kendall. Thesis of University of Nottingham for the Degree of Ph.D. Oct., 2000
[22]. Eyal Flato, Dan Halperin, The Design and Implementation of Planar Maps in CGAL, Tel Aviv 69978.
[23]. The CGAL User Manual, Version 2.2, 2001, http://www.cgal.org;
[24]. Henry L, Warren N. Practice & Experience Nesting of Two-dimensional Irregular Parts Using a Shape Reasoning Heuristic. Computer Aided Design. 1997, 29(3), pp.221-238.
[25]．刘嘉敏，张胜男，黄有群：二维不规则形状自动排料算法的研究与实现。《计算机辅助设计与图形学学报》，2000，12(7)：488-491。
[26]．曹矩，胡修彪：大规模矩形件优化排样的遗传算法。《锻压机械》，1999，(4)：17-20。
[27]．曹矩，冯松：遗传算法在矩形件优化排样中的应用。《计算机工程与应用》，1999，(5)：5-7。
[28]．魏生民，韩云霞：CAN--计算机辅助排样软件包。《微机发展》，No．6，
PP．10-13，1993。
[29]．徐彦欣：基于产生式规则的二维不规则零件的排料算法。《小型微型计算机系统》，1998，19(10)：48-52。
[30]．滕健，李滨慧，施洪生等：用神经网络解决二维不规则零件的排料问题。《机械设计与制造制造工程》，1999，28(6)：61-63
[31]．一个快速有效的凹多边形分解算法 鞍山师范学院学报。2001—03，3(1)：99—102。
[32]．孔永明 康小明 马泽恩 基于微机的板料自动排样与下料系统 机械工业自动化
[33]．龚时华，邓勇等 计算机自动排样系统中NFP问题的算法实现 华中理工大学学报 Vol 26 No 12 Dec 1998．
[34]．李英华，周兆英 熊沈蜀等 二维几何排样问题分类编码的研究 机械科学与技术。Vol．19 No．3，2000。
[35]．严蔚敏，吴伟民编著 数据结构 清华大学出版社，1998。
[36]．唐荣锡主编，CAD／CAM技术，北京航空航天大学出版社，1994年。
[37]．金文标 金通，曲线造型的本征离散法，高校应用数学学报 Vol．13 Ser．A 1998增刊。
[38]．李博轩，Visual C++6.0图形用户界面开发指南，清华大学出版社，2000年11月3。
[39]．李博轩，Visual C++6.0数据库开发指南，清华大学出版社，2000年11月3。
[40]. Murray Hill, New Jersey, The C++ Programming Language, Third Edition, AT&T Labs, 1999.
[41]．David J．Kruglinski，Scot Wingo，Visual C++技术内幕6.0，第五版。北京希望电子出版社，2000年2月。
[2]. Kathryn A. Dowsland. Solution approaches to irregular nesting problems. European Journal of Operational Research 84(1995) 506-521.
[3]. Henry Lamousin. Practice & Experience—Nesting of two-dimensional Irregular Parts Using a Shape Reasoning Heuristic. Computer Aided Design. Vol. 29, No. 3 pp 221-238, 1997.
[4]. Burke E. and Kendall G. "Evaluation of Two Dimensional Bin Packing Problem using the No Fit Polygon", Proceedings of the 26th International Conference on Computers and Industrial Engineering, Melbourne, Australia, 15-17 December 1999, pp 286-291
[5]. Li Z, Milenkovic V. Compaction and Separation Algorithms for Non-convex Polygons and Their Application. European Journal of Operations Research 1995; 84: 539-61.
[6]. Burke E. and Kendall G. "Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem", Proceeings of 12th Australian Joint Conference on Artificial Intelligence, Sydney, Australia, 6-10 December 1999, Lecture Notes in Artifcial Intelligence (1747), Foo, N. (Ed), pp 453-464
[7]. Burke E. and Kendall G. "Applying Simulated Annealing and the No Fit Polygon to the Nesting Problem", Proceedings of WMC '99: World Manufacturing Congress, Durham, UK, 27-30 September, 1999, pp 70-76
[8]. Burke E. and Kendall G. "Applying Evolutionary Algorithms and the No Fit Polygon to the Nesting Problem", in proceedings of IC-AI'99 : The 1999 International Conference on Artificial Intelligence, Las Vegas, Nevada, USA, 28 June-1 July 1999, pp 51-57
[9]. Milenkovic V, Daniels K, Li Z/ Placement and Compaction of Non-convex Polygonsfor Clothing Manufacture. Fourth Canadian Conference on Computational Geometry, St John's, Newfoundland, 1992.
[10]. Ramkumar GD. An Algorithm to Compute the Minkowski Sum Outer-face of Two Simple Polygons. Proceedings of the 12th Annual Symposium on Computational Geometry FCRC 96, 1996.
[11]. Stoyan YG. Ponomarenko LD. Minkowski Sum and Hodograph of the Dense Placement Vector Function. Reports of the SSR Academy of Science. SER.A 10, 1977.
[12]. J. Mark Keil. Polygon Decomposition. Department of Computer Science, University of Saskatchewan, Canada. 1996.
[13]. G.T. Klincsek. Minimal triangulations of polygonal domains. Discrete Math., 9:121-123. 1980
[14]. H.Y.F. Feng and T. Pavlidis. Decomposition of polygons into simpler components: feature generation for syntactic pattern recognition. IEEE Trans. Comput., C-24:636-650, 1975.
[15]. D.H. Greene. The decomposition of polygons into convex parts. In E P. Preparata, editor. Computational Geometry, volume 1 of Advances in Computing Research, pp235-259. 1983.
[16]. J. Mark Keil. Decomposing a polygon into simpler components. Ph.D. thesis, Univ. of Toronto, Toronto, Canada. Report 163/83.
[17]. J.M. Keil and J. Snoeyink. On the time bound for convex decomposition of simple polygons. In Proc. 10th Canad. Conf. Comput. Geom.,1998.
[18]. B. Chazelle and D. P. Dobkin. Optimal convex decompositions. In G. T. Toussaint. Computational Geometry, pp63-133. North-Holland, Amsterdam, Netherlands, 1985
[19]. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry Algorithms and Applications. Springer-Verlag, Berlin, 1997
[20]．张维锦，张新系，任意多边形的面积计算及在造价分析中的应用。华东交通大学学报，第十七卷第一期，2000年3月。
[21]. Graham Kendall. Thesis of University of Nottingham for the Degree of Ph.D. Oct., 2000
[22]. Eyal Flato, Dan Halperin, The Design and Implementation of Planar Maps in CGAL, Tel Aviv 69978.
[23]. The CGAL User Manual, Version 2.2, 2001, http://www.cgal.org;
[24]. Henry L, Warren N. Practice & Experience Nesting of Two-dimensional Irregular Parts Using a Shape Reasoning Heuristic. Computer Aided Design. 1997, 29(3), pp.221-238.
[25]．刘嘉敏，张胜男，黄有群：二维不规则形状自动排料算法的研究与实现。《计算机辅助设计与图形学学报》，2000，12(7)：488-491。
[26]．曹矩，胡修彪：大规模矩形件优化排样的遗传算法。《锻压机械》，1999，(4)：17-20。
[27]．曹矩，冯松：遗传算法在矩形件优化排样中的应用。《计算机工程与应用》，1999，(5)：5-7。
[28]．魏生民，韩云霞：CAN--计算机辅助排样软件包。《微机发展》，No．6，
PP．10-13，1993。
[29]．徐彦欣：基于产生式规则的二维不规则零件的排料算法。《小型微型计算机系统》，1998，19(10)：48-52。
[30]．滕健，李滨慧，施洪生等：用神经网络解决二维不规则零件的排料问题。《机械设计与制造制造工程》，1999，28(6)：61-63
[31]．一个快速有效的凹多边形分解算法 鞍山师范学院学报。2001—03，3(1)：99—102。
[32]．孔永明 康小明 马泽恩 基于微机的板料自动排样与下料系统 机械工业自动化
[33]．龚时华，邓勇等 计算机自动排样系统中NFP问题的算法实现 华中理工大学学报 Vol 26 No 12 Dec 1998．
[34]．李英华，周兆英 熊沈蜀等 二维几何排样问题分类编码的研究 机械科学与技术。Vol．19 No．3，2000。
[35]．严蔚敏，吴伟民编著 数据结构 清华大学出版社，1998。
[36]．唐荣锡主编，CAD／CAM技术，北京航空航天大学出版社，1994年。
[37]．金文标 金通，曲线造型的本征离散法，高校应用数学学报 Vol．13 Ser．A 1998增刊。
[38]．李博轩，Visual C++6.0图形用户界面开发指南，清华大学出版社，2000年11月3。
[39]．李博轩，Visual C++6.0数据库开发指南，清华大学出版社，2000年11月3。
[40]. Murray Hill, New Jersey, The C++ Programming Language, Third Edition, AT&T Labs, 1999.
[41]．David J．Kruglinski，Scot Wingo，Visual C++技术内幕6.0，第五版。北京希望电子出版社，2000年2月。
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |