Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle

The nesting problem involves arranging pieces on a plate to maximize use of material. A new scheme for 2D ir- regular-shaped nesting problem is proposed. The new scheme is based on the NFP (No Fit Polygon) algorithm and a new placement principle for pieces. The novel placement principle is to place a piece to the position with lowest gravity center based on NFP. In addition, genetic algorithm (GA) is adopted to find an efficient nesting sequence. The proposed scheme can deal with pieces with arbitrary rotation and containing region with holes, and achieves competitive results in experiment on benchmark datasets.

基于轨迹线改进的临界多边形算法

在异形件的下料排样问题中,最为困难的就是求解裁片在板料中的位置以保证材料较高的利用率,算法复杂度随着料片数量和料片轮廓复杂度的增加迅速上升。临界多边形算法是计算异形件之间靠接位置和重叠关系的一种基础性几何工具,临界多边形算法的性能与下料排样算法效率密切相关。本文在基于轨迹线的求解临界多边形算法基础上,提出一种求解临界多边形(NFP)的改进算法。该算法有效地将移动碰撞算法和轨迹线算法相结合,充分发挥两类算法各自的优点,提高了临界多边形求解的计算速度。仿真实例验证了改进方法的正确性和有效性。

基于重心NFP的二维不规则形状排样算法

提出了一种基于重心NFP的二维不规则多边形排样算法,算法主要包括临界多边形计算和排样定位选优等内容。该算法以多边形来表示板材和待排零件,通过求解临界多边形NFP来得到多边形之间的所有靠接(排放)位置。为了在NFP中进一步得到优化的靠接位置,在NFP的基础上提出了重心NFP的概念,通过选择重心NFP中的最低重心位置来确定零件的排放位置。在零件的排样次序算法上,提出了顺序递归排样算法和遗传算法,以降低排样过程中形成的空腔所造成的浪费。该算法可处理板材和零件均为不规则形状的排样问题,允许零件在全角度范围内进行旋转,并可处理板材内部带孔洞或者边界形成空腔等特殊情况。

基于NFP算法下印前拼版设计及成本控制研究

通过NFP核心算法进行拼版软件组版方式设计,解决拼版环节中无缝拼接问题,从而通过软件的拓展功能,对纸张费用、印刷各环节费用、模切糊盒费用以及总成本费用进行控制,实现在事前进行成本管理,选择合适的生产工艺流程,为企业在实际管理抉择中提供决策参考,并适时掌控企业的成本管理,真正实现及时管理。

一种基于NFP非凸几何的船舶中间产品堆场布局优化方法

针对现代船舶制造过程中堆场空间资源浪费和布局不合理的现状,提出了一种基于NFP(no-fit polygon)非凸几何的船舶中间产品堆场布局优化方法.该方法以不规则多边形来表示结构件轮廓,将非凸多边形分割处理为简单凸多边形,用遗传算法对结构件在堆场中的排序进行优化.通过计算NFP实现船舶中间产品堆场的布局优化,解决非凸几何结构件在堆场中的布局问题.试验结果表明,该方法可以有效提高船舶中间产品堆场的空间资源利用率.

二维不规则图形排料CAD系统的设计

采用轨迹线算法、自适应最低重心规则和遗传算法,解决了不规则图形的计算机辅助排料问题。提出采用轨迹线求解临界多边形实现快速的多边形靠接,根据自适应最低重心NFP的排样放置原则,配合改进后快速收敛的遗传算法,设计了一套自动并支持实时交互的排料CAD系统,给出了排料结果和对比,取得了良好的排料结果和应用。系统还提供零件及板材库的管理功能。

基于BL-NFP神经网络算法的二维不规则钣金零件排样

针对传统工业生产中二维不规则钣金零件的利用率不高、计算时间较长的问题,提出了以能量函数为载体的BL-NFP(Bottom Left-No Fit Polygon)神经网络算法。该算法是将BL(Bottom-Left)定位算法和临界多边形(No-Fit Polygon,NFP)几何特性相结合,同时模拟了钣金零件的排样过程。并采取对待排入零件优先进行面积大小核算、再排入待排物体的方式,并利用Matlab对算法的输出数据和前人所列出的数据结果进行了测试对比。结果表明:BL定位算法能够合理地计算出零件的排入位置,NFP能够有效地解决不规则零件排样利用率小的问题,神经网络算法则能够有效地提高求解速度。针对二维不规则钣金零件的排样问题,与传统神经网络算法相比较,采用该算法缩短了钣金零件下料机器计算最优解40%的时间,并提高了约8%的钣金材料利用率。

基于粒子群算法的二维不规则排样

针对工业生产中常见的二维不规则排样问题,提出运用粒子群算法求解的方法。将BL算法和NFP算法结合,作为排样定位策略;对工件的入排顺序和入排角度进行编码,进行粒子群算法优化求解,并通过交叉替代传统的插值改进粒子位置更新过程,满足排样的离散问题求解;通过添加粒子的变异过程,避免陷入局部最优解。算例排样结果验证了该算法的有效性。