基于重力装载的自适应随机算法求解多箱型三维装箱问题

吴 蓓，丁文英，杜彦华，赵 宁

(北京科技大学 机械工程学院，北京 100083)

0 引言

多箱型三维装箱问题(three-Dimensional Multiple Bin-Size Bin Packing Problem, 3D-MBSBPP)的定义为：已知一组数量有限且三维尺寸不同的待装载货物，有一组不同三维尺寸且价值不同的可选箱型，选择单个或多个箱子在满足装载要求的情况下将货物装载完毕，使被选择的箱子总价值最小。3D-MBSBPP比传统三维装箱问题更加贴合电商行业的实际应用。随着电商行业的发展，网络购物产生的订单量巨大，在装载订单商品的过程中，选择经济合适的箱型装载能够有效减少纸箱成本，以及填充物和胶带纸等物品的使用量，提高运输效率。目前大多数企业在选箱操作时主要依靠员工经验，很难选到优选组合箱型，导致快递被签收后，包装材料大多难以回收，造成大量的包装垃圾。

3D-MBSBPP是三维装箱问题中研究较少的一类问题[1]，除了考虑传统三维装箱问题中的货物摆放方式外，还要考虑箱型选择和货物分配等。空间划分方法是摆放过程中的关键点之一，三维问题中常用的是三空间划分法，该方法同时在3个维度上搜索可用空间，然而随着搜索空间的增多，算法的复杂性在计算后期会大大增加[2]，通过动态改变领域可以改进求解结果[3]。另外，选择装载物前，可以通过构造同质块或利用一些捆绑策略来有效提高箱子的空间利用率[4-5]。另一种常见的空间划分方法是分层法，该方法操作简单，特别适用于同类或相似货物的装载[6-7]，同层装载可看作二维平面问题，二维问题中主要是优化平面上的货物排布[8-9]。然而，在货物异构型强、摆放方向各异的情况下，三维空间上明显分层容易出现层间利用率低和底面无法支撑的问题，可以通过填充不平整层来提高层间利用率[10]。本文结合填充不平整的思想，提出重力式空间搜索策略来合理利用不平整空间，选择装载空间时需要考虑货物的支撑问题[11-12]。

在多容器装箱问题研究中，将对货物和容器的操作分开，分别讨论装载规则和容器的选择，帮助合理使用容器[13-15]，有研究将组合选箱问题看作为拣选和装箱问题的结合，先将订单拆分，分开拣选后装入不同的箱型[16]。为了更加合理地进行选箱，本文同时考虑容器选择和装载规则。

在最优解未知的情况下，与问题的下界比较可以证明算法的优劣，合理的下界更具说服力[17-18]。本文以使用箱子总成本最小为目标，考虑尺寸、稳定性等约束，建立了3D-MBSBPP数学模型；同时提出一种模仿重力作用的新空间划分方法，并针对3D-MBSBPP问题设计了一种自适应随机算法和一种粒子群优化(Particle Swarm Optimization, PSO)算法，通过求解三维装箱问题算例详细展示了求解过程及算法的强大功能，使整体空间利用率提高了2.16%，从而验证了重力式空间搜索策略的有效性和正确性。按照已有文献中的方法构造了3D-MBSBPP算例并求解，证明了自适应随机算法的优越性，该研究能够提高订单商品的选箱效率，降低电商企业的包装使用成本。

1 选箱模型的建立

1.1 问题描述

本文研究3D-MBSBPP的多箱装载问题，分为箱型选择和货物装载两个步骤，箱型选择与货物装载有关，货物装载可以看作传统的装箱问题。在单箱装载的情况下，箱型选择只需要根据货物的不同摆放方式用空间利用率来决定；在多箱装载的情况下，箱型选择需要考虑货物的分箱，可以将箱型选择和货物装载同步进行，也可以先将订单拆分或货物分类再进行单箱选箱。因此，本文主要解决选择装载箱型、货物分箱、货物箱内摆放3个问题。

