.png){kind=icon}
返回
A backtracking heuristic algorithm for two-dimensional strip packing with rotation
.png){kind=icon}
OA
AI
DOI：10.1177/00368504241301530.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
针对带有旋转且无 Guillotine 切割的二维矩形条带装载问题（具有广泛应用），提出了一种回溯启发式算法（BHA）。该算法采用改进的适应度策略，在特定高度的条带上选择适应度最优的矩形进行装载。随后，在更高高度处反复使用回溯构造启发式方法，直至所有矩形均被装载。接着，通过多起点改进程序，以不同矩形作为首个矩形（其余矩形顺序保持不变）来寻找最优解。最后，为进一步扩大解的范围，应用了一种基于随机矩形序列（首个矩形不变）的简单随机局部搜索程序来搜索最优解。BHA 仅包含两个参数，具有简单高效的特点。针对不同规模（从 10 个到 75,032 个矩形）的基准问题（包括零浪费实例和非零浪费实例）的计算结果表明：(1) 虽然算法具有不确定性，但每次运行后的结果差异极小；(2) 所提算法在整体上优于大多数对比算法，尤其在包含 1000 个以上矩形的大规模实例中表现突出，这一结论经统计分析进一步验证，对金属切割等大规模工业生产具有重大意义。
Keyword:
Packing
backtracking heuristic
multi-start improvement
local search
large-scale instance
期刊
IF:
7.2
论文数:
768
被引数:
2.0K
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容