本文研究的二维图形排样问题,属于二维空间布局优化的范畴,目的是把待排零件放置于平面板材上,使得材料利用率达到最大化,约束条件如下:(1)零件位于板材内部;(2)零件与零件之间互不重叠;(3)满足实际生产过程中的工艺要求。排样问题对船舶制造、服装加工、模具生产等行业有重要意义。本文对二维不规则零件排样问题进行了深入的理论分析,对排样过程中的关键性问题提出相应的改进算法,包括改进基于凸化分割的临界多边形求解算法,二维布尔运算中特殊情况的考虑,不规则零件定位策略和定位评估标准的选择,以及智能优化算法如何适用于排样问题等等,设计切实可行的解决方案。主要的研究方向和创新点如下:临界多边形算法研究:改进基于凸化分割的临界多边形求解算法,在传统布尔并运算的基础上,针对排样过程中可能遇到的特殊情况,如凹槽现象、退化现象及重叠点问题,改进原有的算法,最终完整地解决了二维布尔运算在合成多边形,求解临界多边形过程中可能遇到的问题。零件的定位策略研究:提出了一种基于临界多边形和内靠接矩形的定位策略,该算法在定位搜索以及信息重用方面有着无可比拟的优势,可以有效解决排样过程中可能出现的孔洞问题。排样过程中的临界多边形信息可以重用,提高算法执行效率。零件的定位评估标准研究:针对传统的BL标准的不足,提出一种新的定位评估标准,即LOR标准,在排样过程中不仅仅考虑零件尽量做到最左最下,还综合考虑了零件与零件之间的契合度,有助于零件之间形成互补,提高板材利用率。智能优化算法的研究:对传统的智能优化算法(遗传算法、模拟退火算法、蚁群算法)的局限性和缺陷作出分析,并提出一种基于有限分支树搜索方法的二维图形排样算法。根据一定的启发式规则,划分有效搜索区,人为控制搜索方向和搜索范围。有限分支树搜索排样算法综合考虑智能优化算法的全局观和启发式排样算法的优点,既考虑人为的排样规则,又避免陷入局部最优,应用于二维图形排样可以获得较好的板材利用率。