考虑支撑面约束的三维装箱问题快速求解方法

张 莹，刘二超，戚铭尧

（清华大学 深圳研究生院，现代物流研究中心，广东 深圳 518055）

1 引言

集装箱是现代重要的运输工具，在市场竞争日趋激烈的当今社会，如何在货物运输这一重要环节减低成本与费用，是进出口和运输等行业企业普遍关心的问题.事实上，集装箱的装箱问题在大部分企业中一直得不到很好解决，往往是凭经验作业，造成空间利用率低，计算耗时费力，作业缺乏标准，货物摆放混乱.在解决具有规则形状的货物在货柜集装箱、厢式货车、包装箱、托盘中的优化装箱问题中，如果通过三维装箱算法，快速设计装箱方案，可以优化空间效率，节约运费，规范作业，提高车辆配载率.

三维装箱(three-dimensional bin packing,3DBP)问题指如何用最少的车厢将一系列数目为n的三维货物全部装载，同时满足给定的约束条件，如任意两个货物不能有空间重叠，每个货物底部的支撑面积必须达到其底面面积的一定比例.根据Wäscher,G等[1]对“切割和装载”问题所进行的分类，三维装箱(3D-BP)问题属于单箱尺寸装箱问题(SBSBPP).

三维装箱问题最早由Martello等[2]于2000年提出.该文中，作者首先给出三维装箱问题下界的求解方法，并提出基于基本点的构造启发式算法求解3D-BP问题，最后设计了九种算例来验证算法，2000年以后求解三维装箱问题的算法大多基于该算例进行验证和比较.Faroe等[3]提出了引导邻域搜索(GLS)启发式方法，该算法把求解过程分为两步，构造阶段和邻域搜索阶段，通过迭代以逐步减少车厢的方法来达到最优.Grainic T G等[4]提出关键点(Extreme Points)的概念来确定货物摆放位置，对Martello等提出的基本点做了改进，增加了货物摆放位置，并且装箱前将货物按照一定规则进行排序，结果表明，该措施显著减少了车厢使用数目.陈实[5]、王磊[6]提出了一种新的装箱启发式算法，这种装箱启发式算法考虑了更多的关键点，所以使装箱检验的效果提高从而使求解结果取得了改进，同时，该算法也使求解时间变得更长.Grainic T G等[7]提出了两阶段禁忌搜索方法，构造阶段采用基于关键点的装箱方法得到初始解，然后采用两阶段禁忌搜索对初始解进行改进，第一阶段给每个车厢分配货物，第二阶段对分配结果进行装箱测试.Parreño,F等[8]将贪婪搜索算法(GRSAP)应用于三维装箱问题，并首次提出装载空间的概念.Mack D等[9]结合装箱(Container Loading)问题和一维装箱(1D-BP)问题提出一种组合启发式算法求解三维装箱问题.该算法求解速度快，可用于求解货物数量大的三维装箱问题.

根据货物是否可以翻转90°，Boschetti[10]将3DBP分成3BPOF和3BPMF，并分别针对3BPOF和3BPMF设计了更好的下界函数.

本文将基于带支撑面的装载空间来解决带有支撑限制的三维装箱问题.

2 带支撑面的装载空间

带有支撑底面的装载空间如图1所示，该空间外观是一个长方体，其底面阴影部分表示已知的提供支撑的部分，该阴影部分由车厢底面或者放入车厢的货物的上表面提供，阴影部分向长方体的各个侧面有一定的可拓展的空间，这部分空间不确定是否有支撑.

该空间可由以下7个属性来表示：location(x,y,z)，shape(x,y,z)，back，left，front，right和 fragility.其中location(x,y,z)表示图1中所示的点在三维坐标系中的坐标；shape(x,y,z)表示支撑空间的大小，x代表阴影部分的宽，z代表阴影部分的长，y代表该空间结构的高；back表示从阴影部分向长方体的背面可以拓展的可能无支撑空间的长；left表示从阴影部分向长方体的左侧可以拓展的可能无支撑空间的宽；front表示从阴影部分向长方体的前面可以拓展的可能无支撑空间的长；right表示从阴影部分向长方体的右侧可以拓展的可能无支撑的空间的宽；fragility表示提供阴影部分支撑面所对应的货物的易碎性.对于没有摆放货物的一个长、宽、高分别为100、100、100的车厢而言，它构成了一个带支撑底面的装载空间，其属性为：location=(0,0,0)，shape=(100,100,100)，back=0，left=0，front=0，right=0，fragility=0.

