改进三维不规则排样构造算法

刘 虓，徐 磊，陈超核，刘嘉敏

(1.华南理工大学 土木与交通学院，广东 广州 510640；2.沈阳工业大学 信息科学与工程学院，辽宁 沈阳 110870)

0 引言

三维排样是在三维空间将多个零件在容器内进行优化布排的过程[1-5]，在船舶/航天器舱室布局设计、集装箱装运、激光烧结等领域有广泛应用。排样问题作为一类典型的优化问题，其 “设计变量”为零件排样次序；“目标函数”为零件在容器内的排布密度；“约束条件”为零件之间以及零件与容器之间不重叠/冲突。将零件依次排入容器并计算排布密度的算法称为排样“构造算法”(constructive algorithm)，因此构造算法也可看作目标函数的“求解器”。规则三维排样算法已较成熟[5]，不规则排样算法则处于前沿阶段[1-4]。三维不规则零件几何要素和运动自由度较多，相应的构造算法计算效率很低，已经成为三维不规则排样的瓶颈，有必要对其进行更广泛和深入的研究。

构造算法的核心包括零件可行域构建和零件重叠检测两个。临界多边形(No Fit Polygon, NFP)是构建二维排样[6]可行域和避免零件重叠的通行工具[1]，但NFP的生成算法比较耗时，如果将NFP推广到三维，所谓“临界多面体”的生成算法将更加复杂。此外，NFP在考虑零件旋转时会进一步增加算法耗时。因此，很多学者另辟蹊径，提出两类方法：①“像素”方法，Stoyan等[7]将零件分解成多个长方体，将两个零件之间的距离计算在两组长方体之间展开；②“矢量”方法，基于最小势能原理的三维排样启发式算法(Heuristic Algorithm based on the principle of minimum total Potential Energy for 3D packing problems, HAPE3D)[8-9]采用多面体表达零件，将重叠检测归结于“点与线”以及“线与线”的几何关系判断。……