电商物流背景下基于空间矩阵的三维装箱算法

林云鹏，宋 爽，江志斌，张大力

(上海交通大学 1.机械与动力工程学院，上海 200240；2.中美物流研究院，上海 200030；3.安泰经济与管理学院，上海 200030)

装箱问题是一种具有复杂约束条件的离散组合优化问题，具有很强的应用背景。到目前为止，有大量关于装箱问题的研究，并有很多文献对此进行解决方法阐述。这些装箱算法大部分都是关于品类少、单项数量多、弱异构性的装箱问题。随着电子商务应用与供给需求不断改善发展，个性化程度高的电商领域装箱订单越来越多，强异构性装箱问题成为其中重要部分，对传统的装箱算法提出新的要求。本文的研究对象为电商领域中的多箱型三维装箱问题 (three-dimensional multiple bin-size bin packing problem, 3D-MBSBPP)。

近些年来，3D-MBSBPP已经有了一定的研究，主要集中在结构假定方式和启发式算法的优化上。在结构假定方式优化方面，大致可分为关键点法[1]、分层法[2]以及空间分割法[3]，主要关注如何确定物品在箱子内的可摆放位置以及有多个可摆放位置时如何进行选择。在启发式算法优化方面，大量学者从不同方面进行深入研究。Eley[4]首次提出集合覆盖模型，以模型的每一列对应一种装箱方案，并提出相应的基于树搜索启发式算法的列生成算法。随着该模型的提出，各种列生成算法不断涌现，其中启发式算法为首选。例如，Sulaiman等[5]提出一种基于随机交叉和动态变异的遗传算法，以克服早熟收敛。Fu等[6]基于优先级队列分支的思想和约束方法，提出一种分支定界算法。Dell'Amico等[7]在研究了多项式大小公式、指数大小公式以及若干下界上界的基础上，提出一种求解指数型公式的分支价格算法。Li等[8]提出一种基于差分进化算子的入侵杂草优化算法。Fan等[9]根据算法编码的特点，设计一种替换插入的方法并更新了交叉算子，从而提出一种改进的分组遗传算法。此外，国内学者在启发式算法优化方面也取得很好的结果，如在遗传算法[10]、模拟退火算法[11]、蚁群算法[12]等方面。

以上这些算法都假定装填结果满足一定的结构，虽然简化了装填过程，但造成搜索解空间变小，从而导致解的质量不高。而且，电商物流订单具有高度个性化特点，主要体现在由于电商订单均为客户定制订单，订单个体呈现出各品类间物品数量波动大的特点。因此，传统装箱问题的结构假定方式，如砌墙、建堆、立方体排列、切割等，不适用于电商物流。同时，大规模邻域搜索算法是作为一种高效寻优算法，既能保持大规模邻域的寻优能力，又能克服低效耗时的弱点，如在TSP问题研究中，贾瑞玉等[13]就通过引入大规模邻域搜索算法优化传统启发式算法的搜索路径并取得良好效果。而在三维装箱问题中，由于大规模邻域搜索算法的关键元素较难选择，该算法之前并未用于装箱算法的搜索路径优化。因此，为了适用新的问题背景、改进解的质量，本文一方面提出新的假定结构方式，通过采用空间矩阵表征方式和新型算法编码控制装箱过程；另一方面提出三维装箱问题中大规模邻域搜索的关键元素选取方式，并以此优化传统启发式算法对装箱方案的搜索过程，避免陷入局部最优，从而快速有效地解决电商物流领域的3D-MBSBPP。

1 问题描述及数学建模

本节对本文研究的3D-MBSBPP进行数学描述，并结合实际背景，对目标和约束进行介绍。

1.1 问题背景

