启发式算法是在直观、经验的基础上抽象化后得到的算法，适合解决不是很复杂的装箱问题。根据实际约束及实现目标的不同，****们提出了多种启发式的求解方法。Maxence和Manuel[2]基于改进的最佳拟合启发式算法，用于生成将初始可行方案装载到箱中；刘胜等[3-4]将树搜索的思想用于装箱，使用箱子、片、条、层、实体的顺序进行装载；Aline等[5]通过构建数学模型，将一组不规则和规则的块分配给较大的矩形或不规则容器，最大程度地减少了材料或空间的浪费；Mauro等[6]研究了经典装箱问题的扩展，提出一种综合不同方法的整体算法以找到最小数量的箱来装载所有物品；Yu和Amarnath[7]提出曲折排序的启发式算法，构造了可行性保留规则以确保每个盒子的分配；何琨等[8-10]利用占角策略，通过占角动作提出了一种占角空间最小的穴度算法。
遗传算法作为鲁棒搜索算法，不依赖问题的本质，更适合解决复杂问题得到近似最优解。崔会芬等[11]在遗传运算中使用排序选择方法和部分交叉来对遗传进行改进，在考虑部分约束下提高了集装箱的装载效率，但未考虑货物承重性、装箱顺序等因素；张钧和贺可太[12]利用混合遗传、模拟退火2种算法结合求解模型，提出两段式的编码方式充分优化空间利用率，但是采用模拟退火法确定适应度，运行时间较长；Menghani和Guha[13]在考虑多种实际约束的情况下将货物合理装进多个容器中，但其搜索速度与收敛性很容易受到初始化条件的影响；代爱民[14]考虑了货物装箱的及时性和顺序，但并未考虑货物的承载能力、重心分布等约束；于明正等[15]提出基于2个搜索方向的遗传层，分别搜索可行方案的广度和深度以提高优化效率，但其约束条件考虑较少，不能满足实际应用需要。
综上所述，目前大多数算法求解装箱问题时，未考虑货物装载顺序约束的离线装载，以及垛形稳定性等实际装载过程中的现实约束，无法保证货物运输过程中的安全性。另外，对于装箱问题的研究较多集中在规则集装箱的装载上，对不规则集装箱的求解问题研究较少。
本文以航空货运集装箱装载为研究背景，考虑实际装载过程中的诸多现实约束，在此基础上搭建数学模型，提出一种改进遗传算法，以集装箱空间利用率为优化目标，结合稳定性、重心及支撑限制约束构建合理的适应度函数，并加入适应度尺度变换、最优解保存策略以进一步提高优化效果。采用异构性由弱到强的测试算例及3组具体货物装载数据进行实验，验证了算法的有效性与实用性。根据算法输出结果开发可视化程序，为工程应用创造了条件。
1 问题描述 1.1 符号说明及数学模型 以集装箱左后下点为原点，底面为XY平面，垂直底面向上为Z轴建立坐标系。ηi为0/1变量，若货物i已装入则ηi=1，若未装入则ηi=0；wi、hi、di、vi、mi和[gxi, gyi, gzi]分别为货物i的长、宽、高、体积、质量和重心坐标；Ei和Fi分别为货物i所承受的重量和最大承载力；Bi和Ci分别为货物i的顺序号和码放序号；(xi, yi, zi)、(x′i, y′i, z′i)分别为货物i左后下、右前上角坐标；[conx1, conx2]、[cony1, cony2]、[0, conz]分别为x、y、z方向的重心安全区间；V和M分别为集装箱的体积和载重量。
给定航空集装箱和一批待装载货物B={b1, b2, …, bn}，装载要求为：在满足实际约束的情况下，得到使集装箱空间利用率最大的布局方案。
据此，目标函数如下：
 | (1) |
在实际装载过程中存在很多现实问题，假设条件可以简化优化模型，降低装箱问题的复杂度，因此对于假设条件的减少是非常必要的。具体讨论的假设条件围绕以下几点：①货物形状均为长方体；②货物在最大承重范围之内可接受多层装载；③货物重心为其几何中心；④不考虑货物在装载过程中出现的挤压变形等。
1.2 约束条件处理 1) 质量与体积约束。装载货物的总质量、总体积不能超过实际所允许的最大装载质量与体积，即
 | (2) |
 | (3) |
