基于集束搜索的二维矩形排样问题求解算法

The Algorithm of Two-dimensional Rectangle Layout Problem Based on Backtracking

降低成本、提高材料利用率是生产商提高收益的重要方式,所以如何将板材切割出更多有效目标板件是一个值得探讨的问题。为了得到更高效的二维矩形排样算法,通过以贴边度为放置动作判断核心,并以集束搜索的方式进行搜索求解。实验使用packing问题常用的C21算例组进行演算,并与基本算法、GRASP算法和TABU算法进行对比。这3种基本算法平均利用率为97.39%、98.50%、99.53%,而使用集束搜索策略后平均利用率上升到了99.80%。整体利用率比基本算法平均利用率上涨2.41%,比GRASP算法平均利用率上涨1.3%,比TABU算法平均利用率上涨0.27%。基本算法在使用集束搜索策略后,反超GRASP算法和TABU算法,使平均利用率进一步提升。

It is an important way for producers to reduce cost and improve material utilization rate to increase profit.Therefore,how to cut out more effective target plates is a question worth discussion.In order to obtain a more efficient two-dimensional rectangular layout algorithm,the paper designs a method to search and solve the problem by taking the welt as the core of placement action judgment and using the method of cluster search.In the experiment,C21 example set commonly used in packing problem was used for calculation, and it was compared with the basic algorithm,GRASP algorithm and TABU algorithm.The average utilization rate of the 3 algorithm are 97.39%,98.50% and 99.53%.Overall utilization rate is 2.41% higher compared with the average utilization rate of basic algorithm,1.3% compared with the average utilization rate of GRASP algorithm,and 0.27% compared with the average utilization rate of TABU algorithm.After using the cluster search strategy,the average utilization ratio of the basic algorithm has been improved,and the GRASP algorithm and TABU algorithm have been surpassed.