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

摘要

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

主权项

基于三步动态规划的三维装箱方案生成方法，其特征在于：将三维装箱问题分解为按先后顺序执行的三个01背包问题，将三维装箱方案的生成过程转换为三个01背包问题的求解，具体按以下步骤进行：步骤一、读取长方体形状容器的长宽高尺寸，读取所有待装入容器的长方体箱子的长宽高尺寸以及放置方向约束，放置方向约束包括：是否允许长度向上放置、是否允许宽度向上放置、是否允许高度向上放置；步骤二、以长方形容器的高为背包容量，以待装入容器的箱子集合为待装入背包的货物集合，以每个箱子在容器高度方向的可能尺寸为每个货物的重量，以被选中的箱子体积和为背包货物总价值，求解该01背包问题，将所有待装入容器的箱子组合成多个优条，得到优条集合；步骤三、以长方形容器的宽度为背包容量，以步骤二中生成的所有优条为待装入背包的货物集合，以每个优条在容器宽度方向的可能尺寸为每个货物的重量，以被选中的优条体积之和为背包货物总价值，求解该01背包问题，将优条集合中所有优条组合成多个优层，得到优层集合；步骤四、以长方形容器的长度为背包容量，以步骤三中生成的所有优层为待装入背包的货物集合，以每个优层在容器长度方向的尺寸为每个货物的重量，以被选中的优层体积之和为背包货物总价值，求解该01背包问题，根据优层集合中所有优层，生成一个优箱，从而得到一个三维装箱方案；步骤五、给出三维装箱方案的3D图显示，装箱方案生成结束。