2.765

2022影响因子

(CJCR)

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

留言板

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

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

基于多元优化算法的三维装箱问题的研究

李孙寸 施心陵 张松海 董易 高莲

李孙寸, 施心陵, 张松海, 董易, 高莲. 基于多元优化算法的三维装箱问题的研究. 自动化学报, 2018, 44(1): 106-115. doi: 10.16383/j.aas.2018.c160381
引用本文: 李孙寸, 施心陵, 张松海, 董易, 高莲. 基于多元优化算法的三维装箱问题的研究. 自动化学报, 2018, 44(1): 106-115. doi: 10.16383/j.aas.2018.c160381
LI Sun-Cun, SHI Xin-Ling, ZHANG Song-Hai, DONG Yi, GAO Lian. Multi-variant Optimization Algorithm for Three Dimensional Container Loading Problem. ACTA AUTOMATICA SINICA, 2018, 44(1): 106-115. doi: 10.16383/j.aas.2018.c160381
Citation: LI Sun-Cun, SHI Xin-Ling, ZHANG Song-Hai, DONG Yi, GAO Lian. Multi-variant Optimization Algorithm for Three Dimensional Container Loading Problem. ACTA AUTOMATICA SINICA, 2018, 44(1): 106-115. doi: 10.16383/j.aas.2018.c160381

基于多元优化算法的三维装箱问题的研究

doi: 10.16383/j.aas.2018.c160381
基金项目: 

云南省自然科学基金 2013FA008

国家自然科学基金 61561049

国家自然科学基金 61261007

详细信息
    作者简介:

    施心陵  云南大学信息学院教授.主要研究方向为智能优化算法, 自适应信号处理与信息系统, 医学电子学.E-mail:xlshi@ynu.edu.cn

    张松海  云南大学信息学院硕士研究生.主要研究方向为智能优化算法, 电网可靠性分析.E-mail:hai_zs@sina.com

    董易  云南大学信息学博士研究生.主要研究方向为智能优化算法及其应用.E-mail:yeo003@163.com

    高莲  博士, 云南大学信息学院讲师.主要研究方向为生物医学信号处理.E-mail:yanglianbao@yunneidongli.com

    通讯作者:

    李孙寸  云南大学信息学院硕士研究生.主要研究方向为智能算法及其应用.本文通信作者.E-mail:lisuncun@outlook.com

Multi-variant Optimization Algorithm for Three Dimensional Container Loading Problem

Funds: 

Natural Science Foundation of Yunnan Province 2013FA008

National Natural Science Foundation of China 61561049

National Natural Science Foundation of China 61261007

