基于三维移动模式序列与密母算法的三维装箱方法

摘要

本发明公开了一种基于三维移动模式序列与密母算法的三维装箱方法，主要解决现有技术对三维装箱容器体积利用率低的问题。其实现步骤是:1.设定各个参数；2.随机产生初始种群，计算种群中个体的适应度；3.判断是否满足终止条件，若是，执行步骤4，否则，执行步骤9；4.用二元锦标赛法对个体进行选择；5.对个体进行交叉，重新计算个体适应度值；6.对个体进行变异，重新计算个体适应度值；7.保存当代中的适应度值最大的个体；8.迭代次数自加1，返回步骤3；9.用爬山法对适应度值最大的个体进行优化，输出优化后的装箱结果。本发明能提高容器的体积利用率，不仅可用于解决装箱问题，还可用于解决其他组合优化问题。

说明书

技术领域

本发明属于计算机优化技术领域，进一步涉及三维装箱方法，可用于优化箱子放置的 坐标，实现物流等行业装箱的优化。

背景技术

三维装箱3D-BPP是工业生产中常遇到的问题，如船舶集装箱装卸、飞机货运管理、 仓库管理等。在货物装载以及运输过程中，资源以及运输空间的高效利用是公司间的核心 竞争力。因此，由于其实际的需求，寻求一种合理有效的放置策略仍然是研究的重要方向。

Karabulut等发表的“A hybrid genetic algorithm for packing in 3D with deepest bottom left  with fill method”(《Advances in Information Systems》，文章编号:441-450(2004))，该文章的 核心是将箱子放置在三维空间中，使得坐标点z最小，而后y最小，最后x最小，该算法 可以产生很好的效果，但每放入一个箱子，就要记录以及删除极点，即是记录可以放置箱 子的点，以及已经放置了箱子的点并将其删除，最后要重新给极点排序，时间复杂度很高。

张德富等发表的“求解三维装箱问题的混合模拟退火算法”(《计算机学报》，文章编号: 2147-2156(2009)32-11)中提出了复合块作为放置策略，采用模拟退火算法优化3D-BPP。 该算法研究的是带有稳定性和方向约束的单一三维装箱问题，对部分弱异构箱子可以得到 好的填充率，而对于强异构箱子而言，若采用复合块的放置策略，复合块中会产生空隙 并且对于每个复合块而言不能够再次填充，从而使得填充率降低。

何琨等发表的“基于长方体Packing问题的捆绑穴度算法”(《软件学报》，文章编号： 842-851(2011)2-5)中公开了一种用捆绑穴度算法对三维装箱问题进行优化的方法。该方法 的实现过程为，首先对所有箱子进行捆绑，形成新的箱子组合，其次采用穴度算法对三维 装箱问题进行优化。该方法的不足之处在于，只适用于弱异构三维装箱问题，对于箱子种 类多的装箱其获得的体积利用率低。

发明内容

本发明的目的在于针对上述已有技术的不足，提出一种基于三维移动模式序列与密母 算法的三维装箱方法，以减小空间复杂度，提高容器的体积利用率。

为实现上述目的，本发明的技术方案包括如下步骤：

(1)参数设定：

设N为遗传算法中种群中的个体数，N为大于或等于2的整数，M为每个个体中箱子 个数，M为大于或等于1的整数；用W、H、L分别表示装箱容器的宽、高、长；Mgen 表示进化的最大代数，pc0为箱子顺序交叉概率，pc1为移动模式交叉概率，pc2为旋转模 式交叉概率，其中pc0、pc1、pc2为0到1之间的实数；pm为变异概率，取值为0到1 之间的实数；w、h、l分别为箱子的宽、高、长，x、y、z为箱子放置坐标点的值，m为 移动模式值，取值为0、1、2；r为旋转模式值，取值为0～5之间的整数；num为箱子的序 号；TEM为爬山法的迭代次数；RX、RY、RZ分别表示最小立方体包络的宽、高、长； gen为进化代数；结构体数组best[N]用于保存每一代中适应度最大的个体，结构体Best用 于保存爬山法得到的适应度最大的个体；

(2)随机产生初始种群，即随机产生箱子序号0～M-1的排列，随机产生旋转模式0～5 的排列，随机产生移动模式0～2的排列，产生N个这样的个体组成初始种群；计算每个个 体的适应度值，设gen＝0；

