| Citation: | ZHANG Changyong, LIU Jiayu. Multi-box container loading problem based on hybrid genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(5): 747-755. doi: 10.13700/j.bh.1001-5965.2020.0665(in Chinese)
|
Aviation multi-box container loading is an important link to realize fast, efficient and safe air cargo transportation. Aimed at the multi-box container loading optimization problem of multiple cargoes and container types under realistic constraints, a mathematical optimization model is built and a hybrid genetic algorithm is proposed to solve the cargo loading layout scheme, so as to make full use of the container loading space. The three-stage code is used to determine the loading order, cargo placement status and container number to generate the initial population randomly. The optimal solution protection strategy is added in the conventional selection operation, and the center of gravity, non-overlapping and load-bearing constraints are taken into account in the fitness function to evaluate the solution. The simulated annealing operator is added to avoid falling into the local optimum by using its jump property, which further improves the optimization effect. Through the comparison of examples, it shows that the proposed algorithm can still maintain a high volume utilization rate under various constraints, and can well solve the loading of strong and weak heterogeneous cargoes. The feasibility and applicability of the algorithm are further verified by using specific cargo data. The average volume utilization rate of four kinds of air container is higher than 82%, which shows that the proposed algorithm can effectively solve the cargo loading problem of regular and irregular multi-box containers, and has good engineering application value.
| [1] |
MAXENCE D, MANUEL I. Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems[J]. Informs Journal on Computing, 2020, 32(1): 101-119. doi: 10.1287/ijoc.2018.0880
|
| [2] |
刘胜, 沈大勇, 商秀芹, 等. 求解三维装箱问题的多层树搜索算法[J]. 自动化学报, 2020, 46(6): 1178-1187. https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO202006008.htm
LIU S, SHEN D Y, SHANG X Q, et al. A multi-layer tree search algorithm for 3D packing problem[J]. Journal of Automatica Sinica, 2020, 46(6): 1178-1187(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO202006008.htm
|
| [3] |
LIU S, TAN W, XU Z, et al. A tree search algorithm for the container loading problem[J]. Computers & Industrial Engineering, 2014, 75: 20-30.
|
| [4] |
ALINE A S, FRANKLINA M B, TOLEDO J, et al. Irregular packing problems: A review of mathematical models[J]. European Journal of Operational Research, 2020, 282(3): 802-822.
|
| [5] |
何琨, 黄文奇. 基于动作空间的三维装箱问题的确定性高效率求解算法[J]. 计算机科学, 2014, 37(8): 1786-1793. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201408013.htm
HE K, HUANG W Q. Deterministic and efficient algorithm for 3D bin packing problem based on action space[J]. Computer Science, 2014, 37(8): 1786-1793(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201408013.htm
|
| [6] |
何琨, 黄文齐, 胡骞. 基于动作空间的求解三维矩形装箱问题的穴度算法[J]. 计算机科学, 2010, 37(10): 181-183. doi: 10.3969/j.issn.1002-137X.2010.10.042
HE K, HUANG W Q, HU Q. Hole size algorithm for 3D rectangular packing problem based on action space[J]. Computer Science, 2010, 37(10): 181-183(in Chinese). doi: 10.3969/j.issn.1002-137X.2010.10.042
|
| [7] |
张长勇, 翟一鸣. 基于改进遗传算法的航空集装箱装载问题研究[J]. 北京航空航天大学学报, 2021, 47(7): 1345-1352. doi: 10.13700/j.bh.1001-5965.2020.0197
ZHANG C Y, ZHAI Y M. Research on air container loading problem based on improved genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(7): 1345-1352(in Chinese). doi: 10.13700/j.bh.1001-5965.2020.0197
|
| [8] |
张钧, 贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39. doi: 10.3778/j.issn.1002-8331.1902-0127
ZHANG J, HE K T. Hybrid genetic simulated annealing algorithm for 3D bin packing problem[J]. Computer Engineering and Applications, 2019, 55(14): 32-39(in Chinese). doi: 10.3778/j.issn.1002-8331.1902-0127
|
| [9] |
雷定猷, 洪舒华, 张英贵. 集装箱轻重货物混合平衡装载模型与算法[J]. 计算机工程与应用, 2020, 56(8): 233-240. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202008035.htm
LEI D Y, HONG S H, ZHANG Y G. Mixed balanced loading model and algorithm for heavy and heavy containers[J]. Computer Engineering and Applications, 2020, 56(8): 233-240(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202008035.htm
|
| [10] |
张德富, 彭煜, 张丽丽. 求解三维装箱问题的多层启发式搜索算法[J]. 计算机学报, 2012, 35(12): 2553-2561. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201212011.htm
ZHANG D F, PENG Y, ZHANG L L. A multi-layer heuristic search algorithm for three-dimensional packing problem[J]. Chinese Journal of Computers, 2012, 35(12): 2553-2561(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201212011.htm
|
| [11] |
靳志宏, 兰辉, 郭贝贝. 基于现实约束的集装箱配载优化及可视化[J]. 系统工程理论与实践, 2010, 30(9): 1722-1728. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201009028.htm
JIN Z H, LAN H, GUO B B. Container stowage optimization and visualization based on realistic constraints[J]. System Engineering Theory and Practice, 2010, 30(9): 1722-1728(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201009028.htm
|
| [12] |
那日萨, 韩琪玮, 林正奎. 三维多箱异构货物装载优化及其可视化[J]. 运筹与管理, 2015, 24(4): 76-82. doi: 10.3969/j.issn.1007-3221.2015.04.011
NA R S, HAN Q W, LIN Z K. Optimization and visualization of 3D multi container heterogeneous cargo loading[J]. Operations Research and Management Science, 2015, 24(4): 76-82(in Chinese). doi: 10.3969/j.issn.1007-3221.2015.04.011
|
| [13] |
刘嘉敏, 董宗然, 马广焜. 基于禁忌搜索算法求解集装箱装载问题[J]. 沈阳工业大学学报, 2009, 31(2): 212-216. doi: 10.3969/j.issn.1000-1646.2009.02.021
LIU J M, DONG Z R, MA G K. Container loading problem based on tabu search algorithm[J]. Journal of Shenyang University of Technology, 2009, 31(2): 212-216(in Chinese). doi: 10.3969/j.issn.1000-1646.2009.02.021
|
| [14] |
卜雷, 尹传忠, 蒲云. 集装箱运输多箱三维装载优化问题的遗传算法[J]. 铁道学报, 2004, 26(2): 21-25. doi: 10.3321/j.issn:1001-8360.2004.02.004
BU L, YIN C Z, PU Y. Genetic algorithm for multi container three dimensional loading optimization problem[J]. Journal of the China Railway Society, 2004, 26(2): 21-25(in Chinese). doi: 10.3321/j.issn:1001-8360.2004.02.004
|
| [15] |
MAURO D, FABIO F, MANUEL I. A branch-and-price algorithm for the temporal bin packing problem[J]. Computers and Operations Research, 2020, 114: 1-16.
|
| [16] |
PISINGER D. Heuristics for the container loading problem[J]. European Journal of Operational Research, 2002, 141(2): 382-392. doi: 10.1016/S0377-2217(02)00132-7
|
| [17] |
BISCHOFF E E, RATCLIFF M S W. Issues in the development of approaches to container loading[J]. Omega, 1995, 23(4): 377-390. doi: 10.1016/0305-0483(95)00015-G
|
| [18] |
PARREÑO F, ALVAREZ-VALDES R, TAMARIT J M, et al. A maximal-space algorithm for the container loading problem[J]. Informs Journal on Computing, 2008, 20(3): 412-422. doi: 10.1287/ijoc.1070.0254
|
Figures(6) / Tables(4)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn
Supported by:
Beijing Renhe Information Technology Co., Ltd.
DownLoad:
