本文研究二维排样问题。二维排样是一个平面布局优化问题,目的是在平面板材上尽可能多的布置不同形状的零件,并满足以下约束条件:(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)。实验表明智能排样算法的计算时间较长,但是具有较强的全局优化能力,能够取得比启发式算法更好的排样效果。