多箱型三维装箱问题是指有多种不同的箱型，每种箱型有一个尺寸和成本，每种箱型的箱子可使用数量无限制，求能将给定三维物品集合内的所有物品全部装下且不存在物品空间重叠或超出箱子范围的总成本最小的箱子使用方案。而在本文研究的电商领域中，随着客户对便捷性需求的提高和企业对客户满意度的关注，单箱装载(将单个客户订单中所有物品装载至单个箱子中)逐渐成为物流企业在装箱中非常关注的一点。因此，本文所研究的问题，是一种以单箱装载为目标的3D-MBSBPP，具体是指基于客户订单和给定的多种可选箱型，确定一种箱型及其相应装箱方案，在尽可能单箱装载客户订单所有物品的基础上实现装载率最大；若出现无法单箱装载情况，则等效为多个在单箱装载更多物品的基础上实现装载率最大的多箱型三维装箱问题复合，其本质上与前文所述的在尽可能单箱装载所有物品的基础上实现装载率最大的要求相同，因此对于该情况本文不作过多赘述。

1.2 模型建立

1.2.1 相关参数

假设有N种给定的可选箱型，以有序集合(按箱子体积升序)B={b1,b2,···,bN}表示，某客户订单中有n个待装载物品，以有序集合(按物品体积降序)集合T={t1,t2,···,tn}表 示。其中，箱子bI的长LI、宽WI、高HI；物 品ti的 长li、宽wi、高hi， 且LI≥WI≥HI，lI≥wI≥hI。I为被选箱型的编号，I=1,2,···,N，i=1,2,···,n。同时，由于物品无摆放朝向约束，物品ti在X、Y、Z轴上长度与长li、宽wi、高hi的对应关系会因其不同朝向而变化，因此，定义lXi、lYi、lZi分别表示其沿X、Y、Z轴上长度。

问题目标是在满足给定装载约束的条件下，确定最优箱型及其相应的最优装箱方案。其中，最优箱型编号记为I*；最优装箱方案记为P*。因此，本文数学模型的决策变量为选用箱型编号I和对应装箱方案P。

1.2.2 目标函数

由问题背景和求解目标可得本文所研究问题为多重优化问题，其中多重优化如下。

第1重优化 (所装物品数量最多)。

由于第1重优化为主优化目标，上述两重优化目标函数可整合为单目标权重优化函数。

1.2.3 数学模型

本文可行装箱方案必须满足如下两个条件：1) 任一装载的物品不能与其他装载物品或者箱子互相重叠；2) 所有装载的物品以与箱子平行的方式装载。

根据上述装箱约束条件和目标函数，建立如下数学模型。

上述约束中，式(1)为目标函数，目标为装载物品数量最多的基础上装载率最大；式(2)表示箱子最大容积约束；式(3) ～ (5)表示每个物品平行或正交装载于箱子内，由于当且仅当式(6)中6个符号函数之和为6时，物品ti近原点坐标 (xi,yi,zi)被另一物品包含；同理，式(7)是对物品ti远原点坐标的约束，因此两式共同表示物品间不互相重叠；式(8) ～ (9)表示物品装载于箱子内。

2 算法设计

本文针对上述问题和数学模型，提出一种基于空间矩阵的大规模邻域搜索装箱算法，以便快速有效地求解问题。

在之前的三维装箱问题研究中，相关算法大多由基于结构假定方式的装箱检验算法和基于启发式规则的装箱方案路径搜索算法组成，并通过编码译码规则实现前者所得的解空间转化成后者所能处理的搜索空间。而本文则对上述算法进行创新，提出一种新的结构假定方式空间矩阵表征方式用于快速装箱检验，并提出基于物品朝向的编码译码规则以控制算法的迭代次数，最后通过定义关键元素选取方式，首次引入大规模邻域搜索算法以优化传统启发式算法对装箱序列的路径搜索过程。

2.1 空间矩阵表征方式

由于电商领域装箱订单具有个性化程度高特点，传统的结构假定方式不适用于电商问题背景；且由于三维装箱在空间布局中，干涉计算量较多，简单的坐标表示不利于问题求解。因此，本文首先提出空间矩阵表征方式用于装箱问题中的结构假定。Ngoi等[14]在夹具设计应用中提出一种基于可变正交单元的细胞分解、实体模型表征方式，本文则在其基础上提出应用于三维装箱问题中的空间矩阵表征方式，从而快速更新箱内空间使用情况，查找可用空间，便于装箱检验的模拟进行。空间矩阵外框架如图1所示。

图1 空间矩阵外框架Figure 1 Spatial matrix's outer frame

2.1.1 相关介绍