(3)判断是否满足gen<Mgen，若是，执行步骤(4)，否则执行步骤(9)；

(4)根据种群中每个个体的适应度值，用二元锦标赛法从中选择N个适应度值大的个 体；

(5)随机产生0到1之间的随机数temp；随机选择两个个体，若temp<pc0，则对这两 个个体的箱子顺序进行交叉；若temp<pc1则对这两个个体的移动模式进行交叉；若 temp<pc2，则对这两个个体的旋转模式进行交叉，并重新计算这两个个体的适应度值；

(6)随机产生0到1之间的随机数temp₁，若temp₁<pm，随机选择种群中的一个个体， 随机对该个体的箱子顺序、移动模式、旋转模式进行变异，并重新计算该个体的适应度值；

(7)对种群中的个体按适应度值从大到小进行排序，将当前代中适应度值最大的个体 存放在结构体数组best[N]中；

(8)对gen自加1，返回步骤(4)；

(9)对结构体数组best[N]按个体适应度值从大到小进行排序，应用爬山法对结构体 best[0]进行优化，将优化后得到的适应度值最大的个体存入Best中，输出爬山法优化后适 应度最大的个体Best，即为优化后装箱结果，其中包括箱子序号num，箱子的宽w、高h、 长l，箱子放置的坐标点x、y、z，箱子的旋转模式r，移动模式m，适应度即体积利用率。

本发明与现有的技术相比较具有以下优点:

1.本发明由于采用三维移动模式序列的解码方式，不仅为密母算法的设计提供了平 台，而且减小了空间内存的存储量。

2.本发明由于采用密母算法的优化方式，加快了收敛速度，提高了装箱的稳定性。

3.本发明由于采用了密母算法，即遗传算法和爬山法相结合，利用全局搜索和局搜 索，可以得到更大的体积利用率。

附图说明

图1是本发明的实现总流程图；

图2是本发明每个箱子的上覆盖，右覆盖和前覆盖示意图；

图3是本发明中每个箱子的初始位置的三种移动模式示意图；

图4是本发明中基于三维移动模式序列的解码子流程图；

图5是本发明中用爬山法对个体局部搜索的子流程图；

图6是用本发明对20个箱子不同旋转时仿真的最优放置结果示意图；

图7是用本发明对60个箱子不同旋转时仿真的最优放置结果示意图。

具体实施方式

本发明的三维装箱问题，是指在满足可行放置方案的条件下将尽可能多的箱子装到固 定容器中，使得容器的体积利用率最大，并对数据进行测试。

本发明的一个重要特点是，是将二维移动模式序列扩展到三维，并运用箱子投影到平 面的方法对箱子的属性值进行记录，其设计模型是:

设Edgxz表示箱子投影到xoz平面，Edgxy表示箱子投影到xoy平面，Edgyz表示箱 子投影到yoz平面。

Edgxz的信息包括：

xl：箱子投影到xoz平面时，边界最小的x坐标值；

xr：箱子投影到xoz平面时，边界最大的x坐标值；

yt：未投影时坐标点的y坐标值；

zl：箱子投影到xoz平面时，边界最小的z坐标值；

zr：箱子投影到xoz平面时，边界最大的z坐标值。

Edgxy的信息包括：

xl：箱子投影到xoy平面时，边界最小的x坐标值；

xr：箱子投影到xoy平面时，边界最大的x坐标值；

yl：箱子投影到xoy平面时，边界最小的y坐标值；

yr：箱子投影到xoy平面时，边界最大的y坐标值；

zt：未投影时坐标点的z坐标值。

Edgyz的信息包括：

xt：未投影时坐标点的x坐标值；

yl：箱子投影到yoz平面时，边界最小的y坐标值；

yr：箱子投影到yoz平面时，边界最大的y坐标值；

zl：箱子投影到yoz平面时，边界最小的z坐标值；

zr：箱子投影到yoz平面时，边界最大的z坐标值。

用BTT表示已放置的箱子投影到xoz平面，它包括的信息与Edgxz包括的信息相同；用 BTF表示已放置的箱子投影到xoy平面，它包括的信息与Edgxy包括的信息相同；用BTF 表示已放置的箱子投影到yoz平面，它包括的信息与Edgyz包括的信息相同。

参照图1，本发明具体实施步骤如下:

步骤1.参数设定。

