2.793

2018影响因子

(CJCR)

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

留言板

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

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

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

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

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

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


DOI: 10.16383/j.aas.c180795
详细信息
    作者简介:

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

    2011年获国防科技大学系统工程学院系统工程学士学位, 2013年获国防科技大学系统工程硕士学位; 2018年获国防科技大学管理科学与工程博士学位. 他目前的研究方向包括智能调度、人工智能算法和并行社会系统.Email: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

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

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

More Information
  • Fund Project:  Supported by National Research Development Program of China (2018YFB1004803), National Natural Science Foundation of China (61773381, 61773382, 61533019), Hunan’s S & T Project(2018GK1040), Guangdong’s S & T Project (2017B090912001)
  • 摘要: 本文提出了一种求解三维装箱问题的多层树搜索算法, 该算法采用箱子-片-条-层-实体的顺序生成装载方案, 装载方案由实体表示. 该算法由三层搜索树构成, 第一层为三叉树, 每个树节点的三个分叉分别对应向实体中填入XY面平行层、XZ面平行层、YZ面平行层; 第二层为二叉树, 每个树节点的两个分叉分别对应向层内装载两个相互垂直的最优条; 第三层为四叉树, 用于将同种的多个箱子生成片. 在同时满足摆放方向约束和完全支撑约束的前提下, 该算法求解BR12-BR15得到的填充率高于现有装箱算法.
  • 图  1  坐标系和容器、箱子尺寸和摆放方向示意图

    图  2  $piece$示意图

    图  3  $strip$示意图

    图  4  $layer$示意图

    图  5  $entity$示意图

    图  6  ${\bf{TrS\_X\_Piece}}$搜索树

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

    算法约束填充率(%)
    BR1BR2BR3BR4BR5BR6BR7Mean
    GA_GB[15]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的填充率比较

    算法约束填充率(%)
    BR8BR9BR10BR11BR12BR13BR14BR15Mean
    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] 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] 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] 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] 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 //Operations Research Proceedings. Berlin: Springer, 1992: 445−452
    [7] 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] 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] 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] 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] 11 He Kun, Huang Wenqi. An efficient placement heuristic for three-dimensional rectangular packing. Computers & Operations Research, 2011, 38(1): 227−233
    [12] 12 Huang Wenqi, He Kun. A caving degree approach for the single container loading problem. European Journal of Operational Research, 2009, 196(7): 93−101
    [13] 13 He Kun, Huang Wenqi. A caving degree based flake arrangement approach for the container loading problem. Computers & Industrial Engineering, 2010, 59(2): 344−351
    [14] 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] 15 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
    [16] 张德富, 魏丽军, 陈青山, 陈火旺. 三维装箱问题的组合启发式算法. 软件学报, 2007, 18(9): 2083−2089 doi:  10.1360/jos182083

    16 Zhang De-Fu, WeiLi-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
    [17] 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] 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] 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

    21 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] 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] 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] 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] 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] 26 Terno J, G Scheithauer, U Sommerweiß, J Riehme. 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] 27 Eley Michael. 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] 28 Hi fi, 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] 29 Pisinger D. Heuristics for the container loading problem. European Journal of Operational Research, 2002, 141(2): 143−153
    [30] 30 Lim, A., Ma, H., Xu, J., & Zhang, X. 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

    31 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] 32 Liu, S., Tan, W., Xu, Z., & Liu, X. A tree search algorithm for the container loading problem. Computers & Industrial Engineering, 2014, 75: 20−30
    [33] 刘胜, 朱凤华, 吕宜生, 李元涛. 求解三维装箱问题的启发式正交二叉树搜索算法. 计算机学报, 2015, 38(8): 1530−1543 doi:  10.11897/SP.J.1016.2015.01530

    33 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] 34 Ren, J., Tian, Y., 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] 35 Wang, N., Lim, A., Zhu, W. 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] 36 Lim, A., Ma, H., Qiu, C., Zhu, W. 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] 37 Liu Sheng, Shang Xiuqin, Cheng Changjian, Zhao Hongxia, Wang Feiyue. Heuristic algorithm for the container loading problem with multiple constraints. Computers & Industrial Engineering, 2017, 108: 149−164
    [38] OR Library. http://people.brunel.ac.uk/~mastjjb/jeb/orlib/thpackinfo.html
  • [1] 李孙寸, 施心陵, 张松海, 董易, 高莲. 基于多元优化算法的三维装箱问题的研究[J]. 自动化学报, doi: 10.16383/j.aas.2018.c160381
    [2] 王金然, 罗小元, 杨帆, 关新平. 三维最优持久编队拓扑生成策略[J]. 自动化学报, doi: 10.16383/j.aas.2015.c140474
    [3] 窦全胜, 李国江, 史忠植, 姜平. 三维网格空间上的自组装模型[J]. 自动化学报, doi: 10.3724/SP.J.1004.2012.01595
    [4] 周果清, 王庆. 基于minmaxKKT条件的三维重构方法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2012.01439
    [5] 戴先中, 臧强, 张凯锋. 非线性微分--代数子系统的逆系统的构造[J]. 自动化学报, doi: 10.3724/SP.J.1004.2009.01094
    [6] 蔡秀珊, 韩正之, 汪晓东. 一类非线性系统控制Lyapunov函数的构造[J]. 自动化学报
    [7] 徐一华, 李京峰, 贾云得. 人体三维运动实时跟踪与建模系统[J]. 自动化学报
    [8] 刘国才, 王耀南. 基于水平集逐层迭代算法的多层Mumford-Shah图像分割、去噪与重建模型[J]. 自动化学报
    [9] 王红霞, 陈波, 成礼智. 基于主方向构造二分树复数小波的新方法[J]. 自动化学报
    [10] 楼建光, 柳崎峰, 谭铁牛, 胡卫明. 基于三维模型的交通场景视觉监控[J]. 自动化学报
    [11] 黄向生, 杨小帆, 王阳生. 基于提升方案的高维形态小波构造[J]. 自动化学报
    [12] 胡卫明, 吴兵, 刘崴. 大幅面地图的三维地形重建[J]. 自动化学报
    [13] 张茂军, 钟力, 孙立峰, 李云浩, 胡晓峰. HVS:构造一个虚拟实景空间[J]. 自动化学报
    [14] 刘向杰, 柴天佑, 张焕水. 三维模糊控制器的结构研究[J]. 自动化学报
    [15] 苗原, 李春文. 含二维临界部分系统的李亚普诺夫函数构造[J]. 自动化学报
    [16] 林应强, 吴立德. 基于模型的三维物体识别[J]. 自动化学报
    [17] 刘成君, 戴汝为. 广义线性八元树表示及物体的广义三维重建[J]. 自动化学报
    [18] 姚增起. 用不可靠元件构造可靠系统及其神经网络实现[J]. 自动化学报
    [19] 柳星, 喻学恒. 动态系统的随意观测性及其观测器的构造[J]. 自动化学报
    [20] 柳星, 喻学恒. 非线性系统降价观测器的构造[J]. 自动化学报
  • 加载中