空间矩阵将根据内部物品装箱情况分解成多个二维矩阵，每个二维矩阵表示某个高度范围内的箱内空间占用情况，具体表征方式如下。同时，由于空间矩阵中可用空间可视为由多个长方体组成，因此采用同上文物品ti空间信息一样的表述方式描述可用空间位置。

步骤1 构建当前空间矩阵外框架。

1) 整理汇总X、Y、Z轴参考量。根据所选箱子bI及其当前已装载物品ti， 将LI及各物品的xi、xi+lXi汇 总成X轴参考量，将WI及各物品的yi、yi+lYi汇总成Y轴参考量，将HI及各物品的zi、zi+lZi汇总成Z轴参考量。

3) 根据X、Y、Z轴参考量生成如图1所示空间矩阵外框架，并填充0表示空间均无占用。

步骤2 确定每一层平面矩阵所包含物品。

1)Z轴参考量分别对应各层平面矩阵层高。

2) 物品ti如满足条件zi＜ZM≤zi+lZi，则其被第M层平面矩阵包含。

步骤3 填充各层平面矩阵以表示空间占用情况。

1) 根据每层矩阵所包含的相应物品ti，确定其在相应平面矩阵的行起点、列起点、行终点、列终点，并填充1表示空间被占用。

2) 确定行起点，若xi=Xr,Xr∈X′，则其行起点为第r+ 1行；确定列起点，若yi=Yr,Yr∈Y′，则其列起点为第r+ 1列。

3) 确定行终点，若xi+lXi=Xs,Xs∈X′，则其行终点为第s行；确定列终点，若yi+lYi=Ys,Ys∈Y′，则其行终点为第s列。

步骤4 寻找空间矩阵内可用空间。

1) 记空间矩阵第x行 、第y列、第z层元素为Fxyz， 其中，x=1,···,x′；y=1,···,y′；z=1,...,z′。

2) ∀x∈{1,···,x′}，y∈{1,···,y′}，z∈{1,···,z′}，若Fxyz=0， 则有单位长方体子空间(Xx-1,Yy-1,Zz-1,Xx,Yy,Zz)， 并记为sxyz。

3) 汇总可用单位长方体子空间，并基于预设规则将其合并为若干个较大的长方体子空间，组成可用空间集合S，其所含元素表示为S[p]，p表示装箱检验时，该子空间在集合中被选择的顺序，并定义其长宽高S[p]l≥S[p]w≥S[p]z，在X、Y、Z轴上长度S[p]X、S[p]Y、S[p]Z。装箱检验中，物品将按照集合中的顺序与可用空间逐一进行检验。

2.1.2 使用示例

空间矩阵表征方式运用示例如下。当前空间矩阵内装箱情况如图2所示。已知X′={0,20,30,50}，Y′={0,10,20,40}，Z′={0,5,10,30}。构建空间矩阵外框架，并填充各层平面矩阵空间占用情况，得空间矩阵如图3所示。

图2 三维装箱示例Figure 2 3D packing example

图3 空间矩阵示例Figure 3 Space matrix example

2.2 算法优化设计

2.2.1 编码规则

启发式算法在三维装箱问题中运用成功的关键在于通过编码规则将问题的可行解从其解空间转化到算法能处理的搜索空间[15]。在之前的三维装箱问题研究中，大多以有序物品集合作为编码方式，实现启发式算法的搜索空间和装箱方案可行解空间的相互转化。而本文为简化模型，便于搜索，提出一种新的算法编码，以有朝向约束的物品(简称物品(朝向))作为搜索空间，以有序的物品(朝向)集合作为可行解。

由于物品ti的可旋转性，lXi、lYi、lZi会因摆放朝向的变化而改变。根据物品需平行或正交装载于箱子内的约束条件，物品有6种摆放朝向，故lXi、lYi、lZi也有6种组合。因此，基于物品集合T={t1,t2,···,tn}建立集合T′={1,2,···,6n}，其中，T′的元素表示物品(朝向)，ti的6种朝向分别对应集合T′中的 6i-5至 6i，从而避免在后续算法中考虑物品的可旋转性。同时，构造函数i(t′)=(t′-1)//6+1，其中，//为整除符号；t′∈T′，i(t′)表 示物品(朝向)编号t′对应的物品编号。并定义物品每种摆放朝向下X、Y、Z轴上长度与长宽高的对应关系，如式(10)所示，其中，%为取余符号。

