| 求解三维装箱问题的多层树搜索算法 |
| |
| 引用本文： | 刘胜, 沈大勇, 商秀芹, 赵红霞, 董西松, 王飞跃. 求解三维装箱问题的多层树搜索算法. 自动化学报, 2020, 46(6): 1178−1187 doi: 10.16383/j.aas.c180795 |
| |
| 作者姓名： | 刘胜 沈大勇 商秀芹 赵红霞 董西松 王飞跃 |
| |
| 作者单位： | 1.中国科学院自动化研究所复杂系统管理与控制国家重点实验室 北京 100190;2.中国科学院自动化研究所北京市智能化技术与系统工程技术研究中心 北京 100190;3.青岛智能产业技术研究院 青岛 266109;4.国防科技大学系统工程学院 长沙 410073 |
| |
| 基金项目： | 国家重点研究发展计划基金(2018YFB1004803), 国家自然科学基金(61773381, 61773382, 61533019), 湖南省科技重大专项基金(2018GK1040), 广东省科技厅项目基金(2017B090912001) 资助 |
| |
| 摘 要： | 提出了一种求解三维装箱问题的多层树搜索算法, 该算法采用箱子–片–条–层–实体的顺序生成装载方案, 装载方案由实体表示. 该算法由3层搜索树构成. 第1层为三叉树, 每个树节点的3个分叉分别对应向实体中填入XY面平行层、XZ面平行层、YZ面平行层; 第2层为二叉树, 每个树节点的两个分叉分别对应向层内装载两个相互垂直的最优条; 第3层为四叉树, 用于将同种的多个箱子生成片. 在同时满足摆放方向约束和完全支撑约束的前提下, 该算法求解BR12~BR15得到的填充率高于现有装箱算法.
|
| 关 键 词： | 三维装箱 墙构造 水平层构造 多层树 |
| 收稿时间： | 2018-11-29 |
A Multi-level Tree Search Algorithm for Three Dimensional Container Loading Problem |
| |
| 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 |
| |
| Authors: | LIU Sheng SHEN Da-Yong SHANG Xiu-Qin ZHAO Hong-Xia DONG Xi-Song WANG Fei-Yue |
| |
| Affiliation: | 1. State Key Laboratory for Management and Control of Complex Systems, Institute of Automation, Chinese Academy of Sciences, Beijing 100190;2. Beijing Engineering Research Center of Intelligent Systems and Technology, Institute of Automation, Chinese Academy of Sciences, Beijing 100190;3. Qingdao Academy of Intelligent Industries, Qingdao 266109;4. College of Systems Engineering, National University of Defense Technology, Changsha 410073 |
| |
| Abstract: | This paper presents a multiple-level tree search algorithm for the three dimensional container loading problem. This algorithm generates a loading plan in the box-piece-strip-layer-entity sequence. Hereby an entity denotes a loading plan. This algorithm consists of three levels of search tree. The first level is a ternary tree. In this tree the three branches of each node correspond to filling three layers which are parallel to the XY-plane, the XZ-plane, and the YZ-plane, respectively. The second level is a binary tree. In this tree the two branches of each node correspond to loading two orthogonal strips into a layer, respectively. The third level is a quad tree to search the best piece. In this tree the boxes of the same kind are integrated into a piece. The proposed algorithm achieves better filling rate for BR12~BR15 than the existing algorithms when the orientation constraint and the full-support constraint are satisfied. |
| |
| Keywords: | Three-dimensional container loading wall building horizontal layer building multi-level tree search |
|
| 点击此处可从《自动化学报》浏览原始摘要信息 |
|
点击此处可从《自动化学报》下载全文 |
|