设N为遗传算法中种群中的个体数，N为大于或等于2的整数，M为每个个体中箱子 个数，M为大于或等于1的整数；用W、H、L分别表示装箱容器的宽、高、长；Mgen 表示进化的最大代数，pc0为箱子顺序交叉概率，pc1为移动模式交叉概率，pc2为旋转模 式交叉概率，其中pc0、pc1、pc2为0到1之间的实数；pm为变异概率，取值为0到1 之间的实数；w₁、h、l分别为箱子的宽、高、长，x、y、z为箱子放置坐标点的值，m 为移动模式值，取值为0、1、2；r为旋转模式值，取值为0～5之间的整数；num为箱子的 序号；TEM为爬山法的迭代次数；RX、RY、RZ分别表示最小立方体包络的宽、高、长； gen为进化代数；结构体数组best[N]用于保存每一代中适应度最大的个体，结构体Best用 于保存爬山法得到的适应度最大的个体。

步骤2.随机产生初始种群，即随机产生箱子序号0～M-1的排列，随机产生旋转模式 0～5的排列，随机产生移动模式0～2的排列，产生N个这样的个体组成初始种群；计算每 个个体的适应度值，设gen＝0；

2.1)给出了箱子的上覆盖、右覆盖以及前覆盖的概念。

参照图2，本发明给出了箱子的上覆盖、右覆盖以及前覆盖的概念，其中：

2.11)上覆盖的定义：将箱子a投影到xoz平面上的信息Edgxz与已放置的箱子b投 影到xoz平面上的信息BTT相比较，若不满足下式：

(Edgxz.yt＜BTT.yt)or(Edgxz.xr＜＝BTT.xl)or(Edgxz.xl＞＝BTT.xr)or

(Edgxz.zr＜＝BTT.zl)or(Edgxz.zl＞＝BTT.zr)。

则说明箱子a上覆盖有已放置的箱子b，即为箱子的上覆盖，参照图2a；

2.12)右覆盖的定义：将箱子a投影到xoy平面上的信息Edgxy与已放置的箱子b投 影到xoy平面上的信息LTR相比较，若不满足下式:

(Edgxy.zt＜LTR.zt)or(Edgxy.xr＜＝LTR.xl)or(Edgxy.xl＞＝LTR.xr)or

(Edgxy.yr＜＝LTR.yl)or(Edgxy.yl＞＝LTR.yr)。

则说明箱子a右覆盖有已放置的箱子b，即为箱子的右覆盖，参照图2b；

2.13)前覆盖的定义：将箱子a投影到yoz平面上的信息Edgyz与已放置的箱子b投 影到yoz平面上的信息BTF相比较，若不满足下式：

(Edgyz.xt＜BTF.xt)or(Edgyz.yr＜＝BTF.yl)or(Edgyz.yl＞＝BTF.yr)or

(Edgyz.zr＜＝BTF.zl)or(Edgyz.zl＞＝BTF.zr)。

则说明箱子a前覆盖有已放置的箱子b，即为箱子的前覆盖，参照图2c。

2.2)定义三维移动模式

参照图3，本发明将三维移动模式定义为如下3种：

第一种移动模式为0，第二种移动模式为1，第三种移动模式为2，每种移动模式有两 种移动状态，其中：

第一种移动模式0的两种移动状态：一是将箱子先向下移动找出上覆盖，再向后移动 找出前覆盖，最后向左移动找出右覆盖；二是将箱子先向下移动找出上覆盖，再向左移动 找出右覆盖，最后向后移动找出前覆盖；

第二种移动模式1的两种移动状态：一是将箱子先向左移动找出右覆盖，再向后移动 找出前覆盖，最后向下移动找出上覆盖；二是将箱子先向左移动找出右覆盖，再向下移动 找出上覆盖，最后向后移动找出前覆盖；

第三种移动模式2的两种移动状态：一是将箱子先向后移动找出前覆盖，再向左移动 找出右覆盖，最后向下移动找出上覆盖；二是将箱子先向后移动找出前覆盖，再向下移动 找出上覆盖，最后向左移动找出右覆盖；

2.3)对每个个体进行基于三维移动模式序列的解码：

参照图4所示，本步骤的具体实现如下:

(2.3a)初始化M个箱子的长、宽、高，随机产生移动模式m的值；设箱子初始坐标 为(-1，-1，-1)；i为计数变量，temp₂为一个随机产生的数，取值为0或1；

