空白矩形填充和邻域搜索结合的矩形件排样优化算法

针对矩形件排样问题,提出一种新的空白矩形填充算法和邻域搜索算法相结合的混合优化算法。首先,设计空白矩形填充算法时,提出了消除多余空白矩形的方法,以减小计算时间复杂度。其次,利用邻域搜索算法优化矩形件排放顺序,通过挖掘矩形件排样的问题特征,设计了受限距离的交叉和插入两种邻域算子,并提出了特殊算子执行点选择策略。然后,设计了基于两种邻域算子交替迭代的邻域搜索算法。最后,对文献中的21个经典案例进行试验计算,4个案例的排样利用率达到了100%,绝大多数案例的排样利用率超过了99%,最小排样利用率超过了98%。将其他常用算法和文献中算法进行比较,验证了本文算法的有效性。同时,对某建材加工企业所提供的8个实际案例进行试验计算,所得排样利用率与理想最优排样利用率的平均差为1.7%,说明了本文算法的实用性。

Optimal algorithm on rectangular workpiece layout combining blank rectangle filling and neighborhood search algorithms

For the problem of rectangular workpiece layout,a new hybrid optimization algorithm was proposed by combining blank rectangle filling and neighborhood search algorithms. Firstly,when the blank rectangle filling algorithm was designed,a method to eliminate extra blank rectangles was proposed to reduce the computation time complexity. Secondly,two kinds of neighborhood operators such as crossover and insertion of the limited distance are designed when the layout order of rectangular workpieces was optimized by using neighborhood search algorithm according to the characteristics of the problem. In addition,the execution point selection strategy of special operators was proposed. Then,a neighborhood search algorithm was implemented based on alternating iteration of two neighborhood operators.Finally,the experiment calculations of twenty-one classical cases in literature show that the layout utilization rate of four cases is up to100%,the layout utilization rate of most cases exceeds 99%,and the minimum layout utilization rate exceeds 98%. Compared with other algorithms commonly used in the literature,the effectiveness of the proposed algorithm was verified. At the same time,eight actual cases provided by a building materials processing enterprise were tested and calculated,and the average difference between the obtained layout utilization rate and the ideal optimal layout utilization rate is 1. 7% to indicate the practicability of the algorithm in this paper.