客户订购的商品一般有种类多、同种商品只有一件、总件数少的特点，从而导致货物差异大，增加了人为估计的难度、增加了摆放的复杂性，难以采用简单的分层装载。为了研究方便，将货物简化为长方体。电商企业都有一系列大小规格不同的纸箱用于装载订单商品，其尺寸、载重能力等都不同，一般选箱操作时首要考虑的因素是三维尺寸。目前电商行业使用的箱型系列并未统一。

1.2 变量及符号说明

已知待装载货物和待选箱型，假设：①将待装载货物简化为长方体，货物质量均匀，重心在几何中心位置；②箱型已知，数量不限，不考虑箱子厚度和装载间隙；③单个货物的尺寸必须在最大箱型允许的范围内；④装载的货物的总体积不能超过箱子的最大容积；⑤货物不能悬空摆放。

表1所示为本文使用的符号集。

表1 符号集

续表1

1.3 坐标系及摆放方式

计算过程使用坐标系，每一个使用的箱子都有单独的坐标系，坐标原点为箱子的某一顶点，假设X，Y，Z分别为箱子的3个维度方向，如图1所示，对角坐标(px1，py1，pz1)(i，s，j(s))和(px2，py2，pz2)(i，s，j(s))分别表示货物i在放入箱型s中序列号为j(s)的箱子后，在箱子坐标系中靠近和远离坐标原点的对角顶点。货物在箱内有6种摆放方向，分别以长宽、长高、宽高平面为底，沿底面方向旋转90°，分别得到另外一种摆放方向，如图2所示。

每个箱子的的摆放结果用两个矩阵表示，一个表达货物装入顺序和摆放方向，由货物号和摆放方向代号构成，记为A(s，j(s))，j(s)为箱子编号；另一个确定货物在箱内的具体位置，由对角坐标(px1，py1，pz1)(i，s，j(s))和(px2，py2，pz2)(i，s，j(s))构成，记为B(s，j(s))，每一列对应A(s，j(s))中的一行。综合A(s，j(s))和B(s，j(s))两个矩阵可以唯一确定每件货物在不同箱内的位置。

1.4 模型

以使用箱子的总价格最低为目标，目标函数表示为

(1)

(2)

aik+bik+cik≥1,aik，bik，cik∈{0,1},

i，k=1,2,…,n,i≠k。

(3)

(4)

i=1,2,…,n,j(s)=1,2,…,J(s),

s=1,2,…,S。

(5)

aik=0,bik=0,pz2(k,s,j(s))=pz1(i,s,j(s))；

i，k=1,2,…,n,i≠k,j(s)=1,2,…,J(s),

s=1,2,…,S。

(6)

其中：式(2)表示所有货物摆放完成后在坐标系3个维度方向都不超过箱子尺寸；式(3)表示货物i和k的空间位置关系，aik=1表示货物i在货物k的左方，即货物i在X轴方向的坐标值小，bik=1表示货物i在货物k的后方，即货物i在Y轴方向的坐标值小，cik=1表示货物i在货物k的下方，即货物i在Z轴方向的坐标值小；式(4)表示坐标在货物不同摆放方向时，参数li(mi)，wi(mi)，hi(mi)的计算方式；式(5)表示货物各边与箱子各边平行或正交摆放；式(6)表示保证货物摆放的物理稳定性，假设货物k在货物i下方且k顶面与i底面接触，则货物i的重心G必须受到货物k的顶面支撑，如图3所示。

2 算法介绍

2.1 自适应随机算法

异构型强的货物如果采用分层装载，则将导致层间有很多剩余空间。本文提出一种新的重力式空间搜索策略，其弱化“层”的思想，不明显区分每一层，通过模仿重力作用进行空间搜索，优先选择较低的支撑平面，以当前情况为基础作最优选择，而不考虑整体上各种可能的情况，不需要回溯，大大缩短了计算时间。装载过程可以看作为从一维到二维再到三维的过程，重力式空间搜索主要在二维和三维方向。

自适应随机算法是建立在重力式空间搜索策略上的一种串行求解算法，在初始装载过程上具有随机性，包括初始箱型的选择和首件装入货物的选择，在已装载货物的基础上选择新的装载空间，并动态更新可选空间集合，根据即时更新的装载空间得到候选装载货物集合，再根据最佳货物选择规则得到装载货物，摆放时结合空间和货物选择摆放方向，空间与货物之间相互反馈，自动调整。

