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

刘胜; 沈大勇; 商秀芹; 赵红霞; 董西松; 王飞跃

doi:10.16383/j.aas.c180795

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

doi: 10.16383/j.aas.c180795

刘胜^{1, 2, 3,},
沈大勇^4,,
商秀芹^{1, 2, 3,},
赵红霞^{1, 2, 3,},
董西松^{1, 2, 3,},
王飞跃^{1, 2, 3,}

1.
中国科学院自动化研究所复杂系统管理与控制国家重点实验室北京 100190
2.
中国科学院自动化研究所北京市智能化技术与系统工程技术研究中心北京 100190
3.
青岛智能产业技术研究院青岛 266109
4.
国防科技大学系统工程学院长沙 410073

基金项目: 国家重点研究发展计划基金(2018YFB1004803), 国家自然科学基金(61773381, 61773382, 61533019), 湖南省科技重大专项基金(2018GK1040), 广东省科技厅项目基金(2017B090912001) 资助

详细信息

作者简介:
刘胜：中国科学院自动化研究所复杂系统管理与控制国家重点实验室副研究员. 主要研究方向为组合优化, 智能物流, 智能制造.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

中图分类号: TP301
计量
- 文章访问数: 2165
- HTML全文浏览量: 520
- PDF下载量: 250
- 被引次数: 0
出版历程
- 收稿日期: 2018-11-29
- 网络出版日期: 2020-01-21
- 刊出日期: 2020-07-10

A Multi-level Tree Search Algorithm for Three Dimensional Container Loading Problem

LIU Sheng^{1, 2, 3
,},
SHEN Da-Yong^4
,,
SHANG Xiu-Qin^{1, 2, 3
,},
ZHAO Hong-Xia^{1, 2, 3
,},
DONG Xi-Song^{1, 2, 3
,},
WANG Fei-Yue^{1, 2, 3
,}

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

Funds: Supported by National Research and Development Program of China (2018YFB1004803), National Natural Science Foundation of China (61773381, 61773382, 61533019), Hunan Science and Technology Project (2018GK1040), and Guangdong Science and Technology Project (2017B090912001)

摘要

摘要: 提出了一种求解三维装箱问题的多层树搜索算法, 该算法采用箱子–片–条–层–实体的顺序生成装载方案, 装载方案由实体表示. 该算法由3层搜索树构成. 第1层为三叉树, 每个树节点的3个分叉分别对应向实体中填入XY面平行层、XZ面平行层、YZ面平行层; 第2层为二叉树, 每个树节点的两个分叉分别对应向层内装载两个相互垂直的最优条; 第3层为四叉树, 用于将同种的多个箱子生成片. 在同时满足摆放方向约束和完全支撑约束的前提下, 该算法求解BR12~BR15得到的填充率高于现有装箱算法.
- 三维装箱 /
- 墙构造 /
- 水平层构造 /
- 多层树
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.
- Three-dimensional container loading /
- wall building /
- horizontal layer building /
- multi-level tree search

HTML全文

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

Fig. 1 Examples of coordination, size, and orientations of container and box

下载: 全尺寸图片幻灯片

图 2 片的示意图

Fig. 2 Examples of pieces

下载: 全尺寸图片幻灯片

图 3 条的示意图

Fig. 3 Examples of strips

下载: 全尺寸图片幻灯片

图 4 层的示意图

Fig. 4 Examples of layers

下载: 全尺寸图片幻灯片

图 5 装载实体示意图

Fig. 5 Example of entity

下载: 全尺寸图片幻灯片

图 6 TrS_X_piece搜索树

Fig. 6 The searching tree of TrS_X_piece

下载: 全尺寸图片幻灯片

表 1 各种算法对BR1~BR7的填充率比较

Table 1 Comparison of filling rates of BR1~BR7 by various algorithms

