货物三维装箱问题建模及其乌鸦搜索算法优化

王素欣，温恒†，卢福强，刘浩伯，王雷震

（1.东北大学秦皇岛分校 控制工程学院，河北 秦皇岛 066004；2.东北大学 信息科学与工程学院，辽宁 沈阳 110819）

货物装箱与物流运输过程影响着企业的竞争力、成本、客户满意度、销量、以及市场占有率，直接影响着企业的盈亏情况甚至是企业未来的发展.货物三维装箱问题的优化，可以减少物流过程所需要的成本，提高物流运输效率，使企业得到更好发展.

货物三维装箱问题其本质属于装箱问题（Bin Packing Problem，BPP）.作为一个经典的组合优化问题，“组合爆炸”现象的出现，导致这个NP-hard 问题的最优解很难找到.

目前，装箱问题应用广泛，考虑平衡、稳定等因素的货物三维装箱问题逐渐增多.Galrão 等[1]针对集装箱装载问题，提出了一种具有静力稳定约束的集装箱装载算法，指出了静态稳定性与动态稳定性的对立关系.Martínez 等[2]考虑动态稳定约束的集装箱装载问题，提出了坠落箱数及加速时可能损坏箱数两项动态稳定性指标.装箱问题的求解方法可以粗略地分为运筹学方法和启发式方法两大类.Paquay等[3]针对三维多尺寸箱型的装箱问题，考虑了箱子的易碎性、稳定性和定位，以及箱子的特殊形状和重量等因素，提出了一个快速的建设性两阶段启发式算法.Alonso 等[4]考虑了几何、重量、重心、动力稳定性等约束，采用整数线性模型解决了多集装箱装载问题.

现有三维装箱研究中存在如下问题：

1）一些模型的约束条件不完善，重心约束没有考虑转弯情况.

2）目标函数考虑较少，部分模型未说明假设条件.

3）用到的遗传算法等求解方法较旧，全局寻优的能力较弱，迭代收敛速度较慢.

乌鸦搜索算法[5]（Crow Search Algorithm，CSA）自被提出以来，广泛应用到诸多领域，如图像分割[6]、数据挖掘分类问题[7]、帕金森病的诊断[8]、评估噪声对损伤检测过程的影响[9]、图像处理问题[10]等.改进乌鸦搜索算法的方法可以分为两大类，一类是引入策略对算法进行改进.例如，Sayed 等[11]引入了10 种混沌映射，提出CCSA；另一类是与其他算法相结合的混合算法.例如，Javaid 等[12]将CSA 与蝙蝠算法混合，提出了BCSA.Pasandideh 等[13]将CSA 和正弦余弦算法的优点相结合，提出了余弦乌鸦搜索算法.

针对上述问题，为了减少翻车情况的发生，建立了具有考虑转弯情况、重心约束等7 个约束条件，容积利用率、载重总重量、重心坐标等5 个目标函数的多约束多目标货物三维装箱模型.为了使乌鸦搜索算法更好地适配装箱问题，同时加快迭代收敛速度，提高全局搜索能力，提出并引入了多概率随机游走策略和解修复策略对原始乌鸦搜索算法进行改进，并对模型进行了求解，装箱效果更好.

为了验证改进CSA 的有效性，结合实例通过遗传算法、粒子群算法、乌鸦搜索算法、灰狼优化算法[14]（Grey Wolf Optimizer，GWO）、鲸鱼优化算法[15]（Whale Optimization Algorithm，WOA）、最有价值球员算法[16]（Most Valuable Player Algorithm，MVPA），以及改进后的乌鸦搜索算法对货物三维装箱问题进行了优化仿真与测试，进一步说明了改进后的算法迭代收敛速度更快，跳出局部最优的能力更强.为了说明改进后的算法在连续问题中的适用性，通过对3 个基准函数测试以及和其他部分算法对比，验证了改进后算法的优越性.

1 货物三维装箱模型的建立

由于大部分装箱问题研究中给出的重心约束都没有考虑货车转弯的情况，针对这一现象，建立了考虑转弯的情况的模型，并得出了与其他研究不一样的重心约束条件.

1.1 问题假设与符号说明

1.1.1 问题假设

