基于三步动态规划的三维装箱方案生成方法

摘要

本发明提供一种基于三步动态规划的三维装箱方案生成方法，将三维装箱问题分解为按先后顺序执行的三个01背包问题，将三维装箱方案的生成过程转换为三个01背包问题的求解。本发明的方案，相对于现有方法，提高了装箱率和装箱方案生成速度；采用本发明的方法，进一步提高了集装箱空间利用率，降低集装箱货运成本，增加了企业利润。

说明书

技术领域

本发明涉及三维装箱方法领域技术领域，具体地说，涉及基于三步动态规划的三维装箱 方案生成方法。

背景技术

三维装箱问题是在集装箱货物装运、封闭式货车货物装运领域经常遇到的问题，研究三 维装箱问题可以帮助企业客户提高集装箱容积利用率，降低货运成本、提高货运利润。

三维装箱问题属于典型的NP-Hard问题，求解难度大。目前求解三维装箱问题主要基于砌 墙策略、建堆策略、空间分割策略和拟人策略等。

上述方案中，主要采用启发式算法在有限空间内穷举装箱方案，装箱率不高，且在计算 机上的运算时间较长。

发明内容

为了解决目前三维装箱技术领域存在的问题，本发明提供基于三步动态规划的三维装箱 方案生成方法，其具体的技术方案如下：

基于三步动态规划的三维装箱方案生成方法，将三维装箱问题分解为按先后顺序执行的 三个01背包问题，将三维装箱方案的生成过程转换为三个01背包问题的求解，具体按以下 步骤进行：

步骤一、读取长方体形状容器的长宽高尺寸，读取所有待装入容器的长方体箱子的长宽 高尺寸以及放置方向约束，放置方向约束包括：是否允许长度向上放置、是否允许宽度向上 放置、是否允许高度向上放置；

步骤二、以长方形容器的高为背包容量，以待装入容器的箱子集合为待装入背包的货物 集合，以每个箱子在容器高度方向的可能尺寸为每个货物的重量，以被选中的箱子体积和为 背包货物总价值，求解该01背包问题，将所有待装入容器的箱子组合成多个优条，得到优条 集合；

步骤三、以长方形容器的宽度为背包容量，以步骤二中生成的所有优条为待装入背包的 货物集合，以每个优条在容器宽度方向的可能尺寸为每个货物的重量，以被选中的优条体积 之和为背包货物总价值，求解该01背包问题，将优条集合中所有优条组合成多个优层，得到 优层集合；

步骤四、以长方形容器的长度为背包容量，以步骤三中生成的所有优层为待装入背包的 货物集合，以每个优层在容器长度方向的尺寸为每个货物的重量，以被选中的优层体积之和 为背包货物总价值，求解该01背包问题，根据优层集合中所有优层，生成一个优箱，从而得 到一个三维装箱方案；

步骤五、给出三维装箱方案的3D图显示，装箱方案生成结束。

其中，步骤二中，每一个箱子在容器长度方向和宽度方向的尺寸必须小于给定值；利用 动态规划方法求解一次01背包问题得到一个箱子集合，称该箱子集合为优条；

每生成一个优条，就从待装入容器的箱子集合中去除该优条中包含的所有箱子；然后再 通过求解01背包问题生成新的优条，再从待装入容器的箱子集合中去除新的优条中包含的所 有箱子，循环求解01背包问题，直至所有待装入容器的箱子都形成优条为止；

每个优条中所有箱子沿容器高度方向放置，优条的宽度等于优条中所有箱子在容器宽度 方向尺寸的最大值，优条的长度等于优条中所有箱子在容器长度方向尺寸的最大值，优条的 高度等于优条中所有箱子在容器高度方向尺寸的和，优条的体积等于该优条中所有箱子体积 的和。

进一步，步骤三中，

每一个优条在容器长度方向尺寸，利用动态规划方法求解一次01背包问题得到一个优条 集合，称该优条集合为优层；

每生成一个优层，就从步骤二中生成的所有优条中去除该优层中包含的所有优条；然后 再通过求解01背包问题生成新的优层，再从步骤二生成的所有优条中去除新的优层中包含的 所有优条，循环求解01背包问题，直至步骤二生成的所有优条都形成优层为止；

每个优层中所有优条沿容器宽度方向放置，优层的宽度等于优层中所有优条在容器宽度 方向尺寸的和，优层的长度等于优层中所有优条在容器长度方向尺寸的最大值，优层的体积 等于该优层中所有优条体积的和。

更进一步，步骤四中，

利用动态规划方法求解一次01背包问题得到一个优层集合，称该优层集合为优箱；优箱 中的所有优层沿容器长度方向放置；一个优箱即是一个三维装箱方案。

本发明所提供的基于三步动态规划的三维装箱方案生成方法，具有以下优点：

第一：相对于现有方法，提高了装箱率和装箱方案生成速度；

第二：采用本发明的方法，进一步提高了集装箱空间利用率，降低集装箱货运成本，增 加了企业利润。

附图说明

图1为基于三步动态规划的三维装箱方案生成系统架构示意图；

图2为基于三步动态规划的三维装箱方案生成流程；

图3为本发明实施例验证试验输出的三维装箱方案的3D图。

具体实施方式

下面结合附图及本发明的实施例对本发明的基于三步动态规划的三维装箱方案生成方法 作进一步详细的说明。

基于三步动态规划的三维装箱方案生成方法，将三维装箱问题分解为按先后顺序执行的 三个01背包问题，将三维装箱方案的生成过程转换为三个01背包问题的求解，具体按以下 步骤进行：

