求解三维装箱问题的多层树搜索算法

• 作者: 刘胜 商秀芹 沈大勇 王飞跃 董西松 赵红霞
• 来源期刊: 自动化学报
• 关键词: 三维装箱 墙构造 水平层构造 多层树
• 年，卷（期）: 2020,（6）
• 所属期刊栏目: 论文与报告
• 页码范围: 1178-1187
• 页数: 10页
• 字数: 9079字
• 语种: 中文
• DOI: 10.16383/j.aas.c180795

摘要

提出了一种求解三维装箱问题的多层树搜索算法,该算法采用箱子-片-条-层-实体的顺序生成装载方案,装载方案由实体表示.该算法由3层搜索树构成.第1层为三叉树,每个树节点的3个分叉分别对应向实体中填入XY面平行层、XZ面平行层、YZ面平行层;第2层为二叉树,每个树节点的两个分叉分别对应向层内装载两个相互垂直的最优条;第3层为四叉树,用于将同种的多个箱子生成片.在同时满足摆放方向约束和完全支撑约束的前提下,该算法求解BR12～BR15得到的填充率高于现有装箱算法.