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

摘要：

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

关键词：矩形条带装箱、拟人、启发式、全局优化、一刀切

所属期刊栏目：47

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61862027,71701156

在线出版日期：2020-12-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：119-125