预设装箱序列Q是一个过渡量，既是装箱方案路径搜索算法的输出量，也是装箱检验算法的输入量，表示算法根据启发式规则路径搜索出的未经过实际检验的预设装箱方案。Q为一个包含n个元素的有序集合，其第k个元素表示为Q[k]，表示在后续装箱检验的第k阶段被检验能否装入箱子的物品(朝向)编号。为避免迭代次数超过装箱序列长度，预设序列Q基于上述规则进行编码，Q[k]∈t，从而通过避免在装箱过程中考虑物品旋转性以控制迭代次数，其中装箱检验由装箱算法实现。

2.2.2 译码规则

在装箱方案路径搜索算法中，编码规则实现了问题的可行解从其解空间到算法能处理的搜索空间的转化，从而得出基于启发式规则搜索出的预设装箱序列Q。而在装箱检验算法中，则需要通过译码规则将Q转化成空间矩阵可以模拟装载的各物品装箱顺序和朝向信息。

译码规则如式(11)所示，首先将Q[k]译码成物品ti(Q[k])的lXi(Q[k])、lYi(Q[k])、lZi(Q[k])信息，再和当前空间矩阵Space的 可用空间 SUB进 行装箱检验，并生成ti(Q[k])的xi(Q[k])、yi(Q[k])、zi(Q[k])信息，从而实现从预设装箱序列Q到各物品实际空间信息的转换。

Q中各元素逐一译码并装箱检验后，求得该预设序列所对应的各物品空间信息。为便于后续启发式算法对装箱方案的迭代优化，对上述各物品空间信息再逐一编码生成实际装箱方案P。P是与Q对应的包含n个元素的有序集合，表示一种可行的装箱方案，其第k个元素表示为P[k]。P[k]为实际装箱的第k阶段中，实际装入箱子的物品(朝向)编号，其值可能会因为装箱检验的调整与Q[k]不一致。

2.2.3 大规模邻域搜索算法优化设计

本文在传统启发式算法搜索装箱方案的过程中，通过对关键元素选取和相关度函数定义，引入大规模邻域搜索算法。

1) 大规模邻域搜索算法关键元素选取和相关度函数定义。

分析目标函数 m axU(I,P)=A+E，其中，E∈[0,1]，故A的取值即箱子所装物品数对目标函数值起关键影响。因此，P中无法成功装箱的元素即为关键元素，关键元素集合表示为R={P[k]|P[k]＜0,P[k]∈P}，其第d个元素记为R[d]，R中元素数量记为D。

2) 相关度函数定义。

2.3 算法流程描述

2.3.1 子算法装箱检验算法

步骤1 初始化k=1， 输入预设装箱方案Q和被选箱型I。

步骤2 根据所选箱子bI构建空间矩阵。

步骤3 根据当前所装物品信息及空间矩阵表征方式规则，更新空间矩阵及其可用空间集合S。

步 骤4 将Q[k]解 码 成 物 品ti(Q[k])的lXi(Q[k])、lYi(Q[k])、lZi(Q[k])， 并将其解码信息与S进行装箱检验，根据检验情况调整Q[k]生 成相应P[k]， 并确定ti(Q[k])的xi(Q[k])、yi(Q[k])、zi(Q[k])。

1) 初始化p=1， 当前S中所含子空间元素数量为s。

2) 根据物品ti(Q[k])的 尺寸信息，若S[p]l≥li(Q[k])、S[p]w≥wi(Q[k])、S[p]h≥hi(Q[k])， 则ti(Q[k])可装载于可用空间S[p]中 ，否则p=p+1，跳至4)。

3) 根据物品ti(Q[k])的朝向信息，若物品可直接装箱，则P[k]=Q[k]， 若物品旋转后可装箱，则P[k]∈{6i(Q[k])-5,6i(Q[k])-4,···,6i(Q[k])}。步骤4结束。

4) 若p≤s，返回2)。

