-
摘要:
航空多箱型集装箱装载是实现快速、高效、安全航空货物运输的重要环节。针对现实约束条件下多种货物和箱型的集装箱多箱装载优化问题，搭建数学优化模型，提出一种求解货物装载布局方案的混合遗传算法，以达到充分利用集装箱装载空间的目的。采用三段式编码确定货物装载顺序、货物放置状态及集装箱编号，随机产生初始种群；在常规选择操作中加入最佳个体保护策略，并将重心、不重叠、承重约束考虑到适应度函数中，以此来评价解的优劣；加入模拟退火算子，用其突跳性避免遗传陷入局部最优的情况，进一步提高优化效果。通过算例对比表明，所提算法在满足多种约束条件下仍能保持较高的体积利用率，能够很好地解决强弱异构货物的装载；采用具体货物数据进一步验证算法的可行性与适用性，4种航空集装箱的平均体积利用率高于82%，表明所提算法能够有效解决规则和不规则多箱型集装箱的货物装载问题，具有较好的工程应用价值。
Abstract: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 算法对比结果
Table 1. Algorithm comparison results
算例 体积利用率/% MS算法 MBL算法 本文算法 BR1 79.96 89.92 91.15 BR2 79.30 90.64 91.92 BR3 80.54 90.67 91.98 BR4 78.63 91.46 92.65 BR5 78.74 91.70 93.05 BR6 78.11 90.87 92.07 BR7 75.92 90.31 91.20 BR8 74.90 90.07 90.85 BR9 74.23 89.87 90.13 BR10 73.06 89.45 90.07 BR11 71.79 89.13 89.88 BR12 70.45 88.95 89.23 BR13 70.21 89.33 89.04 BR14 69.61 89.05 88.96 BR15 69.32 88.73 88.84 
下载: 导出CSV
表 2 航空集装箱参数
Table 2. Air container parameters
集装箱类型 外型及尺寸 容量/m3 可载质量/kg AMA 
17.6 6 444 AKE 
4.3 1 488 AAU 
14.3 4 271 AMF 
14.6 4 705
下载: 导出CSV
表 3 航空货物信息
Table 3. Air cargo information
货号 长/cm 宽/cm 高/cm 放置状态 质量/kg 1 99 60 36 2种 32.5 2 104 54 59 6种 47.3 3 30 53 50 2种 21.6 4 65 57 78 6种 29.3 
430 40 50 47 6种 17.6
下载: 导出CSV
表 4 计算结果
Table 4. Calculation results
集装箱类型 序号 体积利用率/% 装载件数 装载总体积/m3 AMA 1 82.17 52 14.46 2 83.49 56 14.69 3 83.26 55 14.65 AAU 1 82.10 67 11.74 2 82.56 68 11.81 AMF 1 82.96 92 12.11 AKE 1 84.37 40 3.63
下载: 导出CSV
-
[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.htmLIU 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.htmHE 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.042HE 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.0197ZHANG 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-0127ZHANG 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.htmLEI 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.htmZHANG 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.htmJIN 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.011NA 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.021LIU 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.004BU 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 -
下载:
点击查看大图
计量
- 文章访问数: 521
- HTML全文浏览量: 140
- PDF下载量: 248
- 被引次数: 0