算法	约束	填充率 (%)
算法	约束	BR1	BR2	BR3	BR4	BR5	BR6	BR7	平均
GA_GB^[16]	C1&C2	85.80	87.26	88.10	88.04	87.86	87.85	87.68	87.5
GRASP^[23]	C1	93.52	93.77	93.58	93.05	92.34	91.72	90.55	92.65
FDA^[11]	C1	92.92	93.93	93.71	93.68	93.73	93.63	93.14	93.53
HSA^[21]	C1&C2	93.81	93.94	93.86	93.57	93.22	92.72	91.99	93.30
Maximal-space^[24]	C1	93.85	94.22	94.25	94.09	93.87	93.52	92.94	93.82
A2^[12]	C1	−	−	−	−	−	−	−	−
CLTRS^[7]	C1	95.05	95.43	95.47	95.18	95.00	94.79	94.24	95.02
CLTRS^[7]	C1&C2	94.51	94.73	94.74	94.41	94.13	93.85	93.20	94.22
MLHS^[31]	C1	94.92	95.48	95.69	95.53	95.44	95.38	94.95	95.34
MLHS^[31]	C1&C2	94.49	94.89	95.20	94.94	94.78	94.55	93.95	94.69
MLTrS	C1	93.81	93.83	93.80	93.98	93.97	93.83	93.91	93.88
MLTrS	C1&C2	93.48	93.41	93.79	93.85	93.43	93.65	93.63	93.61

下载: 导出CSV

表 2 各种算法对BR8~BR15的填充率比较

Table 2 Comparison of filling rates of BR8~BR15 by various algorithms

算法	约束	填充率 (%)
算法	约束	BR8	BR9	BR10	BR11	BR12	BR13	BR14	BR15	平均
GA_GB^[15]	C1&C2	87.52	86.46	85.53	84.82	84.25	83.67	82.99	82.47	84.71
GRASP^[23]	C1	90.26	89.50	88.73	87.87	87.18	86.70	85.81	85.48	87.69
FDA^[11]	C1	92.92	92.49	92.24	91.91	91.83	91.56	91.30	91.02	91.9
HSA^[21]	C1&C2	90.56	89.7	89.06	88.18	87.73	86.97	86.16	85.44	87.98
Maximal-space^[24]	C1	91.02	90.46	89.87	89.36	89.03	88.56	88.46	88.36	89.39
A2^[12]	C1	88.41	88.14	87.9	87.88	87.92	87.92	87.82	87.73	87.97
CLTRS^[7]	C1	93.70	93.44	93.09	92.81	92.73	92.46	92.40	92.40	92.88
CLTRS^[7]	C1&C2	92.26	91.48	90.86	90.11	89.51	88.98	88.26	87.57	89.88
MLHS^[31]	C1	94.54	94.14	93.95	93.61	93.38	93.14	93.06	92.90	93.59
MLHS^[31]	C1&C2	93.12	92.48	91.83	91.23	90.59	89.99	89.34	88.54	90.89
MLTrS	C1	93.98	93.97	93.78	93.75	93.63	93.43	93.25	93.12	93.61
MLTrS	C1&C2	91.82	91.69	91.55	91.24	91.21	91.03	90.78	90.59	91.24

下载: 导出CSV

参考文献(41)