5) 物品ti(Q[k])始 终无法装箱，P[k]=-Q[k]，负值表示物品ti(Q[k])在 方案P中无法装箱。步骤4结束。

步骤5 如果k＜n，n为待装载物品数量，即未完成所有物品装箱检验，k=k+1，返回步骤3。

步骤6 根据空间矩阵表征方式规则，获得空间矩阵当前所装物品信息，并输出实际装箱方案P和目标函数值U(I,P)，算法结束。

2.3.2 基于三维矩阵的大规模邻域搜索算法

步骤1 确定最小可用箱型编号I。

步骤2 启发式算法初始化，启发式迭代次数m=0。

步骤3 根据蚁群算法信息素浓度规则生成e种预设装箱序列{Q1,Q2,···,Qe}。

步骤4 根据输入被选箱型I和预设装箱序列{Q1,Q2,···,Qe}，调用装箱检验算法输出实际装箱方案{P1,P2,···,Pe} 和 目标函数值 {U1,U2,···,Ue}，并确定该次迭代最优目标函数值U*。

U*=max{U1,U2,···,Ue}。

步骤5 由于最优装箱方案可能并不唯一，根据U*生 成最优装箱方案集合P¯*和其对应目标函数值集合U¯*，P¯*[j]、U¯*[j]分 别表示其第j个元素，J为其所含元素数量。如果U*＞n，则完成单箱装载所有物品，算法结束。

1) 初始化p=1，j=1。

2) 若Up=U*， 则P¯*[j]=Pp，U¯*[j]=U*。

3) 若p＜e， 则p=p+1，返回2)，否则，确定集合P¯*和U¯*。

4) 如 果U*＞n， 则I*=I，P*∈P¯*， 输出I*和P*，算法结束，否则步骤5结束，算法继续。

步骤6 通过大规模邻域搜索算法优化集合P¯*和相应目标函数值集合U¯*。

1) 初始化j=1。

2) 通过大规模邻域搜索算法优化装箱方案P¯*[j]，并初始化大规模邻域搜索迭代次数r=0。

3) 根据前文所述关键元素选取规则和相关度函数定义，确定并选取P¯*[j]中若干关键元素并计算各关键元素相关度，并保留部分相关度较高元素生成关键元素集合R。根据R中所保留关键元素，P¯*[j]中相应元素依次与非关键元素随机置换重组。如果U(I,P¯*[j])＞U¯*[j]， 则更新优化P¯*[j]、U¯*[j]，并转至4)，否则，P¯*[j]保持不变，跳至5)。

4) 如 果U¯*[j]＞n， 则I*=I，P*=P¯*[j]，输 出I*和P*，算法结束，否则，算法继续。

5) 如果r超过给定值或多次迭代没有新的U¯*[j]产生，则当前装箱方案无大规模邻域搜索算法优化可能，转至6)，否则，返回3)，r=r+1。

6) 若j＜J，则j=j+1，返回2)，否则，更新最优目标函数值U*=maxU¯*及其对应最优装箱方案P¯*，步骤6结束。

步骤7 根据启发式规则，强化最优装箱方案集合P¯*对应路径信息素浓度。

步骤8 如果m超过给定值或多次迭代没有新的U*产生，则当前箱型限制下无更优方案，否则，返回步骤2，m=m+1。

步骤9 如果I＞N，无更大箱型可以选择，则I*=I，输出I*和P*，算法结束，否则，返回步骤2，I=I+1。

3 数值实验

本文的组合启发式算法以Python实现，程序试验运行在Intel Core i7-8750H 2.20 GHZ的处理器上。本文针对电商领域所提出的组合启发式算法，在电商领域3D-MBSBPP中具有良好表现。在实验中，为便于检验算法性能，本文组合启发算法的路径搜索算法部分拟采用蚁群算法作为大规模邻域搜索算法的优化对象，同时将基于电商领域物流装箱订单数据，与之前学者所提出的三维装箱算法、当前电商物流企业常用装箱软件进行性能比较。

3.1 算例说明

