Multi-variant Optimization Algorithm for Three Dimensional Container Loading Problem
-
摘要: 用多元优化算法（Multi-variant optimization algorithm，MOA）实现三维装箱问题的求解.算法通过随机放置和局部调整从而逐步逼近最优解.随机放置是将随机选择的几个箱子装入容器中；局部调整是根据目标函数值对随机放置容器的箱子序列作局部调整优化；通过递推的随机放置和局部调整优化，目标函数值逐步逼近最优值，从而获得一个较为理想的三维装箱方案.算法通过对BR1~BR10共1000组三维装箱问题测试实例的测试仿真，得到理想的装箱效果，说明用多元优化算法实现三维装箱问题的有效性和可行性.Abstract: This paper investigates that three-dimensional container loading problem is solved by the Multi-variant optimization algorithm. The Multi-variant optimization algorithm applied random placement and partial adjustment to gradually approximate the optimal solution. The random placement denotes that several boxes of randomly selected are put into the container; the partial adjustment indicates that the sequence of the boxes in the container of random placement are topically adjusted and optimized with objective function value. Then, the objective function value will gradually approximate the optimal value by recursively random replacement, partial adjustment and optimization, and we acquire a desirable three-dimensional container loading program. In order to verify the effectiveness and practicability of three-dimensional container problem with the multi-variant optimization algorithm, 1000 groups of three-dimensional container loading problems that vary from BR1-BR10 are tested in this paper and acquire desirable 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/rjxb200109016He 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/rjxb200709003Zhang 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.htmlZhang 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.htmlZhang 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.01530Liu 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/jczdh201603004Zhang 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/4304490Wang 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.htmlRen 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-0284You 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.aspxZhang 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.htmHe 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.htmlXia 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.shtmlLi 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)
计量
- 文章访问数: 2901
- HTML全文浏览量: 2131
- PDF下载量: 1131
- 被引次数: 0
