摘要
提出了一种求解三维装箱问题的多层树搜索算法,该算法采用箱子–片–条–层–实体的顺序生成装载方案,装载方案由实体表示.该算法由3层搜索树构成.第1层为三叉树,每个树节点的3个分叉分别对应向实体中填入XY面平行层、XZ面平行层、YZ面平行层;第2层为二叉树,每个树节点的两个分叉分别对应向层内装载两个相互垂直的最优条;第3层为四叉树,用于将同种的多个箱子生成片.在同时满足摆放方向约束和完全支撑约束的前提下,该算法求解BR12~BR15得到的填充率高于现有装箱算法.
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 XZplane,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.
作者
刘胜
沈大勇
商秀芹
赵红霞
董西松
王飞跃
LIU Sheng;SHEN Da-Yong;SHANG Xiu-Qin;ZHAO Hong-Xia;DONG Xi-Song;WANG Fei-Yue(State Key Laboratory for Management and Control of Complex Systems,Institute of Automation,Chinese Academy of Sciences,Beijing 100190;Beijing Engineering Research Center of Intelligent Systems and Technology,Institute of Automation,Chinese Academy of Sciences,Beijing 100190;Qingdao Academy of Intelligent Industries,Qingdao 266109;College of Systems Engineering,National University of Defense Technology,Changsha 410073)
出处
《自动化学报》
EI
CSCD
北大核心
2020年第6期1178-1187,共10页
Acta Automatica Sinica
基金
国家重点研究发展计划基金(2018YFB1004803)
国家自然科学基金(61773381,61773382,61533019)
湖南省科技重大专项基金(2018GK1040)
广东省科技厅项目基金(2017B090912001)资助。
关键词
三维装箱
墙构造
水平层构造
多层树
Three-dimensional container loading
wall building
horizontal layer building
multi-level tree search