多约束三维装箱问题的启发式优化算法

廖云峰，单鸿涛，赵文洁

（上海工程技术大学电子电气工程学院，上海 201620）

0 引言

三维装箱问题是一种具有复杂约束的组合优化问题，如果采用精确的求解算法，随着问题规模的不断扩大，可能会发生组合爆炸的现象。启发式求解算法可在可接受的计算成本内搜寻最好的解，多用于解决非确定性多项式问题，成为装箱问题的首选。例如，George 等［1］基于“层”提出了启发式算法；在此基础上，Araya 等［2］采用集束搜索算法处理双目标三维装箱问题；Bischoff 等［3］设计了基于同类物体的块算法，其中块由完全相同的物体（物体的属性和摆放约束均相同）组成，Eley 等［4］提出的树算法，Mack等［5］提出的局部搜索算法和Zhu 等［6］提出的贪心前向搜索算法均结合了块生成算法；还有许多优秀的解决多约束装箱问题的启发式算法［7-9］。国内学者对三维装箱问题的研究也取得了许多优秀成果，例如张德富等［10］提出一种组合启发式算法；李孙寸等［11］利用多元优化算法求解三维装箱问题，得到了理想的装箱效果；代爱民［12］结合启发式算法和免疫遗传算法提出混合免疫遗传算法，用于提高装载方案的空间利用率；朱莹［13］提出混合遗传算法求解单集装箱问题；车玉馨［14］基于前向搜索树算法提出剩余空间动态调整算法以提高解的质量；刘胜等［15］采用二叉树搜索算法求解三维装箱问题。

目前启发式算法在求解简单约束的三维装箱问题上均取得了较好效果，但很少有适用于实际情况中具有多约束条件三维装箱问题的算法［16-19］。因此，针对约束条件相对复杂的三维装箱问题，本文建立了以集装箱体积利用率最大为目标的数学模型，提出一种基于块装载算法的启发式优化算法，通过块装载算法考虑约束条件，如重量约束等，进而生成装载块列表，然后在剩余空间中根据装载序列选择合适的装载块，得到最优装载方案。本文算法在测试算例中取得了较好的装载结果，且能用于求解大规模的集装箱装载问题。

1 模型建立

多约束三维装箱问题可以定义为：给定一个集装箱C=(L，W，H)，其中L、W、H分别表示集装箱的长、宽、高，最大容积和最大载重量分别为V和M，第i种货物数量为ni，质量为mi，体积为vi，长、宽和高分别为li、wi、hi，要求在装载时满足一定的约束条件，并将货物尽可能多地装入集装箱内，使得空间装载率最大。

以集装箱的装载率最大为目标函数，表示为：

式中，F为集装箱装载率，i为货物序号，φi为第i种箱子装进集装箱的数量。

装载货物时的范围约束表示为：

式中，lxi、lyi、lzi为值为0 或1 的变量，分别表示第i种箱子的长是否平行于集装箱的长、宽、高，例如若第i种箱子的长平行于集装箱的长，则lxi=1，否则lxi=0；wxi、wyi、wzi为值为0 或1 的变量，表示第i种箱子的宽是否平行于集装箱的长、宽、高；hxi、hyi、hzi为值为0 或1 的变量，表示第i种箱子的高是否平行于集装箱的长、宽、高。

2 基于块装载的启发式算法

2.1 块装载算法

不同于利用箱子进行装载的传统启发式算法，本文算法主要基于块装载算法建立装载序列与放置方案的映射关系，其中块装载算法指的是简单块的生成。

简单块是一种同种类型箱子之间没有丝毫缝隙堆叠而形成的长方体，其生成必须满足3 个条件：①简单块的长宽高必须在集装箱的体积范围内；②简单块的重量必须在集装箱的承受范围内；③简单块使用的箱子数量必须符合该类箱子的剩余数量。图1（a）和图1（b）分别展示了箱子在两种不同方向生成的简单块，其中nxi、nyi、nzi分别为简单块在每个坐标轴上的箱子数量，nxi*nyi*nzi则是该简单块所需第i种类型箱子的总数量，通过枚举第i种类型箱子在集装箱内所有满足条件的组合(nxi，nyi，nzi)，将得到的每个简单块加入到装载块列表中。

Fig.1 Generation examples of simple blocks图1 简单块的生成例子

2.2 启发式优化算法

