零件的排样又称下料,广泛地存在各行各业中,排样方案的好坏直接关系到零件所消耗的材料量,提高排样中板材的利用率能够有效地降低生产成本、给工厂带来直接可观的利润。随着工业自动化的发展和计算机技术的进步,研究者们对排样问题的优化研究工作越来越多,针对各行各业中具体排样问题提出了许多优化算法。本文主要是对船体建造板材套料排样优化展开研究。首先将矢量格式描述的船体零件简化为多边形,再进行矩形包络以及使用k-means法根据船体零件特征对图形进行聚类分析,最后根据聚类结果进行零件之间的组合矩形包络,并对零件的孔洞进行填补,以及考虑船体的边缘加工对排样的影响将零件几何图形进行扩展,做好排样前的准备工作。使用剩余矩形算法对包络好的船体零件进行排样,并对算法提出改进:添加了零件在选择剩余矩形时的评价原则。介绍了一种可以基于提取多边形线族并按角度计算空间点到线段的位移方法来实现平面多边形的快速内外靠接算法,并将其应用到零件的组合包络和排样算法中。解决了基于固定排序和旋转方式的零件排样的局部寻优问题。最后,在结合靠接算法的剩余矩形排样算法中加入遗传算法,根据船体零件排样的具体问题进行遗传算法设计,以计算出最优的零件排入顺序及旋转方式。解决了在零件所有排序和旋转方式中排样的全局寻优问题。