定义集合D为已装载的货物集合，D′为剩余待装载货物集合，则D∪D′=N0。算法步骤如下：

步骤1输入装箱单。获取待装载货物信息及可选箱型信息，初始化集合D=∅，D′=N0。

步骤2确定摆放方向规则。根据不同规则确定货物在箱内的摆放方向，货物共有3种摆放规则，设置其优先级以应对不同装载情况。在制定货物摆放方向规则之前先固定箱子各边对应坐标轴的方向，本文规定箱子的长宽高分别对应X，Y，Z轴方向。规定第一优先级规则为货物的最长边摆放在X轴方向，次长边摆放在Y轴方向，最短边摆放在Z轴方向，即摆放在各个坐标轴方向的货物边长为X>Y>Z。如果按照该规则不能在选择的平面上摆放，则顺延其他规则。第二优先级规则为Y>X>Z，第三优先规则为Z>X>Y。

步骤3随机选择初始箱型。从已有箱型中随机选择一种作为初始箱型，用s0表示。

步骤4随机选择首件装入货物。在未装载货物中随机选定某一类型货物i第一个装入，若不能装下，则转步骤5；否则更新集合D=D+{i}和D′=D′-{i}，转步骤6。

步骤5修复过程1。选用大一号的箱型s0=s0+1，转步骤4。

步骤6搜索装载空间。利用重力式空间搜索策略选择下一个放置平面，转步骤7；若P=∅，则转步骤9。

步骤7确定最佳货物。计算选定装载平面的剩余装载空间，在D′中选择最适应当前情况的放置货物(具体见本节“装载空间及最佳货物搜索过程”)，将其编号为{ibest}，更新集合D=D+{ibest}和D′=D′-{ibest}，转步骤8。若无可放置货物，则转步骤6。

步骤8试装载。将最佳货物放入选定的装载空间，查看剩余货物情况，D′=∅时终止程序，输出当前的装载方案作为所求解的最佳方案，转步骤11；D′≠∅时转步骤7。

步骤9修复过程2。按照式(7)～式(9)检查已装入的货物整体三个维度的坐标，确定是否可以选用更小的箱型。循环该过程，确定可行的最小s0。

(7)

(8)

(9)

步骤10自动生成新装箱单。保留s0及其中的摆放箱型作为多箱问题中第一个选用箱子的结果，剩余货物集合D′即为新的装箱单，转步骤3选用下一个新的箱子。

步骤11输出结果。

具体流程如图4所示。

在最佳货物搜索过程中引入贪婪思想，选择符合当前情况尽可能大的货物。

(1)一维过程

一维方向的装载过程沿着X轴方向装载，按初始规则在箱型为s的箱子j(s)中装入第一个货物，货物的一条边与箱边重合，此时py2(i,s,j(s))=0,i∈D。按照式(10)计算X轴方向箱子的剩余长度spx，如图5所示。

(10)

在D′中找出满足约束(11)～(13)的货物组成候选货物集合D0。

li(mi)≤spx,i∈D′；

(11)

wi(mi)≤Ws,i∈D′；

(12)

hi(mi)≤Hs,i∈D′。

(13)

集合D0中含有最长边的货物即为最佳货物块，将其编号为{ibest}，其长宽高分别为lbest，wbest，hbest，则

max{lbest,wbest,hbest}=max{li,wi,hi},

i∈D0。

(14)

按照摆放方向规则装入，更新集合D和D′，直到X轴的剩余长度无法装入任何剩余货物，转二维方向。二维方向初始候选支撑面Y的坐标集合为P={py2(i,s,j(s)),i∈D}。

(2)二维过程

li(mi)≤width,i∈D′；

(15)

py2(a)+wi(mi)≤Ws,i∈D′；

(16)

hi(mi)≤Hs,i∈D′。

(17)

(3)三维过程

li(mi)≤widthx,i∈D′；

(18)

wi(mi)≤widthy,i∈D′；

(19)

