【作者】 刘胡瑶；

【导师】 何援军；

【作者基本信息】 上海交通大学 ， Computer Application Technology， 2007， 博士

【摘要】 本文研究二维排样问题。二维排样是一个平面布局优化问题,目的是在平面板材上尽可能多的布置不同形状的零件,并满足以下约束条件:(1)零件布置于板材内部;(2)各零件之间互不重叠;(3)满足一定的工艺要求。它的优化目标是:寻求一个零件布局方案,使得浪费的板材面积为最小,亦即材料利用率为最大。排样问题对船舶、服装、模具等行业有重要意义。针对目前二维排样问题中的难点和关键问题,本文进行了广泛而深入的理论研究,包括二维排样问题中的几何计算、矩形排样、二维不规则形状排样以及智能优化算法在排样问题中的应用等,提出了一系列解决方案和算法。研究成果和创新点可概括如下:(1)临界多边形NFP算法研究:提出了一种新的基于轨迹线计算的临界多边形快速求解算法,解决了NFP求解的准确性问题,并在NFP的计算速度上有了较大的提高(O(mn))。NFP算法是二维排样问题中的基础性几何计算问题,也是目前限制二维排样算法发展的瓶颈问题。由于长期以来缺乏准确、稳定、快速的NFP算法,使得零件定位优化、多角度旋转、板材带孔洞等问题得不到很好的解决,而NFP算法的计算速度也限制了排样问题往智能优化方面发展。基于NFP算法的重要性和基础性,本文提出了一种新的临界多边形快速求解算法,力求比较彻底地解决NFP计算问题。该算法将多边形滑动碰撞问题转化为顶点和边之间的轨迹线计算,从而可引入几何图形索引算法降低时间复杂度,并可统一处理边界空腔和内部靠接NFP等特殊情况。算法的基本步骤是:(1)求解多边形顶点相对于另一多边形的轨迹线;(2)求解轨迹线集合所形成的逆时针外包多边形和内部顺时针环,得到的多边形即为临界多边形。算法采用了基于网格的线段索引方法来加快线段之间的求交计算,进一步提高了NFP求解的计算速度。理论分析和实验结果表明新的NFP算法可以同时处理内靠接NFP计算、边界空腔、板材孔洞等特殊情况,其计算速度较优化移动碰撞法有较大提高(算例2-1~2-2)。(2)二维矩形排样算法研究:分析了矩形零件的现有定位策略,提出了一个基于临界多边形的矩形件定位算法,算法具有较高的定位点搜索能力和较低的时间复杂度O(n2)。研究了矩形排样问题的零件定位算法及启发式排样算法。研究了已有的矩形排样问题的数学模型,针对矩形排样中的两个关键问题——零件定位策略和启发式排样算法进行了分析和改进:在零件的定位策略上提出了基于临界多边形NFP的矩形件定位策略,在求解得到NFP的基础上,将零件定位于NFP的最低最左点。与已有定位算法相比,NFP定位算法的时间复杂度较低(O(n)),并且可对定位点进行全面搜索,有效减少了排样过程中形成的内部空腔面积浪费;在启发式求解排样算法方面,提出了基于最佳适应度优先的启发式排样规则,综合考虑待排零件定位后的材料利用率、面积以及最低Y坐标等评价指标,选择具有最佳适应度的零件作为优先排样零件。此外,本文还将单板材NFP定位算法推广到多板材NFP定位算法,得到了多板材矩形排样算法(算例3-1、3-2)。(3)不规则形状排样算法研究:提出了基于重心NFP的不规则形状零件定位算法和启发式排样算法。通过选择多角度重心NFP中的最低重心位置来确定零件的排样位置,从而达到提高零件分布密度的目的。在不规则形状零件的定位策略上,本文利用NFP计算并通过零件的旋转,提出了基于重心NFP的不规则形状零件定位策略。利用零件重心作为NFP的参考点计算出重心NFP,通过选择多角度重心NFP中的最低重心位置来确定零件的排样位置。在异形件的启发式排样算法上,针对异形件排样方案中容易出现孔洞的问题,提出了顺序递归排样算法,当出现较大孔洞浪费时通过动态调整零件排样次序来减少孔洞的形成,使排样利用率明显提高(算例4-1~4-4)。(4)智能排样算法研究:结合排样问题的具体特点,研究了模拟退火算法(SA)和遗传算法(GA)等智能排样算法,使排样具有较强的全局优化能力,取得比启发式算法更好的排样效果。研究了SA、GA等智能优化算法在二维排样问题中的应用。使上述智能优化算法也适用于本文提出的矩形件和不规则件的排样。在模拟退火算法方面:阐述了模拟退火优化算法的基本原理、技术特点及算法过程,根据排样问题的特点设计退火算法的实现过程及关键参数,如排样方案的编码及解码、领域函数、初温的设定、降温速率设置等内容,最后运用退火排样算法进行了实例计算并和现有排样算法的最好计算结果进行了对比(算例5-1~5-2)。在遗传算法方面:研究了个体的编码和解码、适应度的计算、个体复制过程的设计、交叉变异过程的设计以及交叉变异概率的设置等内容,最后进行了实例计算和对比(算例5-3~5-5)。实验表明智能排样算法的计算时间较长,但是具有较强的全局优化能力,能够取得比启发式算法更好的排样效果。更多还原