由于货车的实际运输过程较为复杂，为了将问题简化，提出如下假设：

1）货车车厢与货物均为标准长方体结构.

2）所有货物均密度均匀，其质心为长方体结构几何中心，且不发生形变.

3）用泡沫或棉花填充空隙，忽略填充物重量.

4）装载时，货物的高必须与车厢的高平行.

5）运输过程中，货车转弯时的行驶路线为规则的圆形道路.

6）运输过程中，道路均为平坦的道路，若存在倾斜情况，倾斜角度始终不变.

1.1.2 符号说明

模型用到的符号及相关说明见表1.

表1 符号说明Tab.1 Symbol description

对货物按照从1 到D 的顺序进行编号，设可行解的结构为：

式中：X 的每一行表示一个解Xn；xnd∈[-D，D]，且xnd是不为0 的整数，表示第d 个装入的货物其序号为，xnd＞0 表示货物的长与车厢的长平行，xnd＜0表示货物的长与车厢的宽平行.

1.2 建立货物三维装箱模型

在保证货物与货物之间不存在镶嵌、包含现象，且货车转弯过程中不翻车的条件下，将货物按照一定的顺序以及摆放方式装入到车厢内.综合考虑容积利用率以及货物合重心等因素对整个装载运输过程的影响，对货物三维装箱问题建立合理的模型.

1.2.1 目标函数

下面对货物三维装箱问题建立具有优先级的多目标优化模型.考虑到运输成本的因素，应当尽量减少货物运输的次数，因此，货物装箱的第1 目标是车厢容积的利用率最大，即第1 目标函数的表达式如式（2）所示.合理利用空间之后，要合理利用载重量，在满足第1 个目标的情况下，货物装箱的第2 目标是装载货物的总质量最大，即第2 目标函数的表达式如式（3）所示.不倒翁之所以不倒，正是因为其重心低的缘故，物体的重心越低越稳定，因此，货物装箱的第3 目标是在满足前2 个目标的情况下，货物合重心的高度最低，即第3 目标函数的表达式如式（4）所示.货物装箱的第4 目标是在满足前3 个目标的情况下，货物合重心的Y 坐标最靠近车厢宽度的中心，即第4 目标函数的表达式如式（5）所示.一般情况下，上述4 个具有优先级的目标函数足以区分不同的解，为了使模型的适用情况更加广泛，这里引入第5 目标，假设运输过程中要求在满足前4 个目标的情况下，货物合重心的X 坐标要最靠近车厢长度的中心，则第5 目标函数的表达式如式（6）所示.即在满足约束且货物容积利用率最大的情况下，进一步按优先级顺序对合重心的各个坐标进行建模与优化.

模型的目标函数为：

1.2.2 约束条件

在物流领域中，货物装箱后存在配送过程，转弯的时候由于货物偏心容易翻车.为了避免翻车现象的出现，在货物装箱过程中加入考虑转弯的重心约束.

1）转弯时重心约束的推导过程

以（xi，yi，zi）表示第i 个箱子的质心的坐标，则I 个箱子的组合体质心坐标表示为，其公式如下：

考虑到货车转弯的对称性，对货车右转弯过程进行分析.货车转弯时，相当于受到一个离心力的作用，此时，货车更容易绕着以货车左前轮、左后轮分别与地面接触的两点所确定的直线看作为转轴逆时针翻转.以靠近车头的车厢左下角为原点，其引出的3 条棱所在直线分别为X 轴、Y 轴、Z 轴建立空间坐标系对车厢进行分析，仅考虑YOZ 平面，即将车厢投影到YOZ 平面上，对货车在即将翻转的临界状态进行受力分析，如图1 所示.

图1 货车车厢模拟后视图及其在投影面的受力分析图Fig.1 The simulated rear view of the truck carriage and its force analysis diagram on the projection plane

受力分析后得到，

左下角的转轴在YOZ 平面投影为O 点，其坐标为（0，0），货物重心在YOZ 平面投影为C 点，其坐标为（y，z），直线CO 与车厢底边Y 轴所夹的锐角为α：

容易得到，此时的合力矩为：

当M ＞0 时，货车发生翻转，即：

货车会绕O 点逆时针翻转，临界翻车时，

即如果想要避免翻车，需要满足的约束条件为：

