基于启发式的二维不规则多规格板材排样问题研究

A Heuristic for the Two-dimensional Multiple Bin Size Irregular Bin Packing Problem

二维不规则板材排样在工业生产中的应用十分广泛,属于空间布局优化问题。目前该方向的研究主要考虑单规格板材,缺乏在多规格板材上排样不规则零件的研究。提出了一种启发式算法求解二维不规则多规格板材排样问题,该问题需要把不规则零件打包到不同尺寸的板材中,使得所选板材的面积总和最小。为了解决该问题,采用回溯算法和剪枝策略生成板材组合,通过二分搜索策略选定并切换板材组合。对于给定板材组合,提出了基于重叠移除的排样算法,首先通过首次适应下降策略和左下算法尝试把每个零件放置在板材里面,假若还有零件未能放置在板材里面,则运用插入算法把这些零件插入到板材中重叠最小的位置,再通过邻域搜索和重叠移除算法最小化重叠值,从而求得可行解。对多规格板材的算例进行测试,实验结果表明,该启发式算法可有效解决二维不规则多规格板材排样问题。

Two-dimensional irregular bin packing is widely used in industrial production,which belongs to spatial layout optimization problem.At present,the research in the direction mainly considers the single-size bins,and there is a lack of research on packing irregular pieces on multiple-size bins.A heuristic is proposed to solve the two-dimensional multiple bin size irregular bin packing problem.The problem requires packing irregular pieces into bins of different sizes so that the total area of the selected bins is minimized.In order to solve the problem,the heuristic uses backtracking algorithm and pruning strategy to generate bin combinations,and then selects and switches bin combinations by binary search strategy.For a given bin combination,a packing algorithm based on overlap removal is proposed.First,try to place each piece in the bin through the first fit decreasing strategy and the bottom-left algorithm.If there are still pieces that cannot be placed in the bin,then use the insertion algorithm to insert these pieces into the position of the minimum overlap in the bin.Then the feasible solution is obtained by minimizing the overlap value through local search and overlap removal algorithm.The instances of the two-dimensional multiple bin size irregular bin packing problem are tested,and the experimental results show that the proposed heuristic can effectively solve the the twodimensional multiple bin size irregular bin packing problem.