求解一刀切式二维矩形Strip Packing问题的混合搜索算法

• 作者: 尹爱华 王磊 郭超
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 矩形条带装箱 拟人 启发式 全局优化 一刀切
• 年，卷（期）: 2020,（z2）
• 所属期刊栏目: 人工智能
• 页码范围: 119-125
• 页数: 7页
• 分类号: TP301
• 语种: 中文
• DOI: 10.11896/jsjkx.200200016

摘要

一刀切式二维矩形Strip Packing问题是一种NP难度问题.问题的实用背景是诸如玻璃板材切割、集成电路布局等工业生产中,需要优化布局和切割方案以提高利用率.总体框架是首先针对二维矩形Packing问题提出混合搜索算法,然后采用跳跃式查找与折半查找相结合的方式,将混合搜索算法用于求解二维矩形Strip Packing问题.从拟人途径提出占角、动作空间、极高度、组合拼凑等基本定义以及基本算法.以基本算法为基础,混合搜索算法分为3个阶段:第一阶段生成初始解.第二阶段调用邻域搜索子程序对矩形块的优先级进行调整.当邻域搜索遇到局部最优解时,采用基于随机扰动的跳坑策略子程序跳出局部最优陷阱,并在新区域继续搜索.第三阶段调用优美度枚举子程序对占角动作的选择进行优化.混合搜索算法计算了2组共91个benchmark实例,并将其计算结果与SPTRS算法进行了比较.SPTRS算法计算结果的平均相对误差是4.26％,混合搜索算法计算结果的平均相对误差是3.83％.因此,混合搜索算法是一种求解一刀切式二维矩形Strip Packing问题的高效启发式算法.