【Abstract】 Research on two dimensional (2D) nesting problems was presented in this thesis. 2D nesting is a kind of planar layout optimization problem with object of arranging a number of pieces inside a given plate, and in the same time, following restrictions must be satisfied: (1) pieces should be nested inside the plate; (2) each piece should not overlap with another; (3) certain restrictions on manufacture should be fulfilled. The optimization object of 2D nesting problem is to find an arrangement for pieces, and minimize the wasted material, in other words, the material usage ratio should be maximized. Nesting problem has a significant influence on the industries such as ship-building, costume making, and mold-manufacture.According to the key problems and difficulties existed in nesting problem, the thesis presented a fundamental researching and proposed corresponding algorithms and resolutions. The main research objects of 2D nesting problem include geometric calculation, rectangular nesting, 2D irregular nesting and the application of intelligent optimization on nesting problem. Detailed research achievements and creative ideas are listed below:(1) Research on No Fit Polygon algorithm: The basic geometric calculation problems were detailly analysised and researched, especially for the key algorithm of nesting problem– No Fit Polygon (NFP) algorithm. NFP algorithm is the neck factor for the development of 2D nesting algorithms, due to the lack of precise, stable and fast NFP algorithm for a long time, some problems such as optimization of piece’s location, piece’s rotation and holes in plate are still not perfectly resolved. On the other hand, defects of existing NFP algorithms have been the main obstacle for the development of implementation of intelligent algorithm on nesting problem. Due to the importance and fundamental function of NFP, this thesis presented a new fast NFP algorithm,that converted the problem of collision between two polygons to the calculation of trace line segment for vertices and edges, and it can deal with the special conditions such as inner cavity holes and inner contacting NFP. The basic principle of the new NFP algorithm is: (1) computing the trace line segment between vertices of one polygon and edges of another polygon; (2) Finding out the enclosure polygon and inner clockwise loops formed by all trace line segments, then the resulted enclosure polygon and inner loops are the final NFP. The new NFP algorithm adopted one grid-based index algorithm for line segments to speedup the computation on interaction between line segments. Experiment results show that the new NFP algorithm can perfectly resolve the problems such as inner NFP, cavity on edges, holes inside plate at the same time. At the same time its calculation speed is up to hundreds times faster than existing NFP algorithms. In addition, 2D nesting related geometric algorithms, such as polygon boolean operations with tolerance and determination on polygon’s wise, are also analyzed and enhanced in this thesis.(2) Research on 2D rectangular nesting algorithm: Mainly include the piece placement algorithm and heuristic nesting algorithm. Firstly the mathematic model of rectangular nesting problem was analyzed, and then the two key technology of rectangular nesting problem– piece placement policy and heuristic algorithm were researched. Principle and technical character of existing placement algorithm were analyzed, and NFP based rectangular placement policy was proposed. Based on the achieved NFP, the piece was placed on the left and bottom point of NFP. Compared with other placement policy, the time complexity of NFP based placement algorithm is low (O(N)), and it can globally search the feasible placement points, hence it effectively reduced the material waste caused by inner cavity, therefore the material usage ratio is increased. Secondly on the heuristic algorithm for nesting problem, this thesis proposed a heuristic nesting algorithm based on fitness evaluating, in this heuristic algorithm, material usage ratio, area changing and lowest Y coordinates were integrated to evaluate the fitness which be used as a heuristic rule, and based on this heuristic rule, the pieces was nested in order while piece with higher fitness was nested first. On the other hand, this thesis proposed a multi-plates nesting algorithm, it adopted a revised NFP placement algorithm based on single plate NFP algorithm, and achieved an ideal result. The experiment results show that the NFP based rectangular placement algorithm can obviously increase the nesting quality while its time complexity is low (nesting quality increase by about 20% in dataset 3-1 and 3-2).(3) Research on irregular nesting algorithm: Piece placement algorithm and heuristic algorithm in irregular shaped nesting problem were researched. Due to the irregular in shape of pieces and plate, specific placement policy and heuristic algorithm should be researched. Firstly in the placement policy for irregular shaped pieces, this thesis using a NFP and multi-rotation hybrid method, and proposed a new piece placement policy which based on lowest center of gravity rule, with gravity center of piece as the reference point, the gravity center NFP can be calculated; Secondly from all the gravity center NFPs which caused by different rotation, the lowest gravity center can be find. Secondly on the heuristic algorithm for irregular nesting, in order to reduce the waste caused by holes, this thesis proposed an order-based recursive nesting algorithm, in the procedure of recursive nesting algorithm, the nesting order of pieces was adjusted when large holes was detected. Finally experiments on the benchmark dataset was presented to compare the new algorithm and existing ones, the experiment results show significant improvement in algorithms proposed by this thesis (dataset 4-1~4-4).(4) Research on intelligent nesting algorithm: Genetic algorithm and annealing algorithm implementation in nesting problem were researched. Adopted intelligent algorithms can work for both rectangular nesting problem and irregular nesting problem. Nesting problem is a typical combination optimization problem, so it is suitable to introduce intelligent algorithm such as SA, GA and TA etc. into nesting problem. This paper adopted GA and SA algorithm in nesting problem. In the aspect of SA: firstly the basic principle, technical characters and procedure were described, then according to the specialty of nesting algorithm, the implementation and key parameters were designed, such as encode and decode for nesting pattern, design for domain function and initial temperature, design for temperature decreasing rate, and experiments on benchmark datasets were conducted to compare the new algorithms with the existing best know nesting algorithms (dataset 5-1~5-2). In the aspect of GA: individual encode and decode, fitness calculation, the selection of individuals, crossover and mutation operations and the probability for crossover and mutation were researched. At the end, comparing experiments on benchmark datasets were conducted (dataset 5-3~5-5). The experiments results show that the runtime of intelligent algorithm is longer than that of heuristic algorithms, but intelligent algorithms achieved more effective nesting pattern than heuristic algorithms.更多还原