图(6) / 表(2)
计量
  • 文章访问数:  368
  • HTML全文浏览量:  235
  • PDF下载量:  38
  • 被引次数: 0
出版历程
  • 网络出版日期:  2020-01-21

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

doi: 10.16383/j.aas.c180795
    基金项目:  国家重点研发计划项目(2018YFB1004803), 国家自然科学基金(61773381, 61773382, 61533019), 湖南省科技重大专项(2018GK1040), 广东省科技厅项目(2017B090912001) 资助
    作者简介:

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

    2011年获国防科技大学系统工程学院系统工程学士学位, 2013年获国防科技大学系统工程硕士学位; 2018年获国防科技大学管理科学与工程博士学位. 他目前的研究方向包括智能调度、人工智能算法和并行社会系统.Email: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

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

English Abstract

刘胜, 沈大勇, 商秀芹, 赵红霞, 董西松, 王飞跃. 求解三维装箱问题的多层树搜索算法. 自动化学报, 2020, 46(x): 1−10. doi: 10.16383/j.aas.c180795
引用本文: 刘胜, 沈大勇, 商秀芹, 赵红霞, 董西松, 王飞跃. 求解三维装箱问题的多层树搜索算法. 自动化学报, 2020, 46(x): 1−10. 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(x): 1−10. 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(x): 1−10. doi: 10.16383/j.aas.c180795
  • 三维装箱问题(a three-dimensional container loading problem, 3D-CLP)研究如何通过优化货物摆放来提高货箱空间利用率, 应用三维装箱算法不仅可以降低货物运输成本, 还可以减少运输工具在运输过程中的碳排放, 具有很好的社会经济效益.

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

    本文接下来讲述如下内容: 第二节简要回顾三维装箱问题的研究进展; 第三节详细叙述本文提出的三维装箱算法的实现步骤; 第四节给出本文算法运行BR[9]算例的结果, 并将结果与目前最新算法的运行结果相比较. 最后第五节总结了本文算法的特点, 并展望了下一步的研究思路.

    • 3D-CLP是典型的NP难题[6, 7], 不存在多项式时间复杂度的最优求解算法. 用传统的精确算法求解这类问题, 会发生“组合爆炸”的现象, 只适合解决箱子种类数量较小的装箱问题, Fekete等人[8]给出了一种求解该问题的精确方法. 对于实际应用中规模比较大的装箱问题, 精确方法难以在可接受时间内求得最优解, 启发式方法依然是首选. 近年来有大量文献报道求解3D-CLP的启发式算法. 按照方法类型来分, 这些算法可以分为以下三种:

      (1)经典启发式方法. 此类方法分为两大类, 一类是构造法, 即从一个空的方案逐步生成一个完全的装载方案, 文献[9-13]的提出的方法可以归为此类方法, 文献[16]将拟人法与模拟退火算法相结合, 取得了很好的效果; 一类是提升法, 即首先生成一个完全的装载方案, 然后不断地优化提升该方案, 文献[14]利用多面构建的方法, 显著提升了填充率.

      (2)元启发式方法. 元启发式方法包括遗传算法、禁忌搜索、模拟退火、贪婪随机自适应等方法, 近年来在求解3D-CLP中得到广泛应用. 文献[15-17]利用遗传算法求解3D-CLP. 文献[18, 19]分别给出了一种求解3D-CLP的禁忌搜索方法. 文献[16, 18, 20, 21]将模拟退火算法应用于求解3D-CLP, 文献[22]给出了基于Nelder-Mead方法的局部搜索方法, 用以提升3D-CLP的解的质量. 文献[23, 24]给出求解3D-CLP的贪婪随机自适应搜索方法(a greedy randomized adaptive search procedure, GRASP).

      (3)树搜索法. 树搜索或图搜索方法用于求解三维装箱问题, 形成了一批高效的求解算法. 文献[25]提出了求解3D-CLP的And/Or graph算法. 文献[26]将分支定界法集成到求解3D-CLP的算法中. 文献[7, 27-34]都是基于树搜索的算法.

      按照装载方案的构造方式来分, 这些启发式算法可以分为以下六种:

      (1)墙构造法(Wall building approach). 其特征是装载方案由一块块竖直的“物品墙”组成, “墙”依次放入容器中, 其上下左右和后方五个方向需紧贴容器剩余空间的边以提高填充率, 所有“墙”的四个竖直面至少有一个和容器竖直面重合. 代表性方法有文献[17, 29]文献[32, 33, 37].

      (2)建堆法(Stack building approach). 其特征是先将物品组合成一个个和容器等高的长方体“堆”, 再将这些“堆”放置到容器中, 与墙构造法不同的是, 堆的四个竖直面不必和容器的竖直重合, 但是堆的上下水平面必须和容器上下水平面重合. 文献[9]和文献[15]正是基于这种方法.

      (3)水平层构造法(Horizontal layer building approach). 其特征是装载方案由一块块水平的长方体物品层组成, 层的四个竖直面和容器的竖直面重合. 代表性方法有文献[10]和文献[26].

      (4)块构造法(Block building approach). 其特征是装载方案由一个个长方体“块”构成, 每个块由尺寸相同(或相近)的并且摆放方向相同的物品组成. 大多数算法采用这种构造方式. 如文献[7, 19, 20, 27, 31, 34]中所述方法.

      (5)完全切割法(Guillotine cutting approach). 该方法利用完全切割树将容器分为多个小的长方体空间, 切割树的叶子结点代表物品. 文献[25]正是基于这种方法.

      (6)基于穴度的全局构造法(Caving-degree- based global building approach). 该方法从全局考虑, 依次为每个物品在容器中寻找最佳放置位置, 再评价所有待放置物品放入后的效果, 选择效果最佳的物品放置到最佳位置, 从而获得高效装载方案. 文献[11-13]对该方法进行了深入的研究, 取得了一系列成果.

      大多数的算法满足摆放方向约束和支撑约束, 除此以外, 还有一些文献提出了满足其他约束的算法. 文献[34, 35]提出了带有运输优先级约束的算法. 文献[30]和[36]分别提出带有动态优先级和轴重约束的算法. 文献[37]算法同时满足运输优先级和完全运输约束.

      本文提出的多层树搜索算法是墙构造法和水平层法相结合的树搜索算法, 与文献[32]和[33]只有一层搜索树不同的是, 本文算法包括三层搜索树, 文献[32]和[33]算法只用到竖直层(即“墙”), 而本文算法同时包括竖直层和水平层. 本文算法简称为多层树搜索算法(MLTrS, Multi-level Tree Search).

    • 3D-CLP问题的形式化定义如下: 给定一个长、宽、高分别为$L$$W$$H$的长方体容器$C$$n$个长方体箱子${b_1}$${b_2}$$ \cdots $${b_n}$, 用集合$B$表示这些箱子, 箱子${b_i}\;\left( {i = 1,2, \cdots ,n} \right)$$l_i$、宽 $w_i$和高 $h_i$, 箱子${b_i}\;\left( {i = 1,2, \cdots ,n} \right)$的体积表示为${v_i} = {l_i}{w_i}{h_i}$. 用0-1标志$z{l_i}$$z{w_i}$$z{h_i}$表示箱子${b_i}\;\left( {i = 1,2, \cdots ,n} \right)$的长宽高是否允许向上摆放(0表示不允许, 1表示允许), 令

      $$ C = \left( {L,W,H} \right),\qquad\qquad\qquad $$ (1)
      $$ B = \left\{ {{b_1},{b_2}, \cdots ,{b_n}} \right\},\qquad\qquad $$ (2)
      $$ {b_i} = \left( {{l_i},{w_i},{h_i},u{l_i},u{w_i},u{h_i}} \right).\; $$ (3)

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

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

      $F$$B$的一个子集, 定义$F$中所有箱子体积之和为${V_F}$, 问题的目标是选择$B$的一个子集$F$使得${V_F}$最大, 并且满足以下条件: 对任何箱子${b_i} \in F$, 在容器$C$中对应一个装填位置; 所有$F$中的箱子必须全部包含在$C$中; $F$中任何两个箱子在$C$中不重叠; $F$中箱子${b_i}$的放置方向必须满足方向标志$u{l_i}$$u{w_i}$$u{h_i}$要求. 定义子集$F$对应的容器$C$的填充率为${{F{R_F} = {V_F}} / {\left( {LWH} \right)}}$. 如果三维装箱问题带有完全支撑约束, 则容器中所有箱子的底部都必须与容器底部或者其他箱子的顶部完全接触. 为了便于介绍算法, 进行如下定义:

      (1)片$piece$: 从长方体箱子的集合$B$取出完全相同的多个箱子进行摆放, 要求在$x$轴、$y$轴、$z$ 轴三个方向中的一个方向上只摆放一层, 且所有箱子在该方向上摆放尺寸相同, 则这些箱子的摆放构成一个$piece$. 定义$piece$的三维坐标与尺寸为它的母长方体的三维坐标与尺寸($piece$的母长方体定义: 在生成$piece$之前, 我们先给定三维尺寸边界, 生成的$piece$不能超过该边界, 则该三维尺寸边界构成的长方体就是$piece$的母长方体). 分别以${\rm{XS}} \left( {piece} \right)$${\rm{YS}} \left( {piece} \right)$${\rm{ZS}} \left( {piece} \right)$表示$piece$的三维尺寸, 以${\rm{VB}} \left( {piece} \right)$表示$piece$中所有箱子体积和, 定义$piece$的填充率${\rm{Fr}} \left( {piece} \right)$${\rm{VB}} \left( {piece} \right)$除以$piece$的生成长方体体积. 如果$piece$$x$轴方向只摆放一层, 则称为$x\_piece$, 同理可得$y\_piece$$z\_piece$, 图2$x\_piece$$y\_piece$$z\_piece$的示意图.

      图  2  $piece$示意图

      (2)条$strip$: 给定一组$x\_piece$($y\_piece$, $z\_piece$), 从中选择一个子集, 在满足箱子摆放方向约束的前提下, 沿$x$轴($y$轴, $z$轴)摞成一串, 形成条$strip$. 定义$strip$的三维坐标与尺寸为它的母长方体的三维坐标与尺寸($strip$的母长方体定义: 在生成$strip$之前, 我们先给定三维尺寸边界, 生成的$strip$不能超过该边界, 则该三维尺寸边界构成的长方体就是$strip$的母长方体). 分别以${\rm{XS}} \left( {strip} \right)$${\rm{YS}} \left( {strip} \right)$${\rm{ZS}} \left( {strip} \right)$表示$strip$的三维尺寸, 以${\rm{VB}} \left( {strip} \right)$表示$strip$中所有箱子体积和, 定义$strip$的填充率${\rm{Fr}} \left( {strip} \right)$为构成${\rm{VB}} \left( {strip} \right)$除以$strip$的最小包围长方体体积. 由$x\_piece$沿$x$轴摞成一串构成的$strip$称为$x\_strip$, 同理可得$y\_strip$$z\_strip$, 图3$x\_strip$$y\_strip$$z\_strip$的示意图.

      图  3  $strip$示意图

      (3)层$layer$: 给定一组$x\_strip$与一组$y\_strip$, 从两组中选择一个子集, 在满足箱子摆放方向约束的前提下, 沿与$xy$面平行的面排列子集中的$strip$, 所有摆放的$strip$$z$坐标相同, 形成层$layer$. 定义$layer$的三维坐标与尺寸为它的母长方体的三维坐标与尺寸($layer$的母长方体定义: 在生成$layer$之前, 我们先给定三维尺寸边界, 生成的$layer$不能超过该边界, 则该三维尺寸边界构成的长方体就是$layer$的母长方体). 分别以${\rm{XS}} \left( {layer} \right)$${\rm{YS}} \left( {layer} \right)$${\rm{ZS}} \left( {layer} \right)$表示$layer$的三维尺寸, 以${\rm{VB}} \left( {layer} \right)$表示$layer$中所有箱子体积和, 定义$layer$的填充率${\rm{Fr}} \left( {layer} \right)$${\rm{VB}} \left( {layer} \right)$除以$layer$的最小包围长方体体积. 由$x\_strip$$y\_strip$沿与$xy$面平行的面排列形成的$layer$称为$xy\_layer$. 同理可得$yz\_layer$$xz\_layer$, 图4$xy\_layer$$yz\_layer$$xz\_layer$的示意图.

      图  4  $layer$示意图

      (4)装载实体$entity$: 给定容器$C$和箱子集合$B$, 从集合$B$中选取一个子集$Q$, $Q$中的箱子全部装入容器$C$, $Q$中所有这些箱子的摆放位置和摆放方向整体构成一个装载实体$entity$, 一个$entity$即是一个装箱方案, 其母长方体就是容器$C$的最大内部空间长方体. 一个$entity$可以分解为一组$layer$, 每一个$layer$可以分解为一组$strip$, 每一个$strip$可以分解为一组$piece$, 每个$piece$则由若干个完全相同的箱子组成. 定义${\rm{VB}} \left( {entity} \right)$$entity$中所有箱子体积和, 定义$entity$的填充率${\rm{Fr}} \left( {entity} \right)$为VB$ \left( {entity} \right)$除以容器$C$的容积. 图5$entity$示意图.

      图  5  $entity$示意图

      过程1.${\bf{TrS\_Entity}}$

      $ {\bf{TrS\_Entity}}\left( {best\_entity,entity,xr,yr,zr,B} \right)$

      $ \left\{ {\text{创建空的}}\right.xy\_layer,best\_xy\_layer,xz\_layer,$$best\_ xz\_layer,yz\_layer{\text{和}}best\_yz\_layer$

      $$ \left\{ \begin{array}{l} {\rm{for}}\; {\rm{each}}\; {\rm{feasible}} \;z\_size \;\;{\rm{ for }}\;\; xy\_layer\\ \;\;\;\;{\rm{ }}{\bf{TrS\_XY\_Layer}}( best\_xy\_layer,xy\_layer,xr,yr,\\ \qquad\qquad\qquad\qquad z\_size,B )\\ \;\;\;\;{\rm{ }}{\mathop{\rm if}\nolimits} \left( {{\mathop{\rm Fr}\nolimits} \left( {xy\_layer} \right) > {\mathop{\rm Fr}\nolimits} \left( {best\_xy\_layer} \right)} \right)\\ \;\;\;\;\;\;{\rm{ }}best\_xy\_layer = xy\_layer\\ {\rm{ }}xy\_entity = entity \cup best\_xy\_layer\\ {\rm{ if}}\left( {{\mathop{\rm VB}\nolimits} \left( {xy\_entity} \right) > {\mathop{\rm VB}\nolimits} \left( {best\_entity} \right)} \right){\rm{ }}\\ \;\;\;\;\;\;{\rm{ }}best\_entity{\rm{ = }}xy\_entity\\ {\rm{ }}xy\_B = B - best\_xy\_layer{\text{中的箱子}}\\ {\bf{ TrS\_Entity}}( xy\_entity,xr,yr,zr - \\ \qquad\qquad\quad {\mathop{\rm ZS}\nolimits} \left( {best\_xy\_layer} \right),xy\_B ) \end{array} \right. $$
      $$ \left\{ \begin{array}{l} {\rm{ }}\;\;\;\;\;{\rm{for}}\;{\rm{ each}}\;{\rm{ feasible }}\;y\_size\;{\rm{ for }}\;xz\_layer\\ {\rm{ }}\;\;\;\;\;{\rm{ }}\;\;{\bf{TrS\_XZ\_Layer}}( best\_xz\_layer,xz\_layer,xr,\\ \qquad\qquad\qquad\qquad \;\; y\_size,zr,B )\\ {\rm{ }}\;\;\;\;\;\;{\mathop{\rm if}\nolimits} \left( {{\mathop{\rm Fr}\nolimits} \left( {xz\_layer} \right) > {\mathop{\rm Fr}\nolimits} \left( {best\_xz\_layer} \right)} \right)\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{ }}best\_xz\_layer = xz\_layer\\ \;\;\;\;xz\_entity = entity \cup best\_xz\_layer\\ {\rm{ }}\;\;\;\;\;\;\;{\rm{if}}\left( {{\mathop{\rm VB}\nolimits} \left( {xz\_entity} \right) > {\mathop{\rm VB}\nolimits} \left( {best\_entity} \right)} \right){\rm{ }}\\ {\rm{ }}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;best\_entity{\rm{ = }}xz\_entity\\ {\rm{ }}\;\;\;\;\;xz\_B = B - best\_xz\_layer{\text{中的箱子}}\\ \;\;\;\;\;\;\;{\bf{TrS\_Entity}}( xz\_entity,xr,yr - \\ \qquad\qquad\qquad\quad {\mathop{\rm YS}\nolimits} \left( {best\_xz\_layer} \right),zr,xz\_B)\end{array} \right. $$
      $$ \;\left\{ \begin{array}{l} \;\;\;\;\;\;\;\;{\rm{for}}\;{\rm{ each}}\;{\rm{ feasible }}\;x\_size\;{\rm{ for }}\;yz\_layer\\ {\rm{ }}\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\bf{TrS\_YZ\_Layer}}(best\_yz\_layer,\\ \qquad\qquad\qquad\qquad\qquad yz\_layer,x\_size,yr,zr,B )\\ {\rm{ }}\;\;\;\;\;\;\;\;\;{\mathop{\rm if}\nolimits} \left( {{\mathop{\rm Fr}\nolimits} \left( {yz\_layer} \right) > {\mathop{\rm Fr}\nolimits} \left( {best\_yz\_layer} \right)} \right)\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;best\_yz\_layer = yz\_layer\\ \;\;\;\;\;yz\_entity = entity \cup best\_yz\_layer\\ \;\;\;\;\;\;{\rm{ if}}\left( {{\mathop{\rm VB}\nolimits} \left( {yz\_entity} \right) > {\mathop{\rm VB}\nolimits} \left( {best\_entity} \right)} \right){\rm{ }}\\ {\rm{ }}\;\;\;\;\;\;\;\;\;\;\;\;{\rm{ }}best\_entity{\rm{ = }}yz\_entity\\ {\rm{ }}\;\;\;\;\;\;yz\_B = B - best\_yz\_layer{\text{中的箱子}}\\ \;\;\;\;{\bf{TrS\_Entity}}(yz\_entity,xr - \\ \qquad\qquad\qquad {\mathop{\rm XS}\nolimits} \left( {best\_yz\_layer} \right),yr,zr,yz\_B)\end{array} \right. $$
    • MLTrS算法包含三层搜索树, 第一层树搜索${\rm{TrS \_Entity}}$是三叉树, 也是算法的主过程, 用于搜索最优$entity$; 第二层树搜索${\rm{TrS \_Layer}}$(包含${\rm{TrS \_XY\_} }$${\rm{Layer}}$, ${\rm{TrS \_XZ\_Layer}}$${\rm{TrS\_YZ\_Layer}} $三种)是二叉树, 用于搜索最优$layer$; 第三层树搜索${\rm{TrS \_Piece}}$(包含${\rm{TrS \_X\_Piece}}$, ${\rm{TrS \_Y\_Piece}}$${\rm{TrS\_Z\_Piece}} $三种)是四叉树, 用于搜索最优$piece$.

      MLTrS算法主过程${\rm{TrS \_Entity}}$如过程1所示. 参数$best\_entity$$entity$分别表示最好的装载实体和当前的装载实体, 参数$xr$$yr$$zr$分别表示容器$C$剩余长方体空间的长宽高, 参数$B$是待装入的箱子集合. ${\rm{TrS \_Entity}}$实现部分包括四大部分, 以大括号分隔开, 第一部分创建6个空白的$layer$, 在接下来的部分将要用到; 第二部分是在剩余长方体空间内填入一个最优的$xy\_layer$; 第三部分是在剩余长方体空间内填入一个最优的$xz\_layer$; 第四部分是在剩余长方体空间内填入一个最优的$yz\_layer$.

      $xy\_layer$为例, 它的x轴向尺寸和y轴向尺寸分别等于$xr$$yr$, 而z轴向尺寸可能等于某个箱子在z轴方向可能的尺寸, 这样$xy\_layer$的可能的z轴向尺寸数量就非常多, 为了加速算法, 我们取尺寸权值最大的5个尺寸, 尺寸权值计算法定义: 初值为0, 对于每一个箱子的每一个边长, 如果该边长等于该尺寸, 而且该边可与z轴平行放置, 则尺寸权值加上与该边垂直的箱子面的面积. $xz\_layer$$yz\_layer$的可行尺寸选择方法可以参照$xy\_layer$.

      ${\rm{TrS \_XY\_Layer}}$, ${\rm{TrS \_XZ\_Layer}}$${\rm{TrS\_YZ\_Layer}} $分别用来求$xy\_layer$, $xz\_layer$$yz\_layer$, 由于三种求解方法是类似的, 限于篇幅, 以过程$\rm{TrS \_}$${\rm{XY\_Layer}}$求解$xy\_layer$为例展开叙述, 如过程2所示. 参数$best\_xy\_layer$$xy\_layer$分别代表最优$xy\_layer$和当前$xy\_layer$, 参数$xr$$yr$$zr$分别是剩余长方体空间的长宽高, 参数$B$表示待装入的箱子集合. ${\rm{TrS \_XY\_Layer}}$实现部分包括两个部分, 以大括号分隔开, 第一部分是在剩余长方体空间内填入一个最优的$x\_strip$, 第二部分是在剩余长方体空间内填入一个最优的$y\_strip$.

      ${\rm{Create \_Best\_X\_Strip\_For\_XY\_Layer}}$$ {\rm{Create \_}}$${\rm{Best\_Y\_Strip\_For\_XY\_Layer}}$ 分别为 $xy\_layer$ 求解$best\_ x\_strip$$best\_y\_strip$. 类似的, ${\rm{Create \_Best\_X\_}} $${\rm{Strip\_For\_XZ\_Layer}}$${\rm{Create \_Best\_Z\_Strip\_For\_XZ\_}}$${\rm{Layer}} $ 分别为 $xz\_layer$ 求解 $best\_x\_strip$$ best\_$$z\_strip,$${\rm{Create \_Best\_Y\_Strip\_For\_YZ\_Layer}}{\text{和}}$$Create \_ $${\rm{Best\_Z\_Strip\_For\_YZ\_Layer}}$ 分别为 $yz\_layer$求解 $best\_y\_strip$$best\_ $$z\_strip$. 这六种求解过程是类似的, 仅以过程${\rm{Create \_Best\_X\_Strip\_For\_XY\_}}$$Layer $求解$best\_x\_strip$为例展开叙述, 如过程3所示. 参数$xr$$yr$$zr$分别是剩余长方体空间的长宽高, 参数$B$表示待装入的箱子集合. 求解之前, $best\_ $$x\_strip$的y轴向尺寸尚未确定, 可能等于某个箱子在y轴方向可能的尺寸, 这样$best\_x\_strip$的可能的y轴向尺寸数量就非常多, 为了加速算法, 我们仅取在箱子边长(该边长必须能平行y轴放置)中出现频率最大的5个尺寸, 然后针对这5个尺寸, 分别求解出5个$x\_strip$, 从中选择填充率最高的作为最终结果返回.

      过程2. ${\bf{TrS\_XY\_Layer}}$

      $ {\bf{TrS\_XY\_Layer}}( best\_xy\_layer,xy\_layer,xr,yr,zr,B )$

      $$ \left\{ \!\!\!\!\begin{array}{l} best\_x\_strip \!=\! {\bf{CreateBest\_X\_Strip\_For\_XY\_Layer}}\\ \qquad\qquad\qquad \left( {xr,yr,zr,B} \right)\\ {\rm{ }}x\_xy\_layer = xy\_layer \cup best\_x\_strip\\ {\rm{ }}{\rm{ if}}\left( {{\mathop{\rm VB}\nolimits} \left( {x\_xy\_layer} \right) > {\mathop{\rm VB}\nolimits} \left( {best\_xy\_layer} \right)} \right){\rm{ }}\\ {\rm{ }}\;\;\;best\_xy\_layer{\rm{ = }}x\_xy\_layer\\ {\rm{ }}x\_B = B - best\_x\_strip{\text{中的箱子}}\\ {\bf{TrS\_XY\_Layer}}( best\_xy\_layer,x\_xy\_layer,xr,yr - \\ \qquad\qquad\qquad {\mathop{\rm YS}\nolimits} \left( {best\_x\_strip} \right),zr,x\_B)\end{array} \right. $$
      $$ \left\{ \!\!\begin{array}{l} best\_y\_strip = {\bf{CreateBest\_Y\_Strip\_For\_XY\_Layer}}\\ \qquad\qquad\qquad \left( {xr,yr,zr,B} \right)\\ y\_xy\_layer = xy\_layer \cup best\_y\_strip\\ {\rm{ }}{\rm{if}}\left( {{\mathop{\rm VB}\nolimits} \left( {y\_xy\_layer} \right) > {\mathop{\rm VB}\nolimits} \left( {best\_xy\_layer} \right)} \right){\rm{ }}\\ {\rm{ }}\;\;\;\;\;\;\;best\_xy\_layer{\rm{ = }}y\_xy\_layer\\ {\rm{ }}y\_B = B - best\_y\_strip{\text{中的箱子}}\\ {\rm{ }}{\bf{TrS\_XY\_Layer}}( best\_xy\_layer,y\_xy\_layer,xr - \\ \qquad\qquad\qquad\quad{\mathop{\rm XS}\nolimits} \left( {best\_y\_strip} \right),yr,zr,y\_B) \end{array} \right. $$

      过程3. ${\bf{Create\_Best\_X\_Strip}}$

      $ {\bf{Create\_Best\_X\_Strip\_XY\_Layer}}\left( {xr,yr,zr,B} \right)$

        $ {\text{创建空的}}x\_strip{\text{和}}best\_x\_strip$

        $ {\rm{for}}\;{\rm{ each}}\;{\rm{ feasible }}\;y\_size\;{\rm{ for }}\;x\_strip$

      $ x\_strip = {\bf{Create\_X\_Strip}}\left( {xr,y\_size,zr,B} \right)$

         $ {\rm{if}}\left( {{\mathop{\rm Fr}\nolimits} \left( {x\_strip} \right) > {\mathop{\rm Fr}\nolimits} \left( {best\_x\_strip} \right)} \right)$

          $ best\_x\_strip{\rm{ = }}x\_strip$

        $ {\rm{return }}\;best\_x\_strip$

      ${\rm{Create \_X\_Strip}}$, ${\rm{Create \_Y\_Strip}}$${\rm{Create \_Z\_Strip}}$分别用来求$x\_strip$, $y\_strip$$z\_strip$, 由于三种求解方法是类似的, 限于篇幅, 以过程${\rm{Create \_X\_Strip}}$求解$x\_strip$为例展开叙述, 如过程4所示. 参数$xr$$yr$$zr$分别是剩余长方体空间的长宽高, 参数$B$表示待装入的箱子集合. 求解之前, 先将$B$中所有组合成$x\_piece$, 再以$xr$为背包容量, 以${\rm{XS}} \left( {x\_piece} \right)$为物品重量, 以${\rm{VB}} \left( {x\_piece} \right)$为物品价值, 用动态规划方法求解一维背包问题, 得到$x\_strip$并返回. 在为每一种箱子求解$x\_piece$时, 分别以箱子长宽高为$x\_piece$的x轴向尺寸, 预求解出三个备选项, 从中选择出填充率最高的, 然后去掉已经装入的箱子, 在进行新一轮的$x\_piece$生成, 直到该种箱子装完. 这里要去掉箱子过大无法在给定空间中形成$x\_piece$的情况.

      过程4. ${\bf{Create\_X\_Strip}}$

      $ {\bf{Create\_X\_Strip}}\left( {xr,yr,zr,B} \right)$

       $ {\text{创建空的}}x\_piece\_list$

       $ {\rm{for}}\;{\rm{ each}}\;{\rm{box}}\;{\rm{type }}\;{b_i}\;{\rm{ and}}\;{\rm{its}}\;{\rm{number }}\;nu{m_i}\;{\rm{ in }}\;B$

        $ {\rm{while}}\left( {num > 0} \right)$

         $ x\_piece\_a = \emptyset $

      $ {\bf{TrS\_X\_Piece}}\left( {x\_piece\_a,{l_i},yr,zr,b,num} \right)$

         $ x\_piece\_b = \emptyset $

      $ {\bf{TrS\_X\_Piece}}\left( {x\_piece\_b,{w_i},yr,zr,b,num} \right)$

         $ x\_piece\_c = \emptyset $

      $ {\bf{TrS\_X\_Piece}}\left( {x\_piece\_c,{h_i},yr,zr,b,num} \right)$

      $ x\_piece = {\rm{the}}\;{\rm{one}}\;{\rm{with}}\;{\rm{ highest}}\;{\rm{ Fr}}\;{\rm{ among }}\;x\_piece\_a, $$ x\_piece\_b{\text{和}}x\_piece\_c $

         $ {\text{将}}x\_piece{\text{加入}}x\_piece\_list$

         $ num{\rm{ = }}num{\rm{ }} - {\rm{ }}x\_piece{\text{中}}b{\text{的数量}}$

      $ x\_strip = {\text{一维书包}}\left( {xr\;{\rm{as}}{\text{背包容量}},x\_piece\_list\;{\rm{as}}\;{\text{物品列表}}} \right)$

       $ {\rm{return }}\;x\_strip$

      ${\rm{TrS \_X\_Piece}}$${\rm{TrS \_Y\_Piece}}$${\rm{TrS \_Z\_Piece}}$是三个树搜索过程, 分别求解$x\_piece$$y\_piece$$z\_piece$. 三个过程是类似的, 限于篇幅, 仅以过程${\rm{TrS \_X\_Piece}}$求解$x\_piece$为例展开, 如图6所示. 根据过程4可知在过程${\rm{TrS \_X\_Piece}}$中箱子在x轴向尺寸已经固定, 所以此时最多考虑两种摆放方向, 分别称为方向1和方向2. 对于每个节点, 其第一个子节点是将箱子以方向1沿y轴向摆放一排, 第二个子节点是将箱子以方向1沿z轴向摆放一排, 第三个子节点是将箱子以方向2沿y轴向摆放一排, 第四个子节点是将箱子以方向2沿z轴向摆放一排. 图中的数字表示箱子是在树的第几层摆放到相应$piece$中的. 实际求解过程中一旦找到填充率为1的$piece$立即结束搜索, 从而加快计算速度.

      图  6  ${\bf{TrS\_X\_Piece}}$搜索树

    • 由于MLTrS算法包含三层搜索树, 因此计算量特别大, 为了加快算法运行速度, 本文采用了一下两种加速机制.

      1. 纪录每一个片、条、层的创建输入和输出, 形成历史库, 在创建一个新的片、条、层之前, 首先查找历史库中有无类似纪录, 如果有, 则直接复制该纪录对应的输出, 从而节约大量计算时间. 以创建一个$x\_strip$为例, 假设输入中的三维空间长宽高分别为$x\_s$$y\_s$$z\_s$, 箱子集合为${B_i}$, 给定的如果历史库中存在一条$x\_strip$创建纪录, 其输入中的三维空间长宽高分别等于$x\_s$$y\_s$$z\_s$, 其输入输出箱子集合分别为${B_h}$$x\_stri{p_h}$, 如果${B_i}$${B_h}$的子集, 且$x\_stri{p_h}$${B_i}$的子集, 则该纪录是类似纪录, 此时直接以$x\_stri{p_h}$作为求解结果.

      2. 树搜索${\rm{TrS \_Entity}}$在搜索最优$entity$时, 在从某一节点向下搜索之前, 首先计算当前$entity$不可利用空间(即容器中所有$layer$的母长方体体积和减去容器中所有$layer$中的所有箱子体积和)占容器体积的百分比, 再用1减去该百分比得到当前树分枝可得结果的填充率上限$fr\_UB$. 如果$fr\_UB$小于已找到的最优$entity$的填充率, 则不再沿该树分枝往下搜索, 从而减少计算时间.

    • 按照3.2部分的算法流程求解出的装载方案满足摆放方向约束(C1), 为了满足完全支撑约束(C2), 需要对MLTrS算法流程做如下调整.

      3. 在创建片$piece$时, 仅考虑箱子体积等于最小包围长方体体积的情况, 即片$piece$构成一个完整的长方体, 不存在缺角情况. 最小包围长方体和母长方体的区别在于: 母长方体是在片$piece$创建之前给定的长方体边界, 片$piece$的最小包围长方体体积小于等于其母长方体体积.

      4. 树搜索${\rm{TrS \_Entity}}$在搜索最优$entity$时, 仅创建$yz\_layer$$xz\_layer$两种$layer$, 不创建$xy\_layer$, 因此${\rm{TrS \_Entity}}$在考虑完全支撑时由三叉树变成了二叉树.

      5. 在创建$x\_strip$($y\_strip$)时, 以所有箱子与$x\_strip$($y\_strip$)母长方体的上表面接触面的最大正交内接长方形(即不超过接触面的边界, 且各边平行于容器的水平边的面积最大的长方形, 在此称之为$x\_strip$($y\_strip$)最大平顶长方形)面积最大为选优标准, 而不是以${\rm{Fr}} \left( {x\_strip} \right)$(${\rm{Fr}} \left( {y\_strip} \right)$)最大为选优标准. 当$x\_strip$($y\_strip$)放入相应$ xz\_$$layer$($yz\_layer$)时, 仅$x\_strip$($y\_strip$)的最大平顶长方形正上方的空间可以用于装载剩余的箱子.

      6. 在创建$z\_strip$时, 除最下方的$piece$外, 其他$piece$的下表面必须与其紧下方$piece$的上表面完全接触. 在生成所有$piece$后、尚未创建$z\_strip$时(不是一般性, 对所有$piece$, 令${\rm{XS}} \left( {piece} \right) \geqslant {\rm{YS}} \left( {piece} \right)$), 先将所有$piece$按照${\rm{XS}} \left( {piece} \right)$值降序排列, 对于${\rm{XS}} \left( {piece} \right)$相同的多个$piece$, 再将它们按${\rm{YS}} \left( {piece} \right)$值降序排列, 这样就得到一个新的$piece$列表. 在利用动态规划求解一维背包时, 就可以较为容易地剔除不满足完全支撑约束的解.

    • 本文MLTrS算法用C#语言实现, 实验程序运行计算机CPU为Intel Xeon E5 2660@2.20 GHz, 内存为16 GB, 操作系统为64位Windows 7 Ultimate版, 实验程序仅使用CPU的8个核中的一核. 本文的测试数据集来源于文献[9], 该测试数据集包括BR1-BR15共15个子集, 每个子集包含100个算例, 同一子集中每个算例包含的箱子种类数相同, BR1-BR15中箱子的种类数分别为从3、5、8、10、12、15、20、30、40、50、60、70、80、90、100, 问题由弱异构到强异构逐渐过渡, 能够很好地测试算法在不同复杂度装箱问题中的性能. 我们在用MLTrS运行算例时, 针对不同复杂度的算例给定不同的计算时间限制, 限定时间$T$计算公式为: 当仅考虑摆放方向约束(C1)时, 对于弱异构算例BR1-BR7, $T = $$ 600$, 对于强异构算例BR8-BR15, $T = 150*\sqrt N $, 当同时考虑摆放方向约束(C1)和完全支撑约束(C2)时, 对于弱异构算例BR1-BR7, $T = 500$, 对于强异构算例BR8-BR15, $T = 100*\sqrt N $, 其中$N$为算例的箱子种类数.

      许多研究者全部或部分测试了BR1-BR15. 其中组合启发式算法(CH)[16]、H_B算法[22]测试了BR1$\sim $BR7; A2算法[12]测试了BR8$\sim $BR15; GA_GB算法[15]、贪心随机自适应搜索算法(GRASP)[23]、混合模拟退火算法(HSA)[21]、maximal-space算法[24]、基于整数拆分的树搜索算法(CLTRS)[7]、FDA算法[11]、多层启发式搜索算法(MLHS)[31]测试了BR1$\sim $BR15全部实例.

      上述算法全部满足C1约束, 部分满足C2约束, 算法的计算结果直接来自于相应文献. 表1列出了这些算法与本文MLTrS算法对BR1-BR7的计算结果, 表1中所有数据表示每个算法针对一类实例所得到的平均填充率(%).

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

      算法约束填充率(%)
      BR1BR2BR3BR4BR5BR6BR7Mean
      GA_GB[15]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

      表1可以看出, 针对BR1-BR7这7组弱异构算例, MLTrS无论在满足C1约束还是在同时满足C1和C2约束前提下, 都要弱于现有基于Block building构造方式的算法如CLTRS[7]、MLHS[31], 从文献[32]和[33]和本文的算例测试结果来看, 基于Wall-building构造方式的算法对弱异构问题的求解性能弱于基于Block building构造方式的算法. 接下来看一看本文算法对强异构算例的测试结果. 表2列出了各个算法对BR8-BR15的计算结果, 表2中所有数据表示每个算法针对一类实例所得到的平均填充率(%).

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

      算法约束填充率(%)
      BR8BR9BR10BR11BR12BR13BR14BR15Mean
      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

      表2可以看出, 在同时满足C1和C2约束的前提下, 在箱子种类数在60种以上时, 填充率超过了目前已知的所有算法. 在同时满足C1和C2约束的前提下, 与CLTRS[7]、MLHS[31]算法的对比如下: 当箱子种类数为70时, MLTrS填充率分别高1.7%和0.62%; 当箱子种类数为80时, MLTrS填充率分别高2.05%和1.04%; 当箱子种类数为90时, MLTrS填充率分别高2.52%和1.44%; 当箱子种类数为100时, MLTrS填充率分别高3.02%和2.05%; 另外针对BR8-BR15总平均值, MLTrS分别提高1.36%和0.35%. 在满足C1约束的前提下, MLTrS比CLTRS[7]提高0.73%, 略高于MLHS[31].

      由此可见, 本文算法在箱子种类数大于等于70时, 且要求满足摆放方向约束和完全支撑约束时, 填充率高于现有主流算法如CLTRS[7]、MLHS[31]等, 而且当箱子种类数越多, 本文算法求得的填充率比现有主流算法求得的填充率高得越多. 而对于箱子种类数小于70的算例, 本文算法要弱于CLTRS[7]和MLHS[31], 并且箱子种类数越少, 本文算法求得的填充率比现有主流算法求得的填充率低得越多. 这表明相对于现有主流算法如CLTRS[7]、MLHS[31]来说, 本文算法更适合求解箱子种类数较多的算例, 即强异构算例.

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

参考文献 (38)

目录

    /

    返回文章
    返回