More Information
    Author Bio:

     Professor at the School of Information Science and Engineering, Yunnan University. His research interest covers intelligent algorithms and the application of intelligent algorithms, adaptive signal processing and information systems, medical electronics

     Master student at the School of Information Science and Engineering, Yunnan University. His research interest covers intelligent algorithms and power system reliability analysis

     Ph. D. candidate at the School of Information Science and Engineering, Yunnan University. His research interest covers intelligent algorithms and its application

     Ph.D., lecturer at the School of Information Science and Engineering, Yunnan University. Her main research interest is biomedical signal processing

    Corresponding author: LI Sun-Cun  Master student at the School of Information Science and Engineering, Yunnan University. Her research interest covers intelligent algorithms and its application. Corresponding author of this paper
  • 摘要: 用多元优化算法(Multi-variant optimization algorithm,MOA)实现三维装箱问题的求解.算法通过随机放置和局部调整从而逐步逼近最优解.随机放置是将随机选择的几个箱子装入容器中;局部调整是根据目标函数值对随机放置容器的箱子序列作局部调整优化;通过递推的随机放置和局部调整优化,目标函数值逐步逼近最优值,从而获得一个较为理想的三维装箱方案.算法通过对BR1~BR10共1000组三维装箱问题测试实例的测试仿真,得到理想的装箱效果,说明用多元优化算法实现三维装箱问题的有效性和可行性.
    1)  本文责任编委 王红卫
  • 图  1  空间的分割

    Fig.  1  Space division

    图  2  箱子的摆放方式

    Fig.  2  The placement method of box

    图  3  空间合并方式

    Fig.  3  The merging method of residual space

    图  4  MOA数据结构图

    Fig.  4  The data structure diagram of MOA

    图  5  测试寻优过程图

    Fig.  5  The test optimization graph

    图  6  测试寻优结果图

    Fig.  6  The result of test results

    图  7  MOA实现装箱问题过程中填充率变化图

    Fig.  7  The filling rate variation diagram of packing problem with MOA

    表  1  BR1-1待装箱子的三维值及数量

    Table  1  The specification and quantity of BR1-1

    长(cm) 宽(cm) 高(cm) 数量
    108 76 30 40
    110 43 25 33
    92 81 55 39
    下载: 导出CSV

    表  2  某次实验得到的填充率的变化关系表

    Table  2  The change table of filling rate obtained from an experiment

    批次 1/(调整优化后) 2/(调整优化后) 3/(调整优化后) 4/(调整优化后) 5/(调整优化后)
    容器填充率 0.2749/(0.3591) 0.5495/(0.5968) 0.7324/(0.7936) 0.8926/(0.9065) 0.9625/(0.9625)
    下载: 导出CSV

    表  3  各种算法的装箱效果比较(1 ~ 500组)

    Table  3  Comparison of packing effects of various (groups 1 ~ 500) algorithms

    测试实例 约束 填充率(%)
    BR1 BR2 BR3 BR4 BR5
    箱子的种类数 3 5 8 10 12
    H_BR[3] C1 and C2 83.79 84.44 83.94 83.71 83.80
    GA_GB[6] C1 and C2 85.80 87.26 88.10 88.04 87.86
    TS_BG[7] C1 and C2 87.81 89.40 90.48 90.63 90.73
    GRASP[12] C1 93.52 93.77 93.58 93.05 92.34
    Maximal-space[15] C1 93.85 94.22 94.25 94.09 93.87
    HSA[17] C1 and C2 93.81 93.94 93.86 93.57 93.22
    CLTRS[18] C1 95.05 95.43 95.47 95.18 95.00
    C1 and C2 94.51 94.73 94.73 94.41 94.13
    MLHS[19] C1 94.92 95.48 95.69 95.53 95.44
    C1 and C2 94.49 94.89 95.20 94.94 94.78
    VNS[24] C1 94.93 95.19 94.99 94.71 94.33
    FDA[25] C1 92.92 93.93 93.71 93.68 93.73
    MOA C1 and C2 95.62 94.68 94.41 94.23 94.03
    下载: 导出CSV

    表  4  各种算法的装箱效果比较(501 ~ 1 000)

    Table  4  Comparison of packing effects of various (groups 501 ~ 1 000) algorithms

    测试实例 约束 填充率(%)
    BR6 BR7 BR8 BR9 BR10 平均
    箱子的种类数 15 20 30 40 50
    H_BR[3] C1 and C2 82.44 82.01 80.10 78.03 76.53 81.88
    GA_GB[6] C1 and C2 87.85 87.68 87.52 86.46 85.53 87.21
    TS_BG[7] C1 and C2 92.72 90.65 87.11 85.76 84.73 89.00
    GRASP[12] C1 91.72 90.55 86.13 85.08 84.21 90.40
    Maximal-space[15] C1 93.52 92.94 91.02 90.46 89.87 92.81
    HSA[17] C1 and C2 92.72 91.99 90.56 89.70 89.06 92.24
    CLTRS[18] C1 94.79 94.24 93.70 93.44 93.09 94.54
    C1 and C2 93.85 93.20 92.26 91.48 90.86 93.42
    MLHS[19] C1 95.38 94.95 94.54 94.14 93.95 95.00
    C1 and C2 94.55 93.95 93.12 92.48 91.83 94.02
    VNS[24] C1 94.04 93.53 92.78 92.19 91.92 93.86
    FDA[25] C1 93.63 93.14 92.92 92.49 92.24 93.23
    MOA C1 and C2 94.56 93.27 93.09 91.52 91.00 93.64
    下载: 导出CSV

    表  5  元优化算法实现三维装箱问题时的一些测试细节

    Table  5  Some test details of MOA for 3D packing problem

    测试实例 约束 运行时间(s) 填充率(%)
    Minimum Maximum Average Minimum Maximum Average
    BR1 3 1.83 114.66 28.84 91.04 98.31 95.62
    BR2 5 2.41 57.89 26.78 89.18 97.23 94.68
    BR3 8 3.42 191.23 86.35 90.60 96.97 94.41
    BR4 10 1.26 274.91 105.67 88.82 96.04 94.23
    BR5 12 7.50 219.01 110.63 89.17 97.45 94.03
    BR6 15 5.83 495.02 265.74 87.36 96.56 94.56
    BR7 20 14.61 811.50 384.38 5.82 95.44 93.27
    BR8 30 30.82 1 312.80 560.21 84.61 95.17 93.09
    BR9 40 33.40 1 798.75 866.08 84.69 94.07 91.52
    BR10 50 54.52 2 401.94 1 380.62 82.27 93.84 91.00
    Mean 19.30 15.56 767.77 381.53 87.36 96.11 93.64
    下载: 导出CSV
  • [1] Dyckhoff H, Finke U. Cutting and Packing in Production and Distribution. Heidelberg: Physica-Verlag, 1992.
    [2] Ngoi B K A, Tay M L, Chua E S. Applying spatial representation techniques to the container packing problem. International Journal of Production Research, 1994, 32(1):111-123 doi: 10.1080/00207549408956919
    [3] 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
    [4] Davies A P, Bischoff E E. Weight distribution considerations in container loading. European Journal of Operational Research, 1999, 114(3):509-527 doi: 10.1016/S0377-2217(98)00139-8
    [5] Sixt M. Dreidimensionale Packprobleme. Losungsverfahren Basierend auf den Meta-Heuristiken Simulated Annealing und Tabu-Suche. Frankfurt am Main: Europaischer Verlag der Wissenschaften, 1996.
    [6] 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/itor.1997.4.issue-5-6
    [7] Bortfeldt A, Gehring H. A tabu search algorithm for weakly heterogeneous container loading problems. OR Spectrum, 1998, 20:237-250 http://citeseerx.ist.psu.edu/showciting?cid=7382720
    [8] 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
    [9] 何大勇, 查建中, 姜义东.遗传算法求解复杂集装箱装载问题方法研究.软件学报, 2001, 12(9):1380-1385 http://d.old.wanfangdata.com.cn/Periodical/rjxb200109016

    He Da-Yong, Zha Jian-Zhong, Jiang Yi-Dong. Research on solution to complex container-loading problem based on genetic algorithm. Journal of Software, 2001, 12(9):1380-1385 http://d.old.wanfangdata.com.cn/Periodical/rjxb200109016
    [10] 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
    [11] 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
    [12] 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
    [13] Zhang D F, Li X. A personified annealing algorithm for circles packing problem. Acta Automatica Sinica, 2005, 31(4):590-595 http://www.oalib.com/paper/1515911
    [14] 张德富, 魏丽军, 陈青山, 陈火旺.三维装箱问题的组合启发式算法.软件学报, 2007, 18(9):2083-2089 http://d.old.wanfangdata.com.cn/Periodical/rjxb200709003

    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 http://d.old.wanfangdata.com.cn/Periodical/rjxb200709003
    [15] Parrenóo F, Alvarez-Valdes R, Oliveira J F, Tamarit J M. A maximal space-algorithm for the container loading problem. INFORMS Journal on Computing, 2008, 20(3):412-422 doi: 10.1287/ijoc.1070.0254
    [16] Huang W Q, He K. A caving degree approach for the single container loading problem. European Journal of Operational Research, 2009, 196(1):93-101 doi: 10.1016/j.ejor.2008.02.024
    [17] 张德富, 彭煜, 朱文兴, 陈火旺.求解三维装箱问题的混合模拟退火算法.计算机学报, 2009, 32(11):2147-2156 https://mall.cnki.net/lunwen-1013317436.html

    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 https://mall.cnki.net/lunwen-1013317436.html
    [18] 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
    [19] 张德富, 彭煜, 张丽丽.求解三维装箱问题的多层启发式搜索算法.计算机学报, 2012, 35(12):2553-2516 http://www.doc88.com/p-9119979416265.html

    Zhang De-Fu, Peng Yu, Zhang Li-Li. A multi-layer heuristic search algorithm for three dimensional container loading problem. Chinese Journal of Computers, 2012, 35(12):2553-2561 http://www.doc88.com/p-9119979416265.html
    [20] 刘胜, 朱凤华, 吕宜生, 李元涛.求解三维装箱问题的启发式正交二叉树搜索算法.计算机学报, 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
    [21] 张雅舰, 刘勇, 谢松江.一种求解装箱问题的改进遗传算法.控制工程, 2016, 23(3):327-331 http://d.old.wanfangdata.com.cn/Periodical/jczdh201603004

    Zhang Ya-Jian, Liu Yong, Xie Song-Jiang. An improved genetic algorithm for bin-packing problem. Control Engineering of China, 2016, 23(3):327-331 http://d.old.wanfangdata.com.cn/Periodical/jczdh201603004
    [22] 王岩, 潘卫平, 张俊晖.单一尺寸长方体三维装箱问题的一种求解算法.包装工程, 2015, 36(11):96-99 http://www.oalib.com/paper/4304490

    Wang Yan, Pan Wei-Ping, Zhang Jun-Hui. An algorithm for solving the problem of three-dimensional packing of single-sized cuboids. Packaging Engineering, 2015, 36(11):96-99 http://www.oalib.com/paper/4304490
    [23] 任岳淼, 陈贤富, 刘斌.面向梯形箱子的三维装箱问题算法研究.微型机与应用, 2015, 34(9):18-21, 25 https://www.wenkuxiazai.com/doc/a27b4ff0580216fc710afdc0.html

    Ren Yue-Miao, Chen Xian-Fu, Liu Bin. Study on algorithm of three-dimensional bin packing problem for trapezoidal bin. Microcomputer and Its Applications, 2015, 34(9):18-21, 25 https://www.wenkuxiazai.com/doc/a27b4ff0580216fc710afdc0.html
    [24] Parreño F, Alvarez-Valdes R, Oliveira J F, Tamarit J M. Neighborhood structures for the container loading problem:a VNS implementation. Journal of Heuristics, 2010, 16(1):1-22 doi: 10.1007/s10732-008-9081-3
    [25] He K, Huang W Q. An efficient placement heuristic for three-dimensional rectangular packing. Computers and Operations Research, 2011, 38(1):227-233 doi: 10.1016/j.cor.2010.04.015
    [26] 游伟, 雷定猷, 朱向.三维装箱问题的偏随机密钥混合遗传算法.计算机工程与应用, 2014, 50(22):265-270 doi: 10.3778/j.issn.1002-8331.1401-0284

    You Wei, Lei Ding-You, Zhu Xiang. Biased random-key hybrid genetic algorithm for three-dimensional loading problem. Computer Engineering and Applications, 2014, 50(22):265-270 doi: 10.3778/j.issn.1002-8331.1401-0284
    [27] 张莹, 刘二超, 戚铭尧.考虑支撑面约束的三维装箱问题快速求解方法.交通运输系统工程与信息, 2014, 14(2):192-198 http://c.g.wanfangdata.com.cn/periodical/jtysxtgcyxx/2014-2.aspx

    Zhang Ying, Liu Er-Chao, Qi Ming-Yao. Quick algorithm for the three-dimensional bin packing problem with support surface constraints. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(2):192-198 http://c.g.wanfangdata.com.cn/periodical/jtysxtgcyxx/2014-2.aspx
    [28] 何琨, 黄文奇.基于动作空间的三维装箱问题的确定性高效率求解算法.计算机学报, 2014, 37(8):1786-1793 http://www.cnki.com.cn/Article/CJFDTOTAL-TDXB201309002.htm

    He Kun, Huang Wen-Qi. An action space based deterministic efficient algorithm for solving the three-dimensional container loading. Chinese Journal of Computers, 2014, 37(8):1786-1793 http://www.cnki.com.cn/Article/CJFDTOTAL-TDXB201309002.htm
    [29] 夏成仁.关于最优化原理的教学.安庆师范学院学报(自然科学版), 2003, 9(2):93-95 http://www.bookask.com/book/4550.html

    Xia Cheng-Ren. Methodology of teaching the principal of optimality. Journal of Anqing Teachers College (Natural Science), 2003, 9(2):93-95 http://www.bookask.com/book/4550.html
    [30] 李宝磊, 施心陵, 苟常兴, 吕丹桔, 安镇宙, 张榆锋.多元优化算法及其收敛性分析.自动化学报, 2015, 41(5):949-959 http://www.aas.net.cn/CN/abstract/abstract18669.shtml

    Li Bao-Lei, Shi Xin-Ling, Gou Chang-Xing, Lv Dan-Ju, An Zhen-Zhou, Zhang Yu-Feng. Multivariant optimization algorithm and its convergence analysis. Acta Automatica Sinica, 2015, 41(5):949-959 http://www.aas.net.cn/CN/abstract/abstract18669.shtml
  • 加载中
图(7) / 表(5)
计量
  • 文章访问数:  2729
  • HTML全文浏览量:  1722
  • PDF下载量:  1085
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-05-09
  • 录用日期:  2017-02-03
  • 刊出日期:  2018-01-20

目录

    /

    返回文章
    返回