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

• 作者: 饶昊
• 来源期刊: 软件导刊
• 学科: 工学
• 关键词: NP难度 Packing问题 集束搜索
• 年，卷（期）: 2019,（5）
• 所属期刊栏目: 算法与语言
• 页码范围: 84-88
• 页数: 5页
• 分类号: TP312
• 字数: 3350字
• 语种: 中文
• DOI: 10.11907/rjdk.191280

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	饶昊	江西财经大学软件与物联网工程学院	2	3	1.0	1.0