(2.3b)设i＝0，将第0个箱子的坐标点设置为(0，0，0)，初始化最小立方体包络的宽 RX、高RY、长RZ，i＝1；

(2.3c)判断是否满足终止条件i<M，若是，则执行步骤(2.3d)，否则，执行步骤(2.3r)；

(2.3d)根据m的取值，确定后续操作：若m＝0，当temp2＝0时，执行步骤(2.3e)，当 temp2＝1时，执行步骤(2.3g)；若m＝1，当temp2＝0时，执行步骤(2.3i)，当temp2＝1时， 执行步骤(2.3k)；若m＝2，当temp2＝0时，执行步骤(2.3m)，当temp2＝1时，执行步骤(2.3o)；

(2.3e)将箱子分别向下移动找出上覆盖，向后移动找出前覆盖，向左移动找出右覆盖；

(2.3f)判断箱子能否再次移动，若能，则返回步骤(2.3e)，否则执行步骤(2.3q)；

(2.3g)将箱子分别向下移动找出上覆盖，向左移动找出右覆盖，向后移动找出前覆盖；

(2.3h)判断箱子能否再次移动，若能，则返回步骤(2.3g)，否则执行步骤(2.3q)；

(2.3i)将箱子分别向左移动找出右覆盖，向后移动找出前覆盖，向下移动找出上覆盖；

(2.3j)判断箱子能否再次移动，若能，则返回步骤(2.3i)，否则执行步骤(2.3q)；

(2.3k)将箱子分别向左移动找出右覆盖，向下移动找出上覆盖，向后移动找出前覆盖；

(2.3l)判断箱子能否再次移动，若能，则返回步骤(2.3k)，否则执行步骤(2.3q)；

(2.3m)将箱子分别向后移动找出前覆盖，向左移动找出右覆盖，向下移动找出上覆盖；

(2.3n)判断箱子能否再次移动，若能，则返回步骤(2.3m)，否则执行步骤(2.3q)；

(2.3o)将箱子分别向后移动找出前覆盖，向下移动找出上覆盖，向左移动找出右覆盖；

(2.3p)判断箱子能否再次移动，若能，则返回步骤(2.3o)，否则执行步骤(2.3q)；

(2.3q)判断箱子是否完全处于容器中，若是，对i自加1，执行步骤(2.3c)，否则，更 新最小立方体包络宽RX、高RY、长RZ，对i自加1，返回步骤(2.3c)；

(2.3r)结束装箱解码过程；

2.4)适应度值计算

三维移动模式序列编码的目的是为了计算每个个体的适应度值，这里按如下公式计 算：

$\eta =\frac{\underset{k=0}{\overset{n}{\Sigma }}{v}_k}{V}\times 100\%$

其中，η为体积利用率，即适应度值；k为计数变量；n为放入容器中的箱子个数；v_k为第k个箱子的体积，其值为v＝w₁*h*l，其中w₁，h，l分别为第k个箱子的宽、高、长； V为容器体积，其值为：V＝W*H*L，其中W，H，L为容器的宽、高、长。

步骤3.判断是否满足gen<Mgen，若是，执行步骤4，否则，执行步骤9。

步骤4.选择个体。

根据种群中每个个体的适应度值，用二元锦标赛法从中选择N个适应度值大的个体， 即从种群中随机选择两个个体，对比两个个体的适应度大小，保留适应度较大的个体。

步骤5.对个体进行交叉操。

随机产生0到1之间的随机数temp；随机选择两个个体，若temp<pc0，则对这两个个 体的箱子顺序进行交叉；若temp<pc1则对这两个个体的移动模式进行交叉；若temp<pc2， 则对这两个个体的旋转模式进行交叉，并重新计算这两个个体的适应度值。

所述交叉是：设交叉点Point，其中Point为大于0且小于M-1的一个随机整数，将两个 个体模式排列中0到Point之间的模式值进行交换，Point到M-1的模式值保持不变，该模 式是指箱子的顺序、移动模式、旋转模式。

步骤6.对个体进行变异

随机产生0到1之间的随机数temp1，若temp1<pm，随机选择种群中的一个个体，随机 对该个体的箱子顺序、移动模式、旋转模式进行变异，并重新计算该个体的适应度值。

所述变异是：随机选取个体模式排列中的两个模式值进行交换，该模式是指箱子的顺 序、移动模式、旋转模式。

步骤7.对种群中的个体按适应度值从大到小进行排序，将当前代中适应度值最大的个 体存放在结构体数组best[N]中。