实验采用的标准算例集来自电商物流企业，共计49 591个客户订单和17种可选箱型，每个订单均可看作有17种箱型可选的3D-MBSBPP算例。此外，由于每个订单所含物品总体积小于最大箱型体积，且问题背景以单箱装载尽可能多物品为目标，因此装箱问题将以订单所含物品全部单箱装载成功作为达标情况并统计，从而简单直观地比较算法性能。

订单来自于电商物流企业实际订单，订单样本具有高度个性化特点，订单间品类数量波动大，订单所含品类最多达44种，所含物品数量最多达208个，品类数量概率分布如图4所示，物品数量概率分布如图5所示。箱型选择较多、长宽高比例特点明显，详细情况如表1所示。

表1 箱型详细数据Table 1 Box type details

同时，为了便于比较本文算法和同类型装箱算法、商用软件在求解不同复杂程度的多箱型三维装箱问题时的性能，基于图4和图5，将算例集按照品类数量分成7组，详细情况如表2所示，按照物品数量分成9组，详细情况如表3所示。

表2 标准算例集(按品类数量分组)Table 2 Standard example set (group by category quantity)

表3 标准算例集(按物品数量分组)Table 3 Standard example set (group by item quantity)

图4 订单品类数量概率分布Figure 4 Category quantity probability distribution of order

图5 订单物品数量概率分布Figure 5 Items quantity probability distribution of orders

此外，在上述的标准算例集中，虽然算例数量庞大，特点明显，但是其仅能实现本文算法和同类型装箱算法、商用软件的性能比较，无法实现和精确解的比较。因此，本文根据该电商物流企业的实际检验反馈，从49 591个标准算例中，遴选出其中58个算例作为特殊算例。这58个特殊算例虽然相较标准算例集，数量较少，但是经由人工装箱检验后理论精确解为100%(即所有装箱订单均可实现单箱全部装载)，且当前该企业所有商用装箱软件均无法对其实现单箱全部装载，具有较大的比较价值。

3.2 比较实验

首先将基于前文分组后的标准算例集，分别进行本文算法和其他学者之前所提出的装箱算法、装箱软件的比较实验和结果分析，从而充分检验本文算法在求解不同品类数量复杂程度的3D-MBSBPP时的性能，比较结果如表4、表5所示。

表4 与其他算法的结果比较(标准算例集)Table 4 Results compared with other algorithms (standard example set)

表5 与商用软件的达标率比较(标准算例集)Table 5 Compliance rate compared with commercial softwares(standard example set) %

根据比较结果，在达标率方面，本文算法求解电商物流领域装箱问题时的性能优于其他算法和装箱软件，而且随着装箱问题复杂程度的提升，性能优势越发明显。此外，在求解速度方面，虽然本文算法慢于部分算法，但是同样随着装箱问题复杂程度的提升，求解速度的差距也在逐渐缩小。因此，本文算法相比之前针对弱异构性问题设计的算法、软件，能更好地满足高度个性化的电商物流邻域订单中强异构性和弱异构性兼有的要求。

最后，将基于特殊算例集对本文算法和其他装箱算法进行进一步性能比较，比较结果如表6所示。根据比较结果，本文算法达标率明显超过其他算法，充分体现出其性能的优越。而且，在求解商用软件无法解决而实际可解的装箱问题时，本文算法的达标率非常接近理论精确解100%，进一步证明本文算法对电商物流领域3D-MBSBPP的求解非常接近理论最优解。

表6 与其他算法的结果比较(特殊算例集)Table 6 Results compared with other algorithms(special example set)

4 结论

本文提出一种针对个性化程度高的电商领域3D-MBSBPP的组合启发式算法。首先，根据电商物流背景建立数学模型；其次，以物品(朝向)作为算法搜索空间，建立编码译码规则及预设装箱序列、实际装箱方案等数据结构，并提出基于空间矩阵表征方式的装箱检验算法，快速实现从预设序列到实际方案的转换；最后，提出一种大规模邻域搜索算法，用于优化3D-MBSBPP中启发式算法的路径搜索过程。实验测试表明，本文所提出的组合启发式算法在求解电商物流3D-MBSBPP中，精度超过传统三维装箱算法，且运算速度较为理想。但是，本文所涉及的三维装箱问题约束较少，且大规模邻域搜索算法的重构规则较为简单，还需要进一步的调试参数、优化算法。