Abstract: The two-dimensional irregular strip packing problem is widely encountered in the manufacturing industry such as textiles,shipbuilding,and leather goods.Traditional packing methods often have high computational complexity and leave room for further optimization of nesting efficiency.To improve packing efficiency and utilization,a Density-Guided Iterative Search Algorithm（DGISA）was proposed.The solution space was reduced to discretized placement positions.Then,local search was performed based on layout density and placement density.The optimal placement position for polygonal parts was determined with adaptive update weight during the search process.Comparative experiments with three typical nesting methods on 14 internationally recognized nesting cases demonstrated that the proposed method achieved optimal nesting efficiency in 10 cases,validating its effectiveness and superiority.

Key words: irregular nesting problem, minimize overlapping subproblems, density-guidance, guided iterative search

摘要： 二维不规则排样问题在纺织、造船和皮革等制造业领域广泛存在。传统的排样方法计算时间复杂度高,排样利用率还有较大优化空间。为进一步提高排样利用率,加快排样速度,提出一种密集度驱动的迭代搜索二维不规则排样算法（DGISA）。首先,通过离散化摆放位置缩小解空间,然后借助布局密集度和摆放密集度进行局部空间搜索,搜索过程中通过自适应更新重叠惩罚权重确定多边形零件的最佳摆放位置。与3种典型的排样方法在国际通用排样的14个用例的对比实验表明,DGISA在10个用例达到了最优排样利用率,验证了方法的有效性和先进性。

关键词: 不规则排样问题, 最小化重叠子问题, 密集度驱动, 引导式迭代搜索