考虑到货车以及路况的对称性，重心应该位于图2 中的阴影区域，货车以速度V 行驶过半径为R的弯道时，不会翻车.即在YOZ 平面上的一个以车底投影的直线为底，底角α=arctan的等腰三角形（或者等腰梯形）投影区域.

图2 货车后视图及重心稳定的区域Fig.2 Rear view of truck and stable centre of gravity area

同理，当道路存在倾斜角为β 的情况时，考虑最糟糕的情况，可以得到此时如果想要避免翻车，需要满足约束条件，

式（15）所表示的重心约束条件是其他文章没有考虑的，加入此约束后，货物三维装箱问题更贴合实际情况，并且可以进一步降低货物运输过程存在的安全风险.重心应该位于图3 中的阴影区域.

图3 货车后视图及重心稳定的区域（道路有斜坡）Fig.3 Rear view and center of gravity stable area（road with slope）

2）约束条件描述

模型的约束条件描述为：

a）保证货物不悬空放置.

b）保证货物与货物之间不存在镶嵌、包含的现象.

c）货物总重量不能超过货车的载重量.

d）货物的总体积不能超过货车的总容积.

e）货物放置的顶面要与车厢顶面平行，货物放置的前面要与车厢前面平行.

f）装入的货物不能有在集装箱箱外的部分.

g）货物的组合重心满足式（15）约束条件.

3）约束条件的特点

上述约束中，前6 个为常用的现实约束，约束条件g 中重心约束范围与其他研究不同.其他研究未考虑转弯情况，只在静止情况下得到的重心范围投影为矩形区域，约束条件g 考虑了转弯情况，得到的是等腰三角形或等腰梯形区域，模型相对更完善.

1.2.3 货物放置规则与特点

1）放置规则

将空容器看作一个剩余空间，将货物的左后下角与剩余空间的左后下角重合放置货物.放入的货物其每个面均可将占用的剩余空间切割为两部分，取货物不占用的那部分空间作为新的剩余空间.图4 表示货物上面切割出的剩余空间S.

图4 剩余空间分割示意图Fig.4 Schematic diagram of residual space segmentation

每个面都切割空间后，删除容积为0 的剩余空间，将得到剩余空间与已有的剩余空间合并.得到新的剩余空间，并尝试放入下一个货物.货物按照解序列所对应的货物编号依次放入容器，且优先放在靠下的剩余空间中.

2）放置特点

其他大部分文献中，上空间的分割得到的底面积和货物顶面的面积相同，即货物上面的货物，其底面面积必须不超过下方货物的顶面面积，相当于增加了限定，而这里的规则突破了限定，增加了解的多样性.

2 改进CSA 求解货物三维装箱问题

对货物三维装箱模型优化求解的目的是为了得到一个更好的装箱方案，在保证运输安全的情况下，更好地利用装载空间，从而尽可能减少运输成本.

2.1 CSA 求解货物三维装箱问题

乌鸦搜索算法（CSA）是Askarzadeh[5]在2016 年提出的启发式算法.其灵感来自于群居的乌鸦隐藏自己多余食物的过程.乌鸦隐藏自己的食物，既要不被其他乌鸦发现，又想跟随其他乌鸦找到它隐藏的食物.由于其相对较好的优化效果，被广泛应用在各个领域中.

随机初始化所有乌鸦种群X，如式（1）.

初始化乌鸦的记忆E，作为当前每个乌鸦的历史最优位置，即每个可行解的历史最优解.

按照解序列进行货物装箱，计算式（2）～式（6）所描述的5 个目标函数值，再进行下一步迭代，迭代更新出新的乌鸦种群，即新解，更新公式为：

检查新解是否可行，如果不可行，将它修正为可行解.解的具体修正过程将在下文中进行详细介绍.

再次计算5 个目标函数值，更新乌鸦记忆，即每个个体的历史最优解.更新公式为：

继续迭代更新乌鸦种群，修正解，计算目标函数，更新记忆，如此循环，直到满足最大迭代次数或者其他终止准则时停止.得出M 中最优的解作为最终的最优解.

2.2 改进CSA 的策略

由于原始CSA 主要用于连续问题，且迭代收敛速度慢，容易陷入局部最优，因此，这里对CSA 进行改进，提出了两个改进策略.