pz2(a)+hi(mi)≤Hs,i∈D′。

(20)

在集合D0中找出含有最大面积的货物即为最佳货物块，将其编号为将其编号为{ibest}，其长宽高分别为lbest，wbest，hbest，则

max{lbest×wbest,lbest×hbest,wbest×hbest}

=max{li×wi,li×hi,wi×hi},i∈D0。

(21)

空间搜索流程如图8所示。装入第一件货物后，在X轴方向搜索装载空间，再选择最佳货物块i装载。X轴方向装载不下时，转至二维方向，在已装载货物的XZ方向平面上选择支撑面，得到装载空间，再选择最佳货物块i装载。底面装载不下时，转至三维方向，在已装载货物的XY方向平面上选择支撑面，得到装载空间，再选择最佳货物块i装载。

基于重力式空间搜索策略的自适应随机算法具有优越性和灵活性，其在空间搜索和算法上进行了如下创新：①不同于常见的分层法和三空间划分法，在重力式空间搜索策略中，当前已摆放货物的平面均可作为层，货物和空间的协同循环搜索有效利用了货物摆放产生的废弃空间；②能够以当前情况为基础，结合贪婪思想自动搜索最佳货物进行装载，合理分配货物并自动形成新装箱单，两种修复过程修复了算法随机部分的漏洞，提高了产生方案的可行性和优越性；③可以根据实际情况制定不同的摆放方向规则或结合多种规则选择摆放方向，具有灵活性。

2.2 改进的粒子群算法

(22)

例如，有一组货物N={1,2,3}，其长宽高li×wi×hi分别为1×1×2，1×2×2，2×2×2，一组待选箱型编号s∈{1,2}，其长宽高Ls×Ws×Hs分别为2×2×2，2×2×4。根据式(22)求得箱子的部分基因长度r=3，总基因长度为6。基因(3 1 2 1 2 0)表示货物按编号3，1，2的顺序装载，使用了1，2号两个箱子。3号货物装入1号箱，按照重力式装载策略，下一个货物(1号)不能继续装入上一个箱，因此1号货物装入2号箱，2号货物继续装入2号箱。

(1)多样化变异操作

对于3D-MBSBPP，传统PSO算法随机生成的种群得到可行解十分困难，迭代效率很低，为了使算法更加贴合问题，将传统PSO算法与遗传算法结合，执行多样化变异操作，每种变异对问题求解起不同的作用。为使前期尽快搜索到可行解，加入大箱变异操作，设置变异概率ps1，即有概率ps1使选用的某一箱号增大。建议ps1设置较大的值，如0.9左右，使算法尽快找到可行解。前期随着无可行解迭代次数的增加，动态增加变异循环次数，使多位基因可以同时变异。式(22)得到的基因长度r在绝大多数情况下大于实际使用箱子的个数，为得到更好的解，在有可行解的情况下加入减箱变异操作，设置变异概率ps2，使箱子的部分基因有概率ps2变异为0，建议取值0.3左右。后期为了得到更优的解，加入小箱变异操作，设置变异概率ps3，即有概率ps3使选用的某一箱号减小，建议取值0.3左右。根据基因进行试装载后，有些箱型无法装载下任何货物，即空箱，这种箱子极大地影响了目标值，加入空箱变异操作检测是否有空箱，并设置变异概率ps4，使这部分基因有概率ps4变异为0，建议取值0.5左右。货物装载顺序部分采用随机互换变异，设置变异概率ps0随机交换两个货物的装入顺序，建议取值0.1左右。

(2)算法步骤

步骤1输入装箱单。获取待装载货物信息和可选箱型信息。

步骤2设置参数。包括学习因子c1和c2、惯性权重w、种群大小sizepop、迭代次数maxgen，以及5种变异概率ps0，ps1，ps2，ps3，ps4。

步骤3生成种群pop。

步骤4计算适应度并进行空箱变异。计算过程按照重力式空间搜索策略进行试装载，若无法完成装载，则记适应值为inf(正无穷大)，否则按照目标函数值Z，即使用箱子的总价格计算。检查试装载过程中出现的空箱执行空箱变异操作。