步骤8.对gen自加1，返回步骤4。

步骤9.对结构体数组best[N]按个体适应度值从大到小进行排序，应用爬山法对结构体 best[0]进行优化。

结构体数组best[N]中共有N个个体，按个体适应度值从大到小排序之后，结构体数组 best[N]中第一个个体best[0]即为个体适应度值最大的一个个体，爬山法即对该适应度值最 大的个体best[0]进行优化。

参照图5，用爬山法对个体best[0]进行优化的步骤如下:

(9a)设TEM为最大迭代次数，设计数变量count＝0，设t₁为一个随机数，取值为0， 1，2中的任一个；

(9b)判断是否满足count<TEM：若是，则执行步骤(9c)；否则，执行步骤(9f)；

(9c)判断t₁的取值：若t₁＝0，则对箱子的顺序进行变异；若t₁＝1，则对箱子的旋转模 式进行变异；若t₁＝2，则对箱子的移动模式进行变异，即随机选取排列中的两个模式值进 行交换，该模式是指箱子的顺序、移动模式、旋转模式；

(9d)重新计算变异后新个体的适应度值，并与未变异之前个体best[0]的适应度值进行 比较，若新得到个体的适应度值大于变异之前个体的适应度值，则用新得到的个体替换原 来的个体best[0]；否则维持原来的个体best[0]不变；

(9e)对count自加1，返回步骤(9b)；

(9f)输出更新后的适应度值最大的结果best[0]，即为优化后装箱结果，其中包括箱子 序号，箱子的宽、高、长，箱子放置的坐标点，箱子的旋转模式，移动模式以及体积利用 率。

步骤10.将爬山法优化best[0]后得到的适应度值最大的个体存入Best中，输出爬山法 优化后适应度最大的个体Best，其中包括箱子序号num，箱子的宽w、高h、长l，箱子放 置的坐标点x、y、z，箱子的旋转模式r，移动模式m，适应度即体积利用率。

本发明可以通过后续的仿真实验来进行验证

1.实验运行环境和条件设置：

实验运行环境：处理器为Intel(R)Core(TM)2CPU 6300@1.86GHZ,1.97GB的内存，硬 盘为250G,操作系统为Microsoft Windows XP Professional 2002,编程环境为Microsoft Visual  C++6.0。

实验条件设置：实验中数据是已有文献中随机产生数据的方法，产生20,60个箱子， 容器的W宽、H高、L长分别为10、10、10，以及233、235、1200。实验中进化代数Mgen 为200代，种群中个体数N为100，交叉概率pc0＝0.9，pc1＝0.8，pc2＝0.9，变异概率为pm＝0.45。

考虑到算法的随机性，求解问题中每个实例时，程序重复运行了10次。

2.实验内容和结果分析：

仿真实验1，用本发明对不同旋转状态下的20个箱子进行放置仿真，结果如图6， 其中图6a表示20个箱子在6种旋转状态时仿真的最优放置结果；图6b表示20个箱子在 2种旋转状态时仿真的最优放置结果，图6c表示20个箱子在没有旋转状态时仿真的最优 放置结果：

从图6a，6b，6c可以看出，20个箱子在6种旋转状态时，可以达到100％的体积利用 率，20个箱子在2种旋转状态以及没有旋转状态时，容器会产生剩余空间。

仿真实验2，用本发明对不同旋转状态下的60个箱子进行放置仿真，结果如图7， 其中图7a表示60个箱子在6种旋转状态时仿真的最优放置结果，图7b表示60个箱子在 2种旋转状态时仿真的最优放置结果，图7c表示60个箱子在没有旋转状态时仿真的最优 放置结果：

从图7a，7b，7c可以看出，60个箱子在不同的旋转状态时，容器产生的剩余空间小， 容器的体积利用率大。

仿真实验3，将本发明与现有技术中HGA，HGAI，DBLF进行20种箱子和60种箱子 在不同旋转状态时的体积利用率对比表，对比结果如表1所示。

表1与其他算法性能比较

------说明文献中未给出结果

从表1可以看出，本发明的体积利用率在20个箱子时优于现有算法，在60个箱子不 旋转的情况下，体积利用率高于现有算法，可见本发明可以取得高的体积利用率。

综上，用本发明对箱子进行放置，可以得到高的容器体积利用率，进一步验证了本发 明的有效性。