引用本文

刘胜, 沈大勇, 商秀芹, 赵红霞, 董西松, 王飞跃. 求解三维装箱问题的多层树搜索算法. 自动化学报, 2020, 46(6): 1178−1187 doi: 10.16383/j.aas.c180795

Liu Sheng, Shen Da-Yong, Shang Xiu-Qin, Zhao Hong-Xia, Dong Xi-Song, Wang Fei-Yue. A multi-level tree search algorithm for three dimensional container loading problem. Acta Automatica Sinica, 2020, 46(6): 1178−1187 doi: 10.16383/j.aas.c180795

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180795

关键词

三维装箱，墙构造，水平层构造，多层树 

摘要

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

文章导读

三维装箱问题(Three-dimensional container loading problem, 3D-CLP)研究如何通过优化货物摆放来提高货箱空间利用率, 应用三维装箱算法不仅可以降低货物运输成本, 还可以减少运输工具在运输过程中的碳排放, 具有很好的社会经济效益.

三维装箱问题属于切割与布局问题(Cutting and packing, CP)[1], 相关研究可以追溯到20世纪80年代[2]. 按照文献[3]的分类命名法, 三维装箱问题可以归为代号为3/V/I或3/B/O的CP问题. 按照文献[4]建议的分类命名法, 三维装箱问题归为三维单一背包问题(Three-dimensional single knapsack problem, 3D-SKP)或三维单一大物体摆放问题(Three-dimensional single large object placement problem, 3DSLOPP). 依据文献[5]中定义, 本文研究的是考虑摆放方向约束(C1)和完全支撑约束(C2)的三维装箱问题. 在目前研究三维装箱问题的文献中, 这也是考虑最广泛的两个约束.

本文结构如下: 第1节简要回顾三维装箱问题的研究进展; 第2节详细叙述本文提出的三维装箱算法的实现步骤; 第3节给出本文算法运行通用算例的结果, 并将结果与目前最新算法的运行结果相比较. 最后第4节总结了本文算法的特点, 并展望了下一步的研究思路.

图 1  坐标系和容器、箱子尺寸和摆放方向示意图

图 2  片的示意图

图 3  条的示意图

本文提出了三维装箱问题的多层树搜索算法, 采用墙构造法和水平层构造法相结合的装载方案构造方式. 该算法包括3层搜索树, 第1层搜索树也是最顶层搜索树, 用于搜索最优装载方案, 该树为三叉树, 每个树节点的三个分叉分别对应生成平行于XY面的层、生成平行于XZ面的层、生成平行于YZ面的层; 第2层搜索树用于为第1层树的每个节点搜索最优的层, 该树为二叉树, 每个树节点的两个分叉分别对应生成两个相互垂直的条; 第3层搜索树用于将每一类箱子生成片, 该树为四叉树, 由于生成片时限定空间比较小, 同类型的箱子数量相对小, 四叉树搜索速度可以接受. 本文提出的多层树搜索算法搜索量比较大, 难以在可接受时间内完成对整个搜索树的遍历, 为此采用了加速策略, 并且限定算法的运行时间. 利用通用算例的运行结果显示本文算法具有一定的竞争力. 我们在运行该算法时也发现一些问题, 例如当箱子体积相对于容器容积越小时, 树搜索深度就越深, 计算时间就越长, 有时甚至不能在限定时间内生成一个完整的装载方案, 因此本算法还有进一步改进的余地.

作者简介

刘胜

中国科学院自动化研究所复杂系统管理与控制国家重点实验室副研究员. 主要研究方向为组合优化, 智能物流, 智能制造.E-mail: sheng.liu@ia.ac.cn

沈大勇

2011年获国防科技大学系统工程学院系统工程学士学位, 2013年获国防科技大学系统工程硕士学位, 2018年获国防科技大学管理科学与工程博士学位. 主要研究方向为智能调度, 人工智能算法和并行社会系统. 本文通信作者.E-mail: dayong.shen@nudt.edu.cn

商秀芹

中国科学院自动化研究所复杂系统管理与控制国家重点实验室副研究员. 2010年获浙江大学控制理论与控制工程博士学位. 主要研究方向为智能制造, 工业过程建模与优化.E-mail: xiuqin.shang@ia.ac.cn

赵红霞

中国科学院自动化研究所复杂系统管理与控制国家重点实验室助理研究员. 主要研究方向为智能交通系统.E-mail: hongxia.zhao@ia.ac.cn

董西松

中国科学院自动化研究所复杂系统管理与控制国家重点实验室副研究员. 2007年获北京科技大学控制理论与控制工程博士学位. 主要研究方向为复杂系统的建模与控制, 智能交通系统.E-mail: xisong.dong@ia.ac.cn

王飞跃

中国科学院自动化研究所复杂系统管理与控制国家重点实验室主任, 国防科技大学军事计算实验与平行系统技术研究中心主任, 中国科学院大学中国经济与社会安全研究中心主任, 青岛智能产业技术研究院院长. 主要研究方向为平行系统的方法与应用, 社会计算, 平行智能以及知识自动化. E-mail: feiyue.wang@ia.ac.cn