步骤5记录个体最佳gbest和群体最佳zbest。每个个体历史适应值最大的个体为gbest，群体历史适应值最大的个体为zbest。

步骤6根据最佳个体进行种群更新。个体有概率w保留原基因，有概率c1与gbest交换部分基因，有概率c2与zbest交换部分基因。货物与箱子两部分基因分开更新，货物部分基因要保证不重复。

步骤7多样化变异。按规则进行大箱、小箱、减箱的互换变异操作。

步骤8计算适应度。

步骤9更新gbest和zbest，返回步骤6，若达到迭代次数，则转步骤10。

步骤10输出结果。

3 实例分析

3.1 三维装箱算例

为了证明重力式空间搜索策略的有效性，求解文献[19]的三维装箱输出最大化算例，共30个待装载长方体，装载容器为国际标准的20英尺集装箱，尺寸为2.352×2.388×5.899，单位为m。选择长方体装载，目标为容器的空间利用率最大。使用重力式搜索策略搜索空间，忽略首件货物选择的随机性。结果对比如表2所示。

表2 文献[19]输出最大化算例的求解结果对比

使用本文算法提高空间利用率约2.16%，装载结果的三维视图如图9所示，证明了重力式装载策略的有效性和优越性，为三维装箱问题提供了新的思路。

3.2 3D-MBSBPP算例

目前尚无关于3D-MBSBPP的标准算例，按照文献[20]的方法构造算例，比较自适应随机算法和改进PSO算法的性能。具体方法如下：将Martello等构造的320个三维装箱算例根据尺寸不同范围划分为8类，每类算例40个，其中待装载货物数分别为n={50,100,150,200}，每种各10个，数据生成器可由链接http://www.diku.dk/～pisinger/codes.html获得。保留三维装箱算例中待装载货物的尺寸数据，8类算例分别取n={50,100,150,200}4种情况中的前两个，共64个算例。待装载箱型共5种，其三维尺寸随机在区间[W/2,W]×[H/2,H]×[D/2,D]内取值，W，H，D分别为原问题中箱型的长、宽、高。箱子价值为

(23)

计算结果用gap表示，

(24)

式中：UB为算法计算的目标值结果；LB为由放松整数约束的线性规划模型计算出的下界值[18]。PSO算法各参数经调节对比能得到较好效果的取值如下：ps1=0.9，ps2=0.3，ps3=0.3，ps4=0.5，ps0=0.1，学习因子c1=0.8，c2=0.8，惯性权重w=0.8，种群大小sizepop=80，迭代次数maxgen=50。两种算法每个算例运行10次，计算8种类型的gap平均值，如表3所示。图10所示为改进PSO算法求解n=50的某一算例的适应度曲线，图11所示为自适应随机算法求解n=50的某一算例的三维结果图。

表3 两种算法的计算结果

由表3可以看出，自适应随机算法求解8类算例的gap值均更小，其平均gap值比PSO算法优19.59%，表明结果与最优解的距离更近，求解质量更优，证明了自适应随机算法求解3D-MBSBPP的优越性。

4 结束语

本文研究订单货物选箱背景下的3D-MBSBPP，考虑三维尺寸、物理稳定性等约束，以使用箱子总成本最小为目标建立了数学模型，针对异构型订单货物的特点提出的模拟重力作用的空间划分方法是对空间搜索策略的创新，使用重力式空间搜索策略提高了已有三维装箱算例2.16%的空间利用率，是对剩余空间利用的突破。摆放规则及有效结合贪婪思的货物选择策略使算法具有自适应性，随机因素和修复过程提高了解的质量。按照已有文献中的方法构造3D-MBSBPP算例，并用两种算法求解，自适应随机算法比PSO算法的平均gap值优19.59%，且具有稳定性。3D-MBSBPP在电商行业的客户订单选箱装箱中有重要应用，合理选箱能够有效节省纸箱和填充物资源。

在本文研究的基础上，未来可以从以下方向进行进一步研究：①构造同质块，或在装箱前进行相似块聚类再进行装箱；②加入货物耐压性、易碎性等其他约束；③进一步消除初始选箱随机性的影响。