图1 带支撑面的装载空间Fig.1 Loading space with support surface

2.1 判断两立方体之间是否有空间重叠

图2 两个物体在车厢底面投影关系Fig.2 Projection of two items on the bottom

2.2 装载空间更新算法

开始（输入：空间集合subBins，当前装载货物item，货物装载位置location）.

Step 1 新建一个空的空间集合newsubBins.

Step 2 依次考察subBins中的每一个空间结构subBin.

如果subBin与item有空间重叠，将该subBin标记为可删除状态，对subBin进行切割更新：如果货物的后表面（左侧面、前表面、右侧面、上表面、下表面）所在的平面切割subBin会形成新的空间结构newsubBin，则将newsubBin增加到newsubBins中.

Step 3 从subBins中删除掉标记为可删除状态的subBin.

Step 4 将newsubBins中的每一个subBin增加到subBins中.

Step 5 合并subBins中可以进行合并的装载空间.结束.

3 基于带支撑面的装载空间求解三维装箱问题

3.1 货物排序

不同的货物排序方法，对最终的装箱结果影响很大.借鉴参考文献[4]，本文采用如表1所示的四种货物排序方法，为了对比，本文还考虑不排序的情况.

表1 货物排序方法Table 1 Sorting Method

表中，“主原则”是主要的排序依据，当两个货物在“主原则”列中的属性相等时，则依据“次原则”进行排序，并且均按降序排列.如“体积-高”排序方法：根据货物体积大小进行排列，体积大的货物排在前面，体积小的排在后面；如果两个货物体积相等，则根据货物高进行排序，较高的货物排在前面，较矮的货物排在后面.

高-体积、面积-高、高-面积排序方法类推即可.

3.2 装载空间选择

[4，5]选择关键点的思想，运用于装载空间的选择并在它们的基础上进行拓展，形成更多的选择策略，分别如下：

ZXY：检验某个货物能否装载时，如果当前空间集合中有多个空间结构能够容纳该货物，则将该货物装载在这些可以容纳该货物的装载空间中属性location的z值最小的装载空间中，如果仍存在多个这样的装载空间，则考虑这些装载空间中x值最小的，如果还存在多个，则考虑y值最小的.

ZYX，XZY，XYZ三种选择策略和上述策略类似，只是在选择装载空间时，考虑属性location的x、y、z顺序不一样.

TouchX：检验某个货物能否装载时如果当前空间集合中有多个装载空间能够容纳该货物，则计算该货物与车厢中已经装载的其它货物和车厢侧面的接触面积之和（不包括与车厢底面的接触面积），选择接触面积之和最小的装载空间来摆放该货物，但如有多个这样装载空间，则选择属性lo-cation中x值最小的一个.

TouchNX，TouchZ，TouchNZ三种选择策略和上述策略类似，在计算接触面积时，TouchNX不考虑与车型侧面的接触面积；存在多个接触面积最小的装载空间时，TouchZ选择location属性中z值最小的一个；TouchNZ不考虑与车型侧面的接触面积.

MaxFit：假设货物的长、宽、高分别为l、w、h，装载空间属性shape的长宽高分别为L、W、H，则货物形状与装载空间形状的匹配值fitness=min(l/L,L/l)·min(w/W,W/w)·min(h/H,H/h).当存在多个装载空间可以装载某个货物时，选择fitness值最大的来装载该货物.

3.3 装载位置选择

检验一空间能否装载某货物时，分四种情况，考虑如图3所示关键点，图中3、5关键点位置根据支撑系数来确定.

图3 不同情况下的装载位置Fig.3 Loading position under different occasions

3.4 装载算法流程

开始（输入：物品装载列表itemlist）.

Step 1 按照某一物品排序策略对itemlist进行排序.

Step 2 初始化空间集合列表subBinsList（空间集合数目为n，n为货物数目），所有sub-Bins的num属性均为0.

Step 3 给subBinsList中每个空间集合加入一个由车厢本身所构成的subBin.