参考张德富等［20］提出的启发式算法，本文提出基于块装载的启发式优化算法。文献［20］中的启发式算法在每个装载阶段中根据剩余空间大小计算能使用的所有块，然后从中选择一个块装入剩余空间，这样在装载时不会考虑重心约束的条件。而本文在装载过程中考虑每次装载时的重心约束，使得箱子装载完成时会有一个很好的平衡性。

将集装箱大小作为剩余空间的初始值，图2 中用前、右、上3个部分表示在装载箱子后生成的3个剩余空间。

Fig.2 Division of residual space图2 剩余空间分割

启发式算法中装载块的编码表示为：

式中，B表示装载块列表，包含生成的简单块；n表示列表中装载块的总数。

装载块bj表示列表中第j个装载块，其编码表示为：

式中，j表示装载块列表中装载块的序号；(li，wi，hi，mi)分别表示装载块的长、宽、高和重量；(ni，di)分别表示该装载块所使用的箱子数量和箱子摆放类型。

剩余空间space表示为：

式中，(xa，ya，za)分别表示剩余空间能放置参考点的三维坐标，即该空间的左、后、下顶点坐标；(xb，yb，zb)表示剩余空间可放置的长、宽、高；γ=(1，2，3)表示装载块在前、右、上3个剩余空间中进行装载。

当放置参考点为原点，即集装箱空载时，(xb，yb，zb)为集装箱的长、宽、高，初始剩余空间表示为：

如图2 所示，将装载块bi放入剩余空间中，分别在3 个坐标轴方向生成对应的3 个剩余空间Space(m)，Space(m+1)和Space(m+2)，对应的编码分别表示为：

式中，m表示剩余空间的序号。在每个装载阶段都需要对剩余空间进行一次新的划分，在集装箱未装满之前会不断生成剩余空间，在搜索过程中对剩余空间进行高度排序，规定其装载优先级，确保箱子的装载是由下至上的，以提高装载稳定性。在剩余空间有可装载块时，根据装载序列选择块装载，重新对未装载的剩余空间进行切割；在剩余空间无可装载块时，对剩余空间进行合并，直到无可用剩余空间。

3 实验结果分析

实验环境：CPU 为Intel（R）Core（TM）i5-8500H @2.30GHz 2.30GHz，内存为8G，操作系统为Windows 10，算法实现语言为MATLAB R2018a。

在求解多约束三维装箱问题时需要考虑货物的重量限制和集装箱装载的重心约束。文献［13］中的BR1-BR7算例组中每组包含100 个单独的子算例，由于BR 算例缺少重量限制，需通过正态分布的方法随机增加重量限制。已知最常见的用于物流运输的箱子密度D=753[kg/m3]，密度di满足正态分布N(D，σ)，其中σ=0.5D，可得出带有重量限制的BRw 算例，BR1w-BR7w 每个算例组中同样包含100 个单独的子算例，算例中箱子的重量限制与体积的关系如图3所示。

图4 中BR1w-BR7w 分别表示两种启发式算法在对应算例上的平均装载率，average 表示两种模型在所有BR1w-BR7w 算例上的平均装载率，其中Heuristic-box 表示仅利用箱子进行装载的启发式算法，Heuristic-CLPw 表示基于块装载的启发式算法。从图4 可以看出，本文算法Heuristic-CLPw 在每一组BRw 算例上的平均装载率都比算法Heuristic-box 要高，且本文算法的平均装载率average 达到83.7%，比传统利用箱子装载的启发式算法的平均装载率要高出4%左右。

Fig.3 Relationship of weights and volumes for boxes in BRw instances图3 BRw算例中箱子重量与体积的关系

Fig.4 Average loading rate of two different models for each group of BR1w-BR7w examples图4 基于BR1w-BR7w算例的两种不同模型的平均装载率

4 结语

针对实际生活中多约束的三维装箱问题，本文提出基于块装载的启发式优化算法。在带有多种约束条件的BRw 算例上进行实验，结果表明启发式优化算法的装载率得到明显提高，这是由于在装载过程中引入的简单块增加了每次装载时箱子的体积，有效提高了集装箱中空隙的利用率。该方法虽然提高了空间利用率，但由于块装载算法需要先将箱子组合成简单块再进行装载，运行算法消耗的时间不可避免地会增加，因此提高启发式算法的运行效率是后续研究目标。