2) 货物装载顺序约束。考虑货物装箱过程中的顺序装载，货物按当前到来的顺序进行装载，即
 | (4) |
3) 不重叠约束。货物之间不能重叠，即
 | (5) |
4) 稳定性约束。保证垛形稳定，货物不可悬空，其下需有一半以上的面积被支撑，即货物i的接触率Ti满足：
 | (6) |
5) 支撑限制约束。在实际装载过程中，要考虑到货物的承载能力，避免出现货物毁坏的状况，即
 | (7) |
式中：
 |
 |
6) 重心约束。为了保证运输货物的安全性，要求其重心必须在一定的范围内，即
 | (8) |
1.3 拟人装载策略 采用不同的装载策略[16]会生成不同的装载方案，从而对集装箱的空间利用率产生影响，因此要选用合适的装载方法。采用可放置点构建、排序、首个匹配、参考线引入的拟人装载策略[17]对货物进行装载。在码放过程中，水平与垂直方向上引入2条参考线以引导货物放置过程，利用更新可放置点的方法来确定货物的放置位置。拟人装载策略流程如图 1所示。
 |
| 图 1 拟人装载策略流程 Fig. 1 Anthropomorphic loading strategy flowchart |
| 图选项 |
在该策略中，首先，将初始可放置点设为(0, 0, 0)，并将水平、垂直参考线初始化为0。然后，按照货物到来顺序依次装载货物，对每个货物判断可放置点是否满足装载条件，装载条件为该货物不能与集装箱及其他货物重叠，且满足x+wi≤Lx，z+di≤Lz，即不超过2条参考线，若不满足，通过水平参考线Lx执行不同的操作。最后，若当前货物找到了可以放置的位置，将其放在该位置，同步更新待装载货物与可放置点序列。算法结束时，输出货物装箱方案及空间利用率。
2 改进的遗传算法 遗传算法具有快速随机的全局搜索力，但收敛速度和局部搜索效果欠佳。为解决标准遗传算法过早收敛的问题，加入罚函数、适应度尺度变换、最优解保存策略来对其进行改进。
2.1 编码与解码 遗传算法的编码大多使用二进制编码，而应用在货物装箱这类问题上显然是不可行的。原因为：①货物坐标使用二进制表示，会出现复杂度随着货物数量的增加而呈指数增长，降低了算法的性能；②坐标的变化描述了待装载货物的位置变化，有可能会出现货物重叠的现象。
货物在集装箱中的装载包含3个要素：装箱顺序、放置状态与放置位置。本文研究的是将货物按照其码放顺序装入到集装箱中，故编码时仅考虑第2个因素，采用实数编码，货物的每种布局方案对应S=(S1, S2, …, Si, …, Sn)，S1~Sn为货物放置状态，分别用整数1, 2, 3, 4, 5, 6代表货物的6种放置状态(见图 2)。第3个因素在解码时完成，根据拟人装载策略实现解码操作。
 |
| 图 2 货物放置状态 Fig. 2 Cargo orientations |
| 图选项 |
2.2 解的不可行性与罚函数 惩罚是遗传算法解决受约束的优化问题的最常用办法，由于遗传操作可能会得到不可行的后代，加入惩罚项对违反约束的个体给予相应的惩罚，其本质是通过惩罚不可行的方案，把带约束的问题转换成无约束问题。综合考虑稳定性约束、支撑限制约束、重心约束，惩罚项如下。
保证垛形稳定，即满足稳定性约束：
 | (9) |
货物所载全部上层货物总重量小于其最大载重量，即满足支撑限制约束：
 | (10) |
垛形重心在合理的范围以内，即满足重心约束：
 | (11) |
 | (12) |
 | (13) |
记
 | (14) |