Step 4 依次装载itemlist中的每一个物品item.

Step 4.1 依次检验subBinsList中的每一个subBins.

Step 4.1.1 将subBins中的subBin按照某一装载空间选择策略进行排序.

Step 4.1.2 依次检验subBins中的每一个subBin

如果当前subBin不能装载当前物品item，检验下一个subBin.

如果能够装载，根据当前物品的摆放位置和当前的空间集合对装载空间进行更新；如果当前subBins第一次装载货物，则将该subBins的num属性设为1；转Step 4.

Step 4.2 如果该subBins不能装载，则检验下一个subBins；否则转Step 4.

Step 5 返回subBins中，属性num为1的空间集合数量，表示全部装载完货物所需车厢数.结束.

4 算例分析

本文所提出的算法用C#语言在Visual Studio 2008开发平台下实现，算法执行的平台环境如下：CPU是酷睿2双核T6500处理器，主频为2.1GHz，内存为2GB，操作系统是Windows7系统.

4.1 测试数据

本文所使用测试数据由Martello等人于2000年提出，下载网址：http://www.diku.dk/～pisinger/codes.html.

该测试数据分为八组，先列举五种数据类型（表2中，w、l和h分别表示单个货物的宽、长、高，W、L、H分别表示车厢的宽、长、高）.八组数据分别如下：

表2 五种数据类型Table 2 Five data types

第一组：60%来自类型一，10%分别来自类型二、三、四、五，W=L=H=100；

第二组：60%来自类型二，10%分别来自类型一、三、四、五，W=L=H=100；

第三组：60%来自类型三，10%分别来自类型一、二、四、五，W=L=H=100；

第四组：60%来自类型四，10%分别来自类型一、二、三、五，W=L=H=100；

第五组：60%来自类型五，10%分别来自类型一、二、三、四，W=L=H=100；

第六组 ：w、l和 h随机 在[1,10]选 取 ，W=L=H=10；

第七组 ：w、l和 h随机 在[1,40]选 取 ，W=L=H=40；

第八组：w、l和h随机在[1,100]选取，W=L=H=100.

由于第二、三组数据和第一组数据类似，这里不再考虑第二、三组数据.针对其它六组数据，货物数量分为 50、100、150、200四种情况，共24种组合，每种组合又随机产生10组数据，一共240套数据.

4.2 实验结果及分析

支撑系数设为0.75，即要求每个货物的底面至少有75%的面积处于被支撑状态，不考虑转向，装载策略为ZXY时，各种组合使用车厢数及车厢总数如表3所示.

表3 支撑系数设为0.75、不考虑转向、装载策略为ZXYZXY时计算结果Table 3 Loading coefficient=0.75,loading strategy=ZXYZXY,forbid rotation

表3中第一到三列的组、车厢尺寸、货物数分别表示第几组数据、车厢长宽高尺寸、货物数量；第四到第八列表示高-体积、体积-高、面积-高、高-面积、无排序五种货物排序策略所使用的车厢数目平均值（对应每一组数据，当货物数量为50、100、150、200四种情况时，取10套数据的平均值）.由表3可知，在不考虑转向，支撑系数为0.75，装载策略为ZXY时，采用体积-高的排序策略结果最好.

其它几种装载策略所使用车厢总数如表4所示.

表4 支撑系数设为0.75、不考虑转向、几种装载策略计算结果Table 4 Loading coefficient=0.75,forbid rotation,different loading strategies

表4中只列出了各种装载策略所对应的几种货物排序策略时使用车厢数目总值.由表4可看出，几种策略均是采用体积-高的货物排序策略结果最好，但采用面积-高的货物排序策略结果与前者差别不大.同时由表4还可知道当装载策略为XYZ，货物排序策略为体积-高时，所使用车厢总数为763.4，使用车厢数目最少.

支撑系数设为0.75，考虑转向，装载策略为ZXY时，各种组合使用车厢数及车厢总数如表5所示.

表5 支撑系数设为0.75、考虑转向、装载策略为ZXYZXY时计算结果Table 5 Loading coefficient=0.75,loading strategy=ZXYZXY,allow rotation

