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

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