2.2.1 解修正策略

原始CSA 主要用于求解连续函数的极值问题，属于连续问题，而货物三维装箱问题的解是离散的，直接用CSA 求解并不符合实际情况，原始CSA 并不适用.为了将CSA 与货物三维装箱问题适配，且尽可能增大解的多样性，这里提出了解修正策略，图5是解修正策略的一个例子.

图5 解的修正策略步骤示意图Fig.5 Schematic diagram of the revision strategy steps of the solution

为了保持解的符号不变，先将解的符号提取出来，正号记为1，负号记为-1，如果为0 则视为正号.再将解序列的绝对值按照从小到大进行排序，如果大小一样则保持其相对顺序，将排序后的序号与解的符号按位相乘对解进行重新编码.

2.2.2 多概率随机游走策略

在加入解修正策略之后，CSA 与货物三维装箱问题成功匹配了，但是其迭代收敛速度还不够快，跳出局部最优的能力还不够强.为了得到更优方案，引入多概率随机游走策略对乌鸦搜索算法进行改进，具体操作步骤如下.

设置3 个概率，分别为p1=0.25，p2=0.5，p2=0.75，产生3 个随机数q1，q2，q3，且满足q1，q2，q3∈[0，1].

当q1≤p1时，随机游走策略为：

当q2≤p2时，随机游走策略为：

当q3≤p3时，随机游走策略为；

2.2.3 改进CSA 流程图

将改进后的CSA 称为多概率随机游走乌鸦搜索算法（Multiple Probability Random Walk Crow Search Algorithm，MPRWCSA）.MPRWCSA 是在原始CSA 的基础上加入了解修正策略和多概率随机游走策略两个重要步骤，对于MPRWCSA，其算法步骤流程图如图6 所示.

图6 MPRWCSA 步骤框图Fig.6 Procedure block diagram of MPRWCSA

3 仿真实验及结果分析

3.1 装箱实例仿真

3.1.1 案例说明

设置转弯时最大行驶速度Vmax=72 km/h，道路转弯的倾斜角β=22°，转弯半径R=0.1 km，重力加速度g=9.8 m/s2.

货车车厢与货物的规格[17]分别见表2 及表3.

表2 货车车厢规格参数Tab.2 Specifications of freight car

表3 货物规格参数Tab.3 Cargo specifications

设置种群数为150，最大迭代次数为1 000，分别用灰狼优化算法（GWO），鲸鱼优化算法（WOA），乌鸦搜索算法（CSA），最有价值球员算法（MVPA），遗传算法（GA），粒子群优化算法（PSO）以及MPRWCSA 对该案例进行建模，借助MATLAB 程序对问题进行求解.

3.1.2 仿真结果

计算每个算法模型求解10 次后平均值，只分析每一代中第2 目标函数（重心高度最低）的值，可以得到如图7 所示的迭代收敛速度曲线.

图7 迭代收敛速度曲线Fig.7 Iterative convergence rate curve

通过仿真实验可以得到，货物装箱的最大体积为17 816.336 m3，最大装载质量为17 682 kg，最大容积利用率为60.095 8 %，最优解的质心坐标为（2 407.425 2，1 147.815 7，663.556 16），最优解序列为3，11，-2，15，-8，6，5，-16，-1，9，4，14，10，12，-13，7，装箱效果图如图8 和图9 所示，仿真结果见表4.

图8 装箱效果图Fig.8 Packing effect drawing

图9 装箱效果俯视图Fig.9 Top view of packing effect

表4 仿真结果表Tab.4 Table of simulation results

3.1.3 结果分析

通过图7 可以直观地看出，改进后的乌鸦搜索算法（MPRWCSA）迭代效果明显优于其他优化算法，迭代收敛速度更快，得到的解更优.表4 中，从解的优劣程度上可以看出，CSA、WOA、MPRWCSA 所得到的解，明显优于GWO、MVPA、GA、PSO.MPRWCSA 的合重心Z 轴坐标的平均值较其他算法更优，10次实验中，Z 轴坐标的最优值比GWO、MVPA、GA、PSO 好，虽然与WOA、CSA 相同，但在Y 轴坐标的最优值上效果更好.相比较CSA 与WOA，MPRWCSA达到最优解时所需要的平均迭代次数小于CSA 与WOA.说明改进CSA 后得到的MPRWCSA 其迭代收敛速度更快，跳出局部最优的能力更强，在离散问题的应用上效果较好.