[1]	Dyckhoff H, Finke U. Cutting and Packing in Production and Distribution. Heidelberg: Physica-Verlag, 1992
[2]	George J A, Robinson D F. A heuristic for packing boxes into a container. Computers and Operations Research, 1980, 7(3): 147−156 doi: 10.1016/0305-0548(80)90001-5
[3]	Dyckhoff, H. A typology of cutting and packing problems. European Journal of Operational Research, 1990, 44(2): 145−159 doi: 10.1016/0377-2217(90)90350-K
[4]	Wäscher G, Haußner H, Schumann H. An improved typology of cutting and packing problems. European Journal of Operational Research, 2007, 183(3): 1109−1130 doi: 10.1016/j.ejor.2005.12.047
[5]	Bortfeldt A, Wäscher G. Constraints in container loading — a state-of-the-art review. European Journal of Operational Research, 2013, 229(1): 1−20 doi: 10.1016/j.ejor.2012.12.006
[6]	Scheithauer G. Algorithms for the container loading problem. In: Proceedings of the 1991 on Operations Research. Berlin, Heidelberg, Germany: Springer, 1992. 445−452
[7]	Fanslau T, Bortfeldt A. A tree search algorithm for solving the container loading problem. INFORMS Journal on Computing, 2010, 22(2): 222−235 doi: 10.1287/ijoc.1090.0338
[8]	Fekete S P, Schepers J, Van der Veen J C. An exact algorithm for higher-dimensional orthogonal packing. Operations Research, 2007, 55(3): 569−587 doi: 10.1287/opre.1060.0369
[9]	Bischoff E E, Ratcliff B S W. Issues in the development of approaches to container loading. Omega, 1995, 23(4): 377−390 doi: 10.1016/0305-0483(95)00015-G
[10]	Bischoff E E, Janetz F, Ratcliff M S W. Loading pallets with non-identical items. European Journal of Operational Research, 1995, 84(3): 681−692 doi: 10.1016/0377-2217(95)00031-K
[11]	He K, Huang W Q. An efficient placement heuristic for three-dimensional rectangular packing. Computers and Operations Research, 2011, 38(1): 227−233
[12]	Huang W Q, He K. A caving degree approach for the single container loading problem. European Journal of Operational Research, 2009, 196(7): 93−101
[13]	He K, Huang W Q. A caving degree based flake arrangement approach for the container loading problem. Computers and Industrial Engineering, 2010, 59(2): 344−351
[14]	Lim A, Rodrigues B, Wang Y. A multi-faced buildup algorithm for three-dimensional packing problems. Omega, 2003, 31(6): 471−481 doi: 10.1016/j.omega.2003.08.004
[15]	张德富, 魏丽军, 陈青山, 陈火旺. 三维装箱问题的组合启发式算法. 软件学报, 2007, 18(9): 2083−2089 doi: 10.1360/jos182083 Zhang De-Fu, Wei Li-Jun, Chen Qing-Shan, Chen Huo-Wang. A combinational heuristic algorithm for the three dimensional packing problem. Journal of Software, 2007, 18(9): 2083−2089 doi: 10.1360/jos182083
[16]	Gehring H, Bortfeldt A. A genetic algorithm for solving the container loading problem. International Transactions in Operational Research, 1997, 4(5–6): 401−418 doi: 10.1111/j.1475-3995.1997.tb00095.x
[17]	Bortfeldt A, Gehring H. A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research, 2001, 131(1): 143−161 doi: 10.1016/S0377-2217(00)00055-2
[18]	Sixt M. Dreidimensionale Packprobleme. Losungsverfahren Basierend auf den Meta-Heuristiken Simulated Annealing und Tabu-Suche. Frankfurt am Main: Europaischer Verlag der Wissenschaften, 1996.
[19]	Bortfeldt A, Gehring H, Mack D. A parallel tabu search algorithm for solving the container loading problem. Parallel Computing, 2003, 29(5): 641−662 doi: 10.1016/S0167-8191(03)00047-4
[20]	Mack D, Bortfeldt A, Gehring H. A parallel hybrid local search algorithm for the container loading problem. International Transactions in Operational Research, 2004, 11(5): 511−533 doi: 10.1111/j.1475-3995.2004.00474.x
[21]	张德富, 彭煜, 朱文兴, 陈火旺. 求解三维装箱问题的混合模拟退火算法. 计算机学报, 2009, 32(11): 2147−2156 Zhang De-Fu, Peng Yu, Zhu Wen-Xing, Chen Huo-Wang. A hybrid simulated annealing algorithm for the three-dimensional packing problem. Chinese Journal of Computers, 2009, 32(11): 2147−2156
[22]	Bischoff E E. Three-dimensional packing of items with limited load bearing strength. European Journal of Operational Research, 2006, 168(3): 952−966 doi: 10.1016/j.ejor.2004.04.037
[23]	Moura A, Oliveira J F. A GRASP approach to the container-loading problem. IEEE Intelligent Systems, 2005, 20(4): 50−57 doi: 10.1109/MIS.2005.57
[24]	Parreno F, Alvarez-Valdes R, Oliveira J F, Tamarit J M. A maximal-space algorithm for the container loading problem. INFORMS Journal on Computing, 2007, 20(3): 412−422
[25]	Morabito R, Arenales M. An AND/OR-graph approach to the container loading problem. International Transactions in Operational Research, 1994, 1(1): 59−73
[26]	Terno J, Scheithauer G, Sommerweiß U, Riehme J. An efficient approach for the multi-pallet loading problem. European Journal of Operational Research, 2000, 123(2): 372−381 doi: 10.1016/S0377-2217(99)00263-5
[27]	Eley M. Solving container loading problems by block arrangement. European Journal of Operational Research, 2002, 141(2): 393−409 doi: 10.1016/S0377-2217(02)00133-9
[28]	Hifi, M. Approximate algorithms for the container loading problem. International Transactions in Operational Research, 2002, 9(6): 747−774 doi: 10.1111/1475-3995.00386
[29]	Pisinger D. Heuristics for the container loading problem. European Journal of Operational Research, 2002, 141(2): 143−153
[30]	Lim A, Ma H, Xu J, Zhang X W. An iterated construction approach with dynamic prioritization for solving the container loading problems. Expert Systems with Applications, 2012, 39(4): 4292−4305 doi: 10.1016/j.eswa.2011.09.103
[31]	张德富, 彭煜, 张丽丽. 求解三维装箱问题的多层启发式搜索算法. 计算机学报, 2012, 35(12): 2553−2561 doi: 10.3724/SP.J.1016.2012.02553 Zhang De-Fu, Peng Yu, Zhang Li-Li. A multi-layer heuristic search algorithm three dimensional container loading problem. Chinese Journal of Computers, 2012, 35(12): 2553−2561 doi: 10.3724/SP.J.1016.2012.02553
[32]	Liu S, Tan W, Xu Z Y, Liu X W. A tree search algorithm for the container loading problem. Computers and Industrial Engineering, 2014, 75: 20−30
[33]	刘胜, 朱凤华, 吕宜生, 李元涛. 求解三维装箱问题的启发式正交二叉树搜索算法. 计算机学报, 2015, 38(8): 1530−1543 doi: 10.11897/SP.J.1016.2015.01530 Liu Sheng, Zhu Feng-Hua, Lv Yi-Sheng, Li Yuan-Tao. A heuristic orthogonal binary tree search algorithm for three dimensional container loading problem. Chinese Journal of Computers, 2015, 38(8): 1530−1543 doi: 10.11897/SP.J.1016.2015.01530
[34]	Ren J D, Tian Y J, Sawaragi T. A tree search method for the container loading problem with shipment priority. European Journal of Operational Research, 2011, 214(3): 526−535 doi: 10.1016/j.ejor.2011.04.025
[35]	Wang N, Lim A, Zhu W B. A multi-round partial beam search approach for the single container loading problem with shipment priority. International Journal of Production Economics, 2013, 145(2): 531−540 doi: 10.1016/j.ijpe.2013.04.028
[36]	Lim A, Ma H, Qiu C Y, Zhu W B. The single container loading problem with axle weight constraints. International Journal of Production Economics, 2013, 144(1): 358−369 doi: 10.1016/j.ijpe.2013.03.001
[37]	Liu S, Shang X Q, Cheng C J, Zhao H X, Wang F-Y. Heuristic algorithm for the container loading problem with multiple constraints. Computers and Industrial Engineering, 2017, 108: 149−164
[38]	Wang L, Lu J W. A memetic algorithm with competition for the capacitated green vehicle routing problem. IEEE/CAA Journal of Automatica Sinica, 2019, 6(2): 516−526
[39]	Shang X Q, Shen D Y, Wang F-Y, Nyberg T R. A heuristic algorithm for the fabric spreading and cutting problem in apparel factories. IEEE/CAA Journal of Automatica Sinica, 2019, 6(4): 961−968
[40]	Luo C, Shen Z, Evangelou S, Xiong G, Wang F-Y. The combination of two control strategies for series hybrid electric vehicles. IEEE/CAA Journal of Automatica Sinica, 2019, 6(2): 596−608
[41]	Shen Z, Shang X Q, Dong X S, Xiong G, Wang F-Y. A learning based framework for error compensation in 3D printing. IEEE Transactions on Cybernetics, 2019, 49(11): 4042−4050