2.765

2022影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

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

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

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

doi: 10.16383/j.aas.c180795
基金项目: 国家重点研究发展计划基金(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

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

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得到的填充率高于现有装箱算法.
  • 图  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

    算法约束填充率 (%)
    BR1BR2BR3BR4BR5BR6BR7平均
    GA_GB[16]C1&C285.8087.2688.1088.0487.8687.8587.6887.5
    GRASP[23]C193.5293.7793.5893.0592.3491.7290.5592.65
    FDA[11]C192.9293.9393.7193.6893.7393.6393.1493.53
    HSA[21]C1&C293.8193.9493.8693.5793.2292.7291.9993.30
    Maximal-space[24]C193.8594.2294.2594.0993.8793.5292.9493.82
    A2[12]C1
    CLTRS[7]C195.0595.4395.4795.1895.0094.7994.2495.02
    C1&C294.5194.7394.7494.4194.1393.8593.2094.22
    MLHS[31]C194.9295.4895.6995.5395.4495.3894.9595.34
    C1&C294.4994.8995.2094.9494.7894.5593.9594.69
    MLTrSC193.8193.8393.8093.9893.9793.8393.9193.88
    C1&C293.4893.4193.7993.8593.4393.6593.6393.61
    下载: 导出CSV

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

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

    算法约束填充率 (%)
    BR8BR9BR10BR11BR12BR13BR14BR15平均
    GA_GB[15]C1&C287.5286.4685.5384.8284.2583.6782.9982.4784.71
    GRASP[23]C190.2689.5088.7387.8787.1886.7085.8185.4887.69
    FDA[11]C192.9292.4992.2491.9191.8391.5691.3091.0291.9
    HSA[21]C1&C290.5689.789.0688.1887.7386.9786.1685.4487.98
    Maximal-space[24]C191.0290.4689.8789.3689.0388.5688.4688.3689.39
    A2[12]C188.4188.1487.987.8887.9287.9287.8287.7387.97
    CLTRS[7]C193.7093.4493.0992.8192.7392.4692.4092.4092.88
    C1&C292.2691.4890.8690.1189.5188.9888.2687.5789.88
    MLHS[31]C194.5494.1493.9593.6193.3893.1493.0692.9093.59
    C1&C293.1292.4891.8391.2390.5989.9989.3488.5490.89
    MLTrSC193.9893.9793.7893.7593.6393.4393.2593.1293.61
    C1&C291.8291.6991.5591.2491.2191.0390.7890.5991.24
    下载: 导出CSV
  • [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
  • 加载中
图(6) / 表(2)
计量
  • 文章访问数:  1978
  • HTML全文浏览量:  465
  • PDF下载量:  224
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-11-29
  • 网络出版日期:  2020-01-21
  • 刊出日期:  2020-07-10

目录

    /

    返回文章
    返回