文献[8]和文献[19]中也用到了相同的仿真案例，对比实验结果发现，MPRWCSA 得到的结果在重心上优于文献[17-19] 中的结果，且模型更为合理.MPRWCSA 由于其在更新后，还会按照不同的概率继续随机游走，结合解修复策略，因此比其他算法优化效果相对较好.

3.2 基准函数测试仿真

3.2.1 案例说明

通过3 个常用的基准函数（Ackley、Sphere、Rastrigin） 对MPRWCSA 进行测试，并与CSA、PSO、GWO、WOA 进行对比.其中，Sphere 函数为单峰函数，Ackley 函数虽是多峰函数，但是峰值间差距不明显，Rastrigin 函数是显著的多峰函数.3 个基准函数的表达式及其对应自变量的取值范围见表5.问题维度设为2 时，函数的图像如图10 所示.

表5 基准函数表Tab.5 Table of benchmark function

图10 基准函数图像（问题维度为2）Fig.10 Baseline function image（problem dimension 2）

设置种群大小为150，最大迭代次数为1 000，问题维度为30，分别对MPRWCSA 和CSA 进行30 次测试.

3.2.2 仿真结果

依次将不同基准函数的30 次测试历代当前最优值取平均值，绘制迭代收敛的半对数曲线，如图11～图13 所示.记录30 次测试的最优解，根据这30个数据，计算出最优值、最差值、平均值、标准差、平均时间等评价指标，结果见表6.

表6 基准函数测试结果表Tab.6 Table of benchmark function test results

3.2.3 结果分析

通过图11～图13 可以看出，MPRWCSA 能够很好地应用在连续问题中，且其前期的迭代收敛速度明显优于其他几个算法.从最终结果上看，除Ackley函数中不及GWO 外，MPRWCSA 得到的结果相对更优一些.从表6 中可以看出，较CSA 而言，除运行时间与Ackley 函数中测试标准差外，其他各项都比后者更优.较WOA 而言，除Ackley 函数中测试最优值外，其他各项都比后者更优.较PSO 与GWO 而言，虽然最优值和运行时间上结果比后者差一点，但其算法稳定性较好.改进后的算法主要是为了提高前期的迭代收敛速度与全局搜索的能力，对于连续问题的寻优精度改进效果并不明显.

图11 Ackley 函数迭代收敛速度半对数曲线图Fig.11 Ackley function iterative convergence rate semi-logarithmic curve

图11 中，MPRWCSA 得到的结果其精度不如GWO 的原因是由于CSA 结果的精度比GWO 差，而MPRWCSA 并未针对最优解精度进行改进，主要改进了迭代收敛速度与全局搜索能力.

图12 Sphere 函数迭代收敛速度半对数曲线图Fig.12 Sphere function iterative convergence rate semi-logarithmic curve

图13 Rastrigin 函数迭代收敛速度半对数曲线图Fig.13 Rastrigin function iterative convergence rate semi-logarithmic curve

4 结论

针对货物三维装箱问题进行了建模与优化，提出了更完善的模型与更高效的求解方法.

1）模型上的改进.在6 个现实约束的基础上，加入了考虑转弯时的重心约束，建立了容积利用率、载重总重量、重心坐标等5 个目标函数的货物三维装箱优化模型.其中，重心区域的投影为等腰三角形或等腰梯形，较其他文献中的矩形区域而言，考虑得更全面.

2）算法中的改进.提出并引入了多概率随机游走策略与解修复策略对乌鸦搜索算法进行改进，对货物三维装箱问题进行了求解与优化.将更新后的解按照不同概率进行随机游走，结合解修复策略，有效地提高了算法的迭代收敛速度与全局搜索能力.

3）优化结果分析.通过实例仿真验证了改进后算法对货物三维装箱问题求解优化的可行性与优越性.通过基准函数测试，说明了改进后的算法同样适用于连续问题，且在前期迭代收敛速度快，全局搜索能力强，得到的结果相对更好.