表5中各列的含义和表3相同.由表5可知，在考虑转向，支撑系数为0.75，装载策略为ZXY时，采用体积-高的货物排序策略结果最好，但采用面积-高的货物排序策略结果与前者差别不大.

考虑转向，装载策略为ZXY，不同支撑率情况下所使用车厢总数如表6所示.

表6 考虑转向、装载策略为ZXYZXY、不同支撑率计算结果Table 6 Loading Strategy=ZXYZXY,Allow Rotation,different Loading Coefficient

由表6可知，在考虑转向，装载策略为ZXY时，支撑系数为0.6、0.75时，采用体积-高的货物排序策略结果最好；但支撑系数为0.9、1时采用面积-高的货物排序策略结果最好.由此可知，当对支撑要求越高，采用面积-高的货物排序策略计算结果更加经济.

考虑易碎性情况，假设0为非易碎，1为易碎，240套数据假设前20%为易碎货物，后80%为非易碎货物，考虑转向、装载策略为ZXY、支撑率为0.75时，五种货物排序策略所使用车厢总数分别为825（高-体积）、785.2（体积-高）、766.1（面积-高）、825（高-面积）、853.4（无排序）.由此可知，在考虑易碎性时，面积-高的货物排序策略明显好于体积-高的货物排序策略.

4.3 计算效率及对比分析

在对所有算例进行计算时，采用不同策略进行组合，每套数据的平均计算时间均不会超过0.1秒，因此该算法计算效率较高.

Martello[2]提出基于基本点的构造启发式算法，且该算法未考虑转向，对其设计的标杆数据进行求解，所使用车厢总数为769.9.由表3和表4可知，对同样的数据集，本文所提出的算法即便考虑了支撑面积的限制，在采用体积-高和面积-高两种货物排序方法时，几种装载策略所使用车厢总数依然比Martello得到的结果优.因此可认为本文算法计算结果达到较好效果.

5 研究结论

本文提出了带支撑面的装载空间这一概念，并应用于三维装箱问题，结果表明，相比关键点等思想，本文提出的方法计算结果质量更高，而且计算速度快，对于实际应用及后续的研究有很大的借鉴意义.下一步可以考虑在本文结果的基础上用启发式算法再进行优化改进，然后集成开发装箱软件，并进行三维显示、报表输出，方便物流计划.

参考文献:

[1]Wäscher G,Haußner H,Schumann H.An improved ty⁃pology of cutting and packing problems[J].European Journal of Operational Research,2007,183(3):1109-1130.

[2]Martello S,Pisinger D,Vigo D.The three-dimensional bin packing problem[J].Operations Research,2000,48(2):256-267.

[3]Faroe O,Pisinger D,Zachariasen M.Guided local search for the three-dimensional bin-packing problem[J].IN⁃FORMS Journal on Computing,2003,15(3):267-283.

[4]Crainic T G,Perboli G,Tadei R.Extreme point-based heuristics for three-dimensional bin packing[J].Informs Journal on Computing,2008,20(3):368-384.

[5]陈实.带有三维装箱能力约束的车辆路径问题的算法研究[D].中山大学,2008.[CHEN S.Research on algo⁃rithm for three-dimensional loading capacitated vehicle routing problem[D].Sun Yat-Sen University,2008.]

[6]王磊.车辆路径与三维装箱混合问题(3L-CVRP)的研究[D].中山大学,2009.[WANG L.An integrated re⁃search for the capacitated vehicle routing problem with container loading[D].Sun Yat-Sen University,2009.]

[7]Crainic T G,Perboli G,Tadei R.TS2PACK:A two-level tabu search for the three-dimensional bin packing prob⁃lem[J].European Journal of Operational Research,2009,195(3):744-760.

[8]Parreño F,Alvarez-Valdés R,Oliveira J F,et al.A hy⁃brid GRASP/VND algorithm for two-and three-dimen⁃sional bin packing[J].Annals of Operations Research,2010,179(1):203-220.

[9]Mack D,Bortfeldt A.A heuristic for solving large bin packing problems in two and three dimensions[J].Cen⁃tral European Journal of Operations Research,2012,20(2):337-354.

[10]Boschetti M A.New lower bounds for the three-dimen⁃sional finite bin packing problem[J].Discrete Applied Mathematics,2004,140(1):241-258.