基于骨架线引导的复杂不规则轮廓自动排样研究

Complex irregular contour packing problems affect material utilization and production efficiency. The packing strategy and the packing sequence play important roles in packing process. The packing contours are rotated by equal angle-interval in existing packing algorithms and the best packing attitudes are easy to miss and affect the packing quality. The skeleton of an irregular contour and the contour are one-to-one correspondence and the topology connectivity remains the same. A skeleton segment means a contour characteristic. Complex irregular contour automatic packing using skeleton guiding method is proposed to research in this program. The convex and non-convex characteristics are paired since the rotated angle-intervals are determined by skeleton characteristics and the packing filling rate is improved. The proposed packing method can be applied to solve all 2D packing problems since skeletons can be calculated for all 2D contours. Genetic Algorithm and Hill-climbing Algorithm are two important intelligent optimization algorithms. Genetic Algorithm has a powerful ability of global searching and a weak local searching ability. Hill-climbing Algorithm has a powerful ability of local searching. But the algorithm is easy to converge to local optimum. A Hill-climbing Genetic Algorithm is proposed to optimize the packing sequence by combining the Genetic Algorithm and the Hill-climbing Algorithm. The solution region is determined by Genetic Algorithm firstly and then the optimum is gained by searching the solution region with Hill-climbing Algorithm. The material utilization and production efficiency can be raised since the packing quality and efficiency can be improved by using the proposed packing method and the Hill-climbing Genetic Algorithm.

复杂不规则轮廓排样直接影响材料利用率和生产效率。排样定位规则和排样顺序是影响排样质量的两个重要因素。现有的不规则轮廓排样定位规则在选择排样姿态时每次旋转固定的角度间隔，容易错过最佳排样姿态，导致排样质量和效率下降。不规则轮廓的骨架线与轮廓具有一一对应关系且保留原轮廓的拓扑连通性，每段骨架线表征轮廓的一个特征，受此启发，本项目研究基于骨架线引导的排样定位规则。排样时根据轮廓的骨架线特征确定排样位置，可以实现轮廓互补特征组合，减小缝隙与孔洞，从而提高排样填充率。二维轮廓通过骨架线描述，排样算法不受排样轮廓形态限制。本项目结合遗传算法和爬山算法的优点提出了爬山遗传算法优化排样顺序，该方法利用爬山算法局部搜索能力强的优点克服了传统遗传算法确定最优解区间后局部搜索能力不足的缺点。项目研究基于骨架线引导的排样方法和基于爬山遗传算法的排样顺序优化方法可以改善排样质量和效率，提高材料利用率和生产效率。

二维不规则排样问题广泛存在于各类制造业中，如造船、航空航天、服装制造及生物医疗等。高效的二维不规则排样方法能够提高工艺自动化程度，提升材料利用率同时降低生产成本。对于二维不规则排样问题的研究具有重要的科学意义和实用价值。本项目从轮廓几何特征相互匹配的角度出发，对二维不规则排样问题展开研究。首先，本项目提出了基于骨架线引导的二维不规则轮廓定位算法，避免了在排样过程中通过分度旋转寻找最佳摆放位置，降低了计算时间开销同时提高了排样密度。其次，本项目将爬山遗传算法用于优化形状入排顺序，进一步提高了排样密度。最后，本项目结合定位及顺序优化算法，开发了一款二维不规则排样系统，为本项目所提出方法的实际应用提供了支撑。为了验证本项目提出的二维不规则轮廓排样方法，分别在卡通切片数据集和口腔修复体数据集上进行了多组实验。实验结果表明，本项目所提出的二维不规则排样方法可行有效，同文献中已有的方法相比，所提出的方法能够在更短的时间内获得更好的排样结果。本项目的研究成果促进了二维不规则排样领域的理论发展，为求解二维不规则排样问题提供了新的思路，具有重要的科学意义。同时，本项目所提出的方法可以被直接应用于现实生产中，具有重要的实用价值。