则式(9)~式(13)任何值为1，皆为不可行方案。
2.3 适应度尺度变换 研究目标是使集装箱空间利用率最大，即最小化集装箱的浪费空间，将适应度定义成空间利用率函数，如式(15)所示。为提高个体间竞争性，防止算法早熟，对其进行线性尺度变换，如式(16)所示。加入惩罚项后的评估函数如式(17)所示。
 | (15) |
 | (16) |
 | (17) |
式中：Fmin为F的最小值；Favg为F的平均值。
2.4 最优解保存策略 由于选择、交叉与变异具有随机性，可能会破坏评估值好的个体。为使最好的个体能够尽可能多地遗传到下一代，确保算法的全局收敛，采用最优解保存策略来实现优胜劣汰。通过设置参数δ=10%，确定被保留不需进行交叉、变异的个体。若上一代种群数为50，则通过计算评估值，将评估值前5的个体直接复制到下一代，减少了破坏最佳方案的可能性。
3 基于拟人装载策略的改进遗传算法 根据上述拟人装载策略和改进的遗传算法，设计了基于拟人装载策略的改进遗传算法，算法流程如图 3所示，步骤如下:
 |
| 图 3 改进遗传算法流程 Fig. 3 Improved genetic algorithm flowchart |
| 图选项 |
步骤1??将集装箱的型号、尺寸与货物的基本信息输入程序，设置改进遗传算法的相关参数。
步骤2?? 考虑到根据特定的排序规则定义初始种群的生成会导致优化结果受到限制，采用随机生成初始种群的方式对装载结果进行寻优。
步骤3?? 根据拟人装载策略实现解码操作，以实现货物的装箱。
步骤4 ??根据式(2)~式(5)判断是否满足质量、体积、货物装载顺序与不重叠约束，若满足，转步骤5；否则，转步骤10。
步骤5 ??根据式(16)，得到线性尺度变换后的适应度函数。
步骤6?? 根据式(9)~式(14)、式(17)计算加入稳定性约束、支撑限制约束、重心约束3项惩罚的评估函数。
步骤7?? 轮盘赌实现个体选择。
步骤8?? 判断个体是否直接成为下一代。若满足，直接复制到下一代中；若不满足，利用双点交叉、顺序逆转实现交叉与变异。
步骤9?? 将最优解保存策略与改进遗传算法得到的解结合起来，产生新一代种群。
步骤10?? 进行下一次循环，判断是否满足终止条件。若满足，输出最佳装载方案；若不满足，返回步骤8。
4 实验方案 采用同类三维装箱研究下的测试算例对本文算法进行性能测试，结合3组具体货物装载数据验证算法的实用性，并基于MATLAB实现装载效果的可视化。
在Visual Studio 2010环境下，计算机型号为Intel(R) Core(TM) i5-7200U CPU 2.50 GHz，操作系统为Windows 10。遗传算法参数设为：{种群规模，交叉，变异，终止条件}={50, 0.6, 0.1, 200}。
4.1 算例对比分析 与同类三维装箱研究用相同的测试算例进行比较验证，以证明本文算法的有效性和优越性。现有文献中大多是研究离线装箱问题，未考虑货物装载顺序约束，而本文研究的集装箱实时装载问题考虑了货物装箱的及时性和顺序，属于半在线装箱问题的研究范畴，两者不具有可比性。目前，仅发现文献[14]和本文属于同类装箱问题研究，故选取该文献中异构性由弱到强的算例进行实验。
表 1为文献[14]的混合免疫遗传算法与改进遗传算法的对比结果，对每组数据分别做5次测试，得到平均空间利用率。可以发现，当货物异构性逐渐增强时，算法的优化效果总体呈上升趋势。经过改进遗传算法进行装载优化后，异构性较强的无尺寸相同的货物装载算例也可以获得较高的空间利用率，分别为80.11%和84.47%，优于文献[14]应用的混合免疫遗传算法求解装载问题的结果。结果表明，本文算法在求解强异构货物装载问题时有明显的优势，有较好的优化效果。
表 1 算例测试结果对比 Table 1 Comparison of example test results
| 货物特征 | 编号 | 长 | 宽 | 高 | 平均空间利用率/% | |
| 混合免疫遗传算法 | 改进遗传算法 | |||||
| 2个尺寸相同 | 1 | 200 | 160 | 80~160 | 96.34 | 95.89 |
| 2 | 200 | 100~200 | 100 | 91.92 | 92.43 | |
| 3 | 160~320 | 160 | 100 | 87.71 | 88.26 | |
| 1个尺寸相同 | 4 | 200 | 100~200 | 50~100 | 86.20 | 89.13 |
| 5 | 140~280 | 140 | 50~100 | 83.20 | 86.56 | |
| 6 | 120~240 | 80~160 | 80 | 82.94 | 85.54 | |
| 无尺寸相同 | 7 | 200~300 | 160~240 | 80~120 | 82.16 | 84.47 |
| 8 | 200~400 | 160~320 | 80~160 | 72.75 | 80.11 | |
表选项
4.2 实例验证 通过4.1节算例对比分析可知，本文算法在求解集装箱实时装载问题中有一定的优越性。为验证改进遗传算法可以解决规则、不规则集装箱的货物装载问题，将算法应用于实际集装箱装载。选用在航空运输领域应用广泛的AMA、AKE集装箱作为待装载集装箱，其参数如表 2所示。从某航空公司获取实际货物数据进行验证，采集了3组不同批次的货物数据，先后输入算法中进行实验。其中，第1组为较大型货物，第2组为混合型货物，第3组为较小型货物。3个实验组组内货物基本信息如表 3所示。
表 2 集装箱参数 Table 2 Container parameters
| 箱型 | 尺寸/cm | 可载重量/kg | 适载机型 |
| AMA集装箱 | {w,h,d}={318,214,214} | 6 444 | 747F |
| AKE集装箱 | {w1,w2,h,d}={201,156,154,163} | 1 488 | 747、777、747F |
表选项
表 3 货物基本参数 Table 3 Basic cargo parameters
| 参数 | 第1组 | 第2组 | 第3组 |
| 平均长度/cm | 65.32 | 51.56 | 45.74 |
| 平均宽度/cm | 50.21 | 44.47 | 36.98 |
| 平均高度/cm | 57.96 | 52.53 | 46.32 |
| 平均质量/kg | 46.56 | 37.18 | 23.27 |
| 货物件数 | 50 | 100 | 150 |
表选项
基于算法的寻优过程，所考虑的约束条件较为全面，与实际工作环境相符合。将标准遗传算法与改进遗传算法进行对比，其中标准遗传算法由拟人装载策略结合改进前的遗传算法得到。2种算法独立运行20次，对比结果如表 4所示。结果表明，算法适用于解决规则、不规则集装箱的货物装箱问题，实用性较好，能满足实际工程需要。改进遗传算法所产生的方案有着较高的空间利用率，避免了不必要的空间浪费，能以较快的速度得到较为理想的装箱方案。究其原因，改进遗传算法加入罚函数、线性尺度变换、最优解保存策略后，算法的局部、全局寻优能力得到提高，能够更快速地找到最佳装载方案。
表 4 不同箱型2种算法的对比结果 Table 4 Comparison results of two algorithms for different container types
| 箱型 | 货物实验组 | 标准遗传算法 | 改进遗传算法 | |||||
| 平均空间利用率/% | 平均装载货物件数 | 平均运行时间/s | 平均空间利用率/% | 平均装载货物件数 | 平均运行时间/s | |||
| AMA集装箱 | 第1组 | 85.21 | 37 | 18.54 | 88.45 | 40 | 10.43 | |
| 第2组 | 85.89 | 75 | 29.37 | 89.89 | 80 | 19.65 | ||
| 第3组 | 86.75 | 104 | 33.41 | 90.97 | 110 | 27.56 | ||
| 平均 | 85.95 | 72 | 27.11 | 89.77 | 77 | 19.21 | ||
| AKE集装箱 | 第1组 | 84.66 | 22 | 12.53 | 87.67 | 25 | 6.28 | |
| 第2组 | 84.98 | 36 | 19.12 | 88.84 | 40 | 15.79 | ||
| 第3组 | 85.29 | 49 | 25.63 | 89.42 | 55 | 18.45 | ||
| 平均 | 84.98 | 36 | 19.09 | 88.64 | 40 | 13.51 | ||
表选项
遗传算法的收敛性是有效判断当前解是否达到最优解的恰当准则。文献[18]中Rudolph用马尔可夫链证明，在标准遗传算法中采用优秀个体保护策略，能保证算法最终收敛到全局最优解。本文算法加入了最优解保存策略，使优秀个体能直接进入下一代种群，故可以收敛于全局最优解。为对比改进前后遗传算法得到最优方案的性能，对AMA集装箱中的第3组货物数据得到的仿真结果进行统计。图 4为评估值随迭代次数发生变化的对比效果。从收敛性角度看，随着优化过程的进展，评估函数最优值逐渐收敛。改进遗传算法在进化80代左右时，评估值趋于稳定，而标准遗传算法在53代开始出现“上升缓慢”现象，迭代到145代时才能趋于稳定，且性能较差。从搜索速度角度看，改进遗传算法能在较快的时间里搜索到最优解，搜索速度明显优于标准遗传算法。
 |
| 图 4 优化性能比较 Fig. 4 Optimized performance comparison |
| 图选项 |
可视化货物的装箱方案，能直观地反映货物在箱内的码放位置、评估方案可行性，有必要根据算法输出结果开发可视化程序。在MATLAB中，先定义并整理输入数据与绘图空间，调用meshgrid函数根据货物放置的左后下、右前上角坐标生成三维网络采样点，再调用slice函数绘制每个采样点在垂直于X、Y、Z轴平面上的切片图，最终用不同颜色填充每个切片的颜色。
图 5和图 6分别为改进遗传算法得到的2种集装箱箱型的装载效果。可见，算法对于不同种类的强异构货物有着较好的适应性，垛形形状较为规则，能够满足规则、不规则集装箱的空间约束。货物摆放紧凑，满足了装载过程中稳定性的要求。
 |
| 图 5 规则集装箱装箱效果 Fig. 5 Regular packing of container |
| 图选项 |
 |
| 图 6 不规则集装箱装箱效果 Fig. 6 Irregular packing of container |
| 图选项 |
5 结论 1) 在考虑实际装载过程中的7个现实约束下，提出了一种适用于不同箱型的改进遗传算法，通过优化货物放置状态来最大化地利用集装箱装载空间，为复杂集装箱的实时装载问题提供了有效的解决办法。
2) 采用异构性不同的测试算例进行性能测试，证明了本文算法在求解集装箱实时装载问题中有一定的优越性。结合3组具体货物装载数据进行实验，证明了本文算法收敛性好，搜索速度快，能在获得最佳装载方案的同时缩短运行时间，对强异构货物有着较好的适应性与有效性。
3) 通过MTALB实现了集装箱布局方案的可视化，将货物按照其装载顺序合理的装载到集装箱中，得到空间利用率最大的布局方案，为实时装载决策提供了理论基础。
参考文献
| [1] | RAMOS A G, SILVA E, OLIVEIRA J F. A new load balance methodology for container loading problem in road transportation[J]. European Journal of Operational Research, 2018, 266(3): 1140-1152. DOI:10.1016/j.ejor.2017.10.050 |
| [2] | 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 |
| [3] | 刘胜, 沈大勇, 商秀芹, 等. 求解三维装箱问题的多层树搜索算法[J]. 自动化学报, 2020, 46(6): 1178-1187. LIU S, SHEN D Y, SHANG X Q, et al. Multi-layer tree search algorithm for solving three-dimensional packing problem[J]. Journal of Automation, 2020, 46(6): 1178-1187. (in Chinese) |
| [4] | 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. |
| [5] | 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): 803-822. DOI:10.1016/j.ejor.2019.04.045 |
| [6] | 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. |
| [7] | YU F, AMARNATH B. Heuristic/meta-heuristic methods for restricted bin packing problem[J]. Journal of Heuristics, 2020, 26: 637-662. DOI:10.1007/s10732-020-09444-y |
| [8] | 何琨, 黄文奇. 基于动作空间的三维装箱问题的确定性高效率求解算法[J]. 计算机学报, 2014, 37(8): 1786-1793. HE K, HUANG W Q. A deterministic and efficient solution algorithm for the three-dimensional packing problem based on action space[J]. Journal of Computer Science, 2014, 37(8): 1786-1793. (in Chinese) |
| [9] | 何琨, 黄文奇, 胡骞. 基于动作空间的求解三维矩形装箱问题的穴度算法[J]. 计算机科学, 2010, 37(10): 181-183. HE K, HUANG W Q, HU Q. Acuity algorithm for solving three-dimensional rectangular boxing problem based on action space[J]. Computer Science, 2010, 37(10): 181-183. DOI:10.3969/j.issn.1002-137X.2010.10.042 (in Chinese) |
| [10] | 何琨, 黄文奇. 三维矩形Packing问题的拟人求解算法[J]. 中国科学: 信息科学, 2010, 40(12): 1586-1595. HE K, HUANG W Q. Anthropomorphic algorithm for solving three-dimensional rectangular Packing problems[J]. Science in China: Information Science, 2010, 40(12): 1586-1595. (in Chinese) |
| [11] | 崔会芬, 许佳瑜, 朱鸿国, 等. 基于改进遗传算法的三维单箱装箱问题研究[J]. 工业工程与管理, 2018, 23(1): 86-89. CUI H F, XU J Y, ZHU H G, et al. Research on three-dimensional single box packing based on improved genetic algorithm[J]. Industrial Engineering and Management, 2018, 23(1): 86-89. (in Chinese) |
| [12] | 张钧, 贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39. ZHANG J, HE K T. Hybrid genetic simulated annealing algorithm for solving the three-dimensional packing problem[J]. Computer Engineering and Applications, 2019, 55(14): 32-39. DOI:10.3778/j.issn.1002-8331.1902-0127 (in Chinese) |
| [13] | MENGHANI D, GUHA A. Packing boxes into multiple containers using genetic algorithm[J]. Journal of the Institution of Engineers (India): Series C, 2016, 97(3): 441-450. DOI:10.1007/s40032-016-0285-2 |
| [14] | 代爱民. 基于混合免疫遗传算法的半在线三维装箱问题研究[D]. 重庆: 重庆大学, 2018. DAI A M. Research on semi-online 3D packing problem based on hybrid immune genetic algorithm[D]. Chongqing: Chongqing University, 2018(in Chinese). |
| [15] | 于明正, 徐斌, 陈佳. 基于双层启发式遗传算法的三维装箱问题[J]. 科学技术与工程, 2020, 20(5): 2042-2047. YU M Z, XU B, CHEN J. Three-dimensional packing problem based on double-layer heuristic genetic algorithm[J]. Science Technology and Engineering, 2020, 20(5): 2042-2047. DOI:10.3969/j.issn.1671-1815.2020.05.050 (in Chinese) |
| [16] | 李鹏, 汤勇. 三维货物装箱问题的研究进展[J]. 铁道科学与工程学报, 2015, 12(5): 1232-1242. LI P, TANG Y. Research progress of three-dimensional cargo packing[J]. Journal of Railway Science and Engineering, 2015, 12(5): 1232-1242. DOI:10.3969/j.issn.1672-7029.2015.05.037 (in Chinese) |
| [17] | 张德富, 魏丽军, 陈青山, 等. 三维装箱问题的组合启发式算法[J]. 软件学报, 2007, 18(9): 2083-2089. ZHANG D F, WEI L J, CHEN Q S, et al. Combined heuristic algorithm for three-dimensional packing problem[J]. Journal of Software, 2007, 18(9): 2083-2089. (in Chinese) |
| [18] | RUDOLPH G. Convergence analysis of canonical GA[J]. IEEE Trans on Neural Networks, 1994, 5(1): 96-101. DOI:10.1109/72.265964 |