步骤一、读取长方体形状容器的长宽高尺寸，读取所有待装入容器的长方体箱子的长宽 高尺寸以及放置方向约束，放置方向约束包括：是否允许长度向上放置、是否允许宽度向上 放置、是否允许高度向上放置；

步骤二、以长方形容器的高为背包容量，以待装入容器的箱子集合为待装入背包的货物 集合，以每个箱子在容器高度方向的可能尺寸为每个货物的重量，以被选中的箱子体积和为 背包货物总价值，求解该01背包问题，将所有待装入容器的箱子组合成多个优条，得到优条 集合；

每一个箱子在容器长度方向和宽度方向的尺寸必须小于给定值；利用动态规划方法求解 一次01背包问题得到一个箱子集合，称该箱子集合为优条；

每生成一个优条，就从待装入容器的箱子集合中去除该优条中包含的所有箱子；然后再 通过求解01背包问题生成新的优条，再从待装入容器的箱子集合中去除新的优条中包含的所 有箱子，循环求解01背包问题，直至所有待装入容器的箱子都形成优条为止；

每个优条中所有箱子沿容器高度方向放置，优条的宽度等于优条中所有箱子在容器宽度 方向尺寸的最大值，优条的长度等于优条中所有箱子在容器长度方向尺寸的最大值，优条的 高度等于优条中所有箱子在容器高度方向尺寸的和，优条的体积等于该优条中所有箱子体积 的和。

步骤三、以长方形容器的宽度为背包容量，以步骤二中生成的所有优条为待装入背包的 货物集合，以每个优条在容器宽度方向的可能尺寸为每个货物的重量，以被选中的优条体积 之和为背包货物总价值，求解该01背包问题，将优条集合中所有优条组合成多个优层，得到 优层集合；

每一个优条在容器长度方向尺寸，利用动态规划方法求解一次01背包问题得到一个优条 集合，称该优条集合为优层；

每生成一个优层，就从步骤二中生成的所有优条中去除该优层中包含的所有优条；然后 再通过求解01背包问题生成新的优层，再从步骤二生成的所有优条中去除新的优层中包含的 所有优条，循环求解01背包问题，直至步骤二生成的所有优条都形成优层为止；

每个优层中所有优条沿容器宽度方向放置，优层的宽度等于优层中所有优条在容器宽度 方向尺寸的和，优层的长度等于优层中所有优条在容器长度方向尺寸的最大值，优层的体积 等于该优层中所有优条体积的和。

步骤四、以长方形容器的长度为背包容量，以步骤三中生成的所有优层为待装入背包的 货物集合，以每个优层在容器长度方向的尺寸为每个货物的重量，以被选中的优层体积之和 为背包货物总价值，求解该01背包问题，根据优层集合中所有优层，生成一个优箱，从而得 到一个三维装箱方案；

利用动态规划方法求解一次01背包问题得到一个优层集合，称该优层集合为优箱；优箱 中的所有优层沿容器长度方向放置；一个优箱即是一个三维装箱方案。

步骤五、给出三维装箱方案的3D图显示，装箱方案生成结束。

如图1所示，基于三步动态规划的三维装箱方案生成系统分为三大部分：①容器和箱子 信息录入模块1，实现容器长宽高信息录入功能、箱子长宽高信息录入功能和放置方向约束 信息录入功能；②三维装箱方案生成模块2，实现基于三步动态规划的三维装箱方案自动生 成功能；③三维装箱方案3D展示模块3，以3D方式显示三维装箱方案。

结合图1，基于三步动态规划的三维装箱方案生成系统各模块实现细节及模块间关系如 下：

容器和箱子信息录入模块1为用户提供容器长宽高信息的录入接口，提供箱子长宽高信 息和摆放方向约束信息的录入接口。

三维装箱方案生成模块2从容器和箱子信息录入模块1获取容器和箱子的长宽高信息和 摆放位置约束信息，生成三维装箱方案。

三维装箱方案3D展示模块3从三维装箱方案生成模块2获取三维装箱方案，利用3D技 术显示装箱方案。

实施例1：

为了验证本发明的方法的可靠性，将本发明的方法通过计算机软件模拟实现，如图1所 示，该软件包括容器和箱子信息录入模块、三维装箱方案生成模块、三维装箱方案3D展示模 块。其具体运行过程如图2所示：

步骤1、读取长方体形状容器的长宽高尺寸，读取所有待装入容器的长方体箱子的长宽 高尺寸以及放置方向约束，放置方向约束包括是否允许长度向上放置、是否允许宽度向上放 置、是否允许高度向上放置；

步骤2、将所有待装入容器的箱子组合成多个优条，得到优条集合；

步骤3、将优条集合中所有优条组合成多个优层，得到优层集合；

步骤4、根据优层集合中所有优层生成一个优箱，从而得到一个三维装箱方案；

步骤5、给出三维装箱方案的3D图显示，装箱方案生成结束。

为了验证基于三步动态规划的三维装箱方案生成方法和系统的可行性，采用了以下案例 信息。

容器信息：

长度 宽度 高度 600 240 225

箱子信息：

本发明所述的方法在计算机系统上的运行结果如图3所示，经与按人工经验装箱比对，装 箱价值提高了10％，为用户节省了成本，提高了装箱效率。

以上实施例仅为本发明的选取的其中一个实施方式，凡依本发明申请专利范围所作的均 等变化与修饰，皆应属本发明专利的涵盖范围。