王飞跃的个人博客分享 http://blog.sciencenet.cn/u/王飞跃

博文

求解三维装箱问题的多层树搜索算法

已有 4900 次阅读 2021-3-10 08:02 |个人分类:论文交流|系统分类:论文交流

引用本文: 刘胜, 沈大勇, 商秀芹, 赵红霞, 董西松, 王飞跃, “求解三维装箱问题的多层树搜索算法”, 自动化学报, 2020, Vol. 46, No. 6, pp.1178−1187. doi: 10.16383/j.aas.c180795  

Citation:Liu Sheng, Shen Da-Yong, Shang Xiu-Qin, Zhao Hong-Xia, Dong Xi-Song, Wang Fei-Yue, A multi-level tree search algorithm for three dimensional container loading problem. Acta Automatica Sinica, 2020, Vol. 46, No. 6, pp.1178−1187.  doi: 10.16383/j.aas.c180795  


求解三维装箱问题的多层树搜索算法


刘胜, 沈大勇, 商秀芹, 赵红霞, 董西松, 王飞跃


摘要: 提出了一种求解三维装箱问题的多层树搜索算法, 该算法采用箱子–片–条–层–实体的顺序生成装载方案, 装载方案由实体表示. 该算法由3层搜索树构成. 第1层为三叉树, 每个树节点的3个分叉分别对应向实体中填入XY面平行层、XZ面平行层、YZ面平行层; 第2层为二叉树, 每个树节点的两个分叉分别对应向层内装载两个相互垂直的最优条; 第3层为四叉树, 用于将同种的多个箱子生成片. 在同时满足摆放方向约束和完全支撑约束的前提下, 该算法求解BR12~BR15得到的填充率高于现有装箱算法.


关键词: 三维装箱, 墙构造, 水平层构造, 多层树 


A Multi-level Tree Search Algorithm for Three Dimensional Container Loading Problem


LIU Sheng, SHEN Da-Yong, SHANG Xiu-Qin, ZHAO Hong-Xia, DONG Xi-Song, WANG Fei-Yue


Abstract: This paper presents a multiple-level tree search algorithm for the three dimensional container loading problem. This algorithm generates a loading plan in the box-piece-strip-layer-entity sequence. Hereby an entity denotes a loading plan. This algorithm consists of three levels of search tree. The first level is a ternary tree. In this tree the three branches of each node correspond to filling three layers which are parallel to the XY-plane, the XZ-plane, and the YZ-plane, respectively. The second level is a binary tree. In this tree the two branches of each node correspond to loading two orthogonal strips into a layer, respectively. The third level is a quad tree to search the best piece. In this tree the boxes of the same kind are integrated into a piece. The proposed algorithm achieves better filling rate for BR12~BR15 than the existing algorithms when the orientation constraint and the full-support constraint are satisfied.


Key words: Three-dimensional container loading, wall building, horizontal layer building, multi-level tree search 


三维装箱问题(Three-dimensional container loading problem, 3D-CLP)研究如何通过优化货物摆放来提高货箱空间利用率, 应用三维装箱算法不仅可以降低货物运输成本, 还可以减少运输工具在运输过程中的碳排放, 具有很好的社会经济效益.


三维装箱问题属于切割与布局问题(Cutting and packing, CP)[1], 相关研究可以追溯到20世纪80年代[2]. 按照文献[3]的分类命名法, 三维装箱问题可以归为代号为3/V/I或3/B/O的CP问题. 按照文献[4]建议的分类命名法, 三维装箱问题归为三维单一背包问题(Three-dimensional single knapsack problem, 3D-SKP)或三维单一大物体摆放问题(Three-dimensional single large object placement problem, 3DSLOPP). 依据文献[5]中定义, 本文研究的是考虑摆放方向约束(C1)和完全支撑约束(C2)的三维装箱问题. 在目前研究三维装箱问题的文献中, 这也是考虑最广泛的两个约束.


本文结构如下: 第1节简要回顾三维装箱问题的研究进展; 第2节详细叙述本文提出的三维装箱算法的实现步骤; 第3节给出本文算法运行通用算例的结果, 并将结果与目前最新算法的运行结果相比较. 最后第4节总结了本文算法的特点, 并展望了下一步的研究思路.


1.   研究综述


3D-CLP是典型的NP难题[6-7], 不存在多项式时间复杂度的最优求解算法. 用传统的精确算法求解这类问题, 会发生“组合爆炸”的现象, 只适合解决箱子种类数量较小的装箱问题, Fekete等[8]给出了一种求解该问题的精确方法. 对于实际应用中规模比较大的装箱问题, 精确方法难以在可接受时间内求得最优解, 启发式方法依然是首选. 近年来有大量文献报道求解3D-CLP的启发式算法. 按照方法类型来分, 这些算法可以分为以下3种:


1)经典启发式方法. 此类方法分为两大类, 一类是构造法, 即从一个空的方案逐步生成一个完全的装载方案, 文献[9-13]提出的方法可以归为此类方法, 文献[14]利用多面构建的方法, 显著提升了填充率, 文献[15]将拟人法与模拟退火算法相结合, 取得了很好的效果; 另一类是提升法, 即首先生成一个完全的装载方案, 然后不断地优化提升该方案.


2)元启发式方法. 元启发式方法包括遗传算法、禁忌搜索、模拟退火、贪婪随机自适应等方法, 近年来在求解3D-CLP中得到广泛应用. 文献[15-17]利用遗传算法求解3D-CLP. 文献[18-19]分别给出了一种求解3D-CLP的禁忌搜索方法. 文献[15, 18, 20-21]将模拟退火算法应用于求解3D-CLP, 文献[22]给出了基于Nelder-Mead方法的局部搜索方法, 用以提升3D-CLP的解的质量. 文献[23-24]给出求解3D-CLP的贪婪随机自适应搜索方法(Greedy randomized adaptive search procedure, GRASP).


3)树搜索法. 树搜索或图搜索方法用于求解三维装箱问题, 形成了一批高效的求解算法. 文献[25]提出了求解3D-CLP的与或图算法. 文献[26]将分支定界法集成到求解3D-CLP的算法中. 文献[7, 27-34]都是基于树搜索的算法.


按照装载方案的构造方式来分, 这些启发式算法可以分为以下6种:


1)墙构造法(Wall building approach). 其特征是装载方案由一块块竖直的“物品墙”组成, “墙”依次放入容器中, 其上下左右和后方五个方向需紧贴容器剩余空间的边以提高填充率, 所有“墙”的4个竖直面至少有一个和容器竖直面重合. 代表性方法有文献[17, 29, 32-33].


2)建堆法(Stack building approach). 其特征是先将物品组合成若干个与容器等高的长方体“堆”, 再将这些“堆”放置到容器中. 与墙构造法不同的是, 堆的4个竖直面不必和容器的竖直面重合, 但是堆的上下水平面必须和容器的上下水平面重合. 文献[9]和文献[16]正是基于这种方法.


3)水平层构造法(Horizontal layer building approach). 其特征是装载方案由若干块水平的长方体物品层组成, 层的4个竖直面和容器的竖直面重合. 代表性方法有文献[10]和文献[26].


4)块构造法(Block building approach). 其特征是装载方案由若干个长方体“块”构成, 每个“块”由尺寸相同(或相近)且摆放方向相同的物品组成. 大多数算法采用这种构造方式. 如文献[7, 19-20, 27, 31, 34]中所述方法.


5)完全切割法(Guillotine cutting approach). 该方法利用完全切割树将容器分为若干个小的长方体空间, 切割树的叶子结点代表物品. 文献[25]正是基于这种方法.


6)基于穴度的全局构造法(Caving-degree- based global building approach). 该方法从全局考虑, 依次为每个物品在容器中寻找最佳放置位置, 再评价所有待放置物品放入后的效果, 选择效果最佳的物品放置到最佳位置, 从而获得高效装载方案. 文献[11-13]对该方法进行了深入的研究, 取得了一系列成果.


大多数的算法满足摆放方向约束和支撑约束, 除此以外, 还有一些文献提出了满足其他约束的算法. 文献[34-35]提出了带有运输优先级约束的算法. 文献[30]和文献[36]分别提出带有动态优先级和轴重约束的算法. 文献[37]算法同时满足运输优先级和完全运输约束. 此外还有大量文献对与3D-CLP相关的组合优化问题进行了研究. 文献[38]针对带容量约束的绿色车辆路径规划问题, 给出了带有竞争的文化基因算法. 文献[39]针对服装展切问题提出了一种反复贪婪算法. 文献[40]提出了电动汽车的混合调度策略, 文献[41]提出了一种高效的3D打印优化算法.


本文提出的多层树搜索算法是墙构造法和水平层法相结合的树搜索算法, 与文献[32-33]只有1层搜索树不同的是, 本文算法包括3层搜索树, 文献[32-33]算法只用到竖直层(即“墙”), 而本文算法同时包括竖直层和水平层. 本文将所提出算法称为多层树搜索算法(Multi-level tree search, MLTrS).


2.   多层树搜索算法


2.1   名词解释


3D-CLP问题的形式化定义如下: 给定一个长、宽、高分别为$L$, $W$, $H$的长方体容器$C$和$n$个长方体箱子${b_1}$, ${b_2}$, $ \cdots $, ${b_n}$, 用集合$B$表示这些箱子, 箱子${b_i}\;\left( {i = 1,2, \cdots ,n} \right)$的长为 $l_i$、宽为 $w_i$、高为 $h_i$, 箱子${b_i}\;\left( {i = 1,2, \cdots ,n} \right)$的体积为${v_i} = {l_i}{w_i}{h_i}$. 用0-1标志$z{l_i}$、$z{w_i}$、$z{h_i}$表示箱子${b_i}\;\left( {i = 1,2, \cdots ,n} \right)$的长宽高是否允许向上摆放(0表示不允许, 1表示允许), 令


image.png


1.jpg

图 1  坐标系和容器、箱子尺寸和摆放方向示意图

Fig. 1  Examples of coordination, size, and orientations of container and box


设$F$为$B$的一个子集, 定义$F$中所有箱子体积之和为${V_F}$, 问题的目标是选择$B$的一个子集$F$使得${V_F}$最大, 并且满足以下条件: 对任何箱子${b_i} \in F$, 在容器$C$中对应一个装填位置; 所有$F$中的箱子必须全部包含在$C$中; $F$中任何两个箱子在$C$中不重叠; $F$中箱子${b_i}$的放置方向必须满足方向标志$u{l_i}$, $u{w_i}$, $u{h_i}$的要求. 定义子集$F$对应的容器$C$的填充率为${{F{R_F} = {V_F}} / {\left( {LWH} \right)}}$. 如果三维装箱问题带有完全支撑约束, 则容器中所有箱子的底部都必须与容器底部或其他箱子的顶部完全接触. 为了便于介绍算法, 进行如下定义:


定义1. 片$(piece)$. 从长方体箱子的集合$B$取出完全相同的多个箱子进行摆放, 要求在$x$轴、$y$轴、$z$ 轴三个方向中的一个方向上只摆放一层, 且所有箱子在该方向上摆放尺寸相同, 则这些箱子的摆放构成一个$piece$. 定义$piece$的三维坐标与尺寸为它的母长方体的三维坐标与尺寸(在生成$piece$之前, 首先给定三维尺寸边界, 生成的$piece$不能超过该边界, 则该三维尺寸边界构成的长方体就是$piece$的母长方体). 分别以 ${{XS}} \left( {piece} \right)$、${{YS}} \left( {piece} \right)$和 ${{ZS}} \left( {piece} \right)$表示$piece$的三维尺寸, 以${{VB}} \left( {piece} \right)$表示$piece$中所有箱子体积和, 定义 $piece$的填充率${{Fr}} \left( {piece} \right)$为${{VB}} \left( {piece} \right)$除以$piece$的生成长方体体积. 如果$piece$在$x$轴方向只摆放一层, 则称为$x\_piece$, 同理可得$y\_piece$和 $z\_piece,$ 图2为$x\_piece$, $y\_piece$和$z\_piece$的示意图.


2.jpg

图 2  片的示意图

Fig. 2  Examples of pieces


定义2. 条$(strip)$. 给定一组$x\_piece$ ($y\_piece$, $z\_piece$), 从中选择一个子集, 在满足箱子摆放方向约束的前提下, 沿$x$轴($y$轴, $z$轴)摞成一串, 形成条$strip$. 定义$strip$的三维坐标与尺寸为它的母长方体的三维坐标与尺寸(在生成$strip$之前, 首先给定三维尺寸边界, 生成的$strip$不能超过该边界, 则该三维尺寸边界构成的长方体就是$strip$的母长方体). 分别以${{XS}} \left( {strip} \right)$、${{YS}} \left( {strip} \right)$和${{ZS}} \left( {strip} \right)$表示$strip$的三维尺寸, 以${{VB}} \left( {strip} \right)$表示$strip$中所有箱子体积和, 定义 $strip$的填充率${{Fr}} \left( {strip} \right)$为构成${{VB}} \left( {strip} \right)$除以$strip$的最小包围长方体体积. 由$x\_piece$沿$x$轴摞成一串构成的$strip$称为$x\_strip$, 同理可得 $y\_strip$ 和$z\_strip$, 图3为$x\_strip$, $y\_strip$和$z\_strip$的示意图.


3.jpg

图 3  条的示意图

Fig. 3  Examples of strips


定义3. 层$(layer)$. 给定一组$x\_strip$与一组$y\_strip$, 从两组中选择一个子集, 在满足箱子摆放方向约束的前提下, 沿与$xy$面平行的面排列子集中的$strip$, 所有摆放的$strip$的$z$坐标相同, 形成层$layer$. 定义$layer$的三维坐标与尺寸为它的母长方体的三维坐标与尺寸(在生成$layer$之前, 首先给定三维尺寸边界, 生成的$layer$不能超过该边界, 则该三维尺寸边界构成的长方体就是$layer$的母长方体). 分别以${{XS}} \left( {layer} \right)$、${{YS}} \left( {layer} \right)$和${{ZS}} \left( {layer} \right)$表示$layer$的三维尺寸, 以${{VB}} \left( {layer} \right)$表示$layer$中所有箱子体积和, 定义 $layer$的填充率${{Fr}} \left( {layer} \right)$为 ${{VB}} \left( {layer} \right)$除以 $layer$的最小包围长方体体积. 由$x\_strip$和$y\_strip$沿与$xy$面平行的面排列形成的$layer$称为$xy\_layer$. 同理可得$yz\_layer$和$xz\_layer$, 图4为$xy\_layer$, $yz\_layer$和$xz\_layer$的示意图.


4.jpg

图 4  层的示意图

Fig. 4  Examples of layers


定义4. 装载实体$(entity)$. 给定容器$C$和箱子集合$B$, 从集合$B$中选取一个子集 $Q$, $Q$中的箱子全部装入容器$C$, $Q$中所有这些箱子的摆放位置和摆放方向整体构成一个装载实体$entity$, 一个$entity$即是一个装箱方案, 其母长方体就是容器$C$的最大内部空间长方体. 一个$entity$可以分解为一组$layer$, 每一个$layer$可以分解为一组$strip$, 每一个$strip$可以分解为一组$piece$, 每个$piece$则由若干个完全相同的箱子组成. 定义${{VB}} \left( {entity} \right)$为$entity$中所有箱子体积和, 定义$entity$的填充率 ${{Fr}} \left( {entity} \right)$为VB$ \left( {entity} \right)$除以容器 $C$的容积. 图5为 $entity$示意图.


5.jpg

图 5  装载实体示意图

Fig. 5  Example of entity


2.2   算法流程


MLTrS算法包含3层搜索树, 第1层树搜索${\rm{TrS \_Entity}}$是三叉树, 也是算法的主过程, 用于搜索最优$entity$; 第2层树搜索${\rm{TrS \_Layer}}$(包含${\rm{TrS \_XY\_} }$${\rm{Layer}}$、${\rm{TrS \_XZ\_Layer}}$和${\rm{TrS\_YZ\_Layer}} $)是二叉树, 用于搜索最优$layer$; 第3层树搜索${\rm{TrS \_Piece}}$(包含${\rm{TrS \_X\_Piece}}$、${\rm{TrS \_Y\_Piece}}$和${\rm{TrS\_Z\_Piece}} $)是四叉树, 用于搜索最优$piece$.


MLTrS算法主过程${\rm{TrS \_Entity}}$的伪代码如算法1所示. 参数$best\_entity$和$entity$分别表示最好的装载实体和当前的装载实体, 参数$xr$、$yr$和$zr$分别表示容器$C$剩余长方体空间的长宽高, 参数$B$是待装入的箱子集合. ${\rm{TrS \_Entity}}$包括4个部分(以大括号分隔), 第1部分创建6个空白的$layer$, 以备后用; 第2部分是在剩余长方体空间内填入一个最优的$xy\_layer$; 第3部分是在剩余长方体空间内填入一个最优的$xz\_layer$; 第4部分是在剩余长方体空间内填入一个最优的$yz\_layer$.


算法1. $\;{\bf{TrS\_Entity}}$伪代码

$ {\bf{TrS\_Entity}}\left( {best\_entity,entity,xr,yr,zr,B} \right)$

$ \left\{


创建空的xy_layer,best_xy_layer,xz_layer,best_xz_layer,yz_layer和best_yz_layer

 

\right.$


image.png

image.png


以$xy\_layer$为例, 它的x轴向尺寸和y轴向尺寸分别等于$xr$和$yr,$而z轴向尺寸可能等于某个箱子在z轴方向可能的尺寸, 这样$xy\_layer$的可能的z轴向尺寸数量就非常多, 为了加速算法, 我们取尺寸权值最大的5个尺寸. 尺寸权值计算法定义如下: 初值为0, 对于每一个箱子的每一个边长, 如果该边长等于该尺寸, 而且该边可与z轴平行放置, 则尺寸权值加上与该边垂直的箱子面的面积. $xz\_layer$和$yz\_layer$的可行尺寸选择方法可以参照$xy\_layer$.


${\rm{TrS \_XY\_Layer}}$, ${\rm{TrS \_XZ\_Layer}}$和${\rm{TrS\_YZ\_Layer}} $分别用来求$xy\_layer$, $xz\_layer$和$yz\_layer$, 由于三种求解方法是类似的, 限于篇幅, 以过程$\rm{TrS \_}$${\rm{XY\_Layer}}$求解$xy\_layer$为例展开叙述, 如算法2所示. 参数$best\_xy\_layer$和 $xy\_layer$分别代表最优$xy\_layer$和当前$xy\_layer$, 参数$xr$, $yr$和$zr$分别是剩余长方体空间的长宽高, 参数$B$表示待装入的箱子集合. ${\rm{TrS \_XY\_Layer}}$包括两个部分(以大括号分隔), 第1部分是在剩余长方体空间内填入一个最优的$x\_strip$, 第2部分是在剩余长方体空间内填入一个最优的$y\_strip$.


算法2.${\bf{TrS\_XY\_Layer}}$伪代码


$ {\bf{TrS\_XY\_Layer}}( best\_xy\_layer,xy\_layer,xr,yr,zr,B )$


image.png


${\rm{Create \_Best\_X\_Strip\_For\_XY\_Layer}}$ 和 $ {\rm{Create \_}}$${\rm{Best\_Y\_Strip\_For\_XY\_Layer}}$ 分别为 $xy\_layer$ 求解$best\_ x\_strip$和$best\_y\_strip$. 类似的, ${\rm{Create \_Best\_X\_}} $${\rm{Strip\_For\_XZ\_Layer}}$ 和 ${\rm{Create \_Best\_Z\_Strip\_For\_XZ\_}}$${\rm{Layer}} $ 分别为 $xz\_layer$ 求解 $best\_x\_strip$ 和 $ best\_$$z\_strip,$${\rm{Create \_Best\_Y\_Strip\_For\_YZ\_Layer}}{\text{ 和}}$$Create \_ $${\rm{Best\_Z\_Strip\_For\_YZ\_Layer}}$ 分别为 $yz\_layer$求解 $best\_y\_strip$ 和 $best\_ $$z\_strip$. 这6种求解过程是类似的, 仅以过程${\rm{Create \_Best\_X\_Strip\_For\_XY\_}}$$Layer $求解$best\_x\_strip$为例展开叙述, 如算法3所示. 参数$xr$, $yr$和$zr$分别是剩余长方体空间的长宽高, 参数$B$表示待装入的箱子集合. 求解之前, $best\_ $$x\_strip$的y轴向尺寸尚未确定, 可能等于某个箱子在y轴方向可能的尺寸, 这样$best\_x\_strip$的可能的y轴向尺寸数量就非常多, 为了加速算法, 我们仅取在箱子边长(该边长必须能平行y轴放置)中出现频率最大的5个尺寸, 然后针对这5个尺寸, 分别求解出5个$x\_strip$, 从中选择填充率最高的作为最终结果返回.


算法3. ${\bf{Create\_Best\_X\_Strip}}$伪代码


$ {\bf{Create\_Best\_X\_Strip\_XY\_Layer}}\left( {xr,yr,zr,B} \right)$

  $ {\text{创建空的}}x\_strip{\text{ 和 }}best\_x\_strip$

  $ {\rm{for}}\;{\rm{ each}}\;{\rm{ feasible }}\;y\_size\;{\rm{ for }}\;x\_strip$

  $ x\_strip \!=\! {\bf{Create\_X\_Strip}}\left( {xr,y\_size,zr,B} \right)$

   $ {\rm{if}}\left( {{\mathop{Fr}\nolimits} \left( {x\_strip} \right) > {\mathop{Fr}\nolimits} \left( {best\_x\_strip} \right)} \right)$

    $ best\_x\_strip{\rm\;{ = }}\;x\_strip$

  $ {\rm{return }}\;best\_x\_strip$


${\rm{Create \_X\_Strip}}$, ${\rm{Create \_Y\_Strip}}$和${\rm{Create \_Z\_Strip}}$分别用来求$x\_strip$, $y\_strip$和$z\_strip.$由于三种求解方法是类似的, 限于篇幅, 以过程${\rm{Create \_X\_Strip}}$求解$x\_strip$为例展开叙述, 如算法4所示. 参数$xr$, $yr$和$zr$分别是剩余长方体空间的长宽高, 参数$B$表示待装入的箱子集合. 求解之前, 先将$B$中所有箱子组合成$x\_piece$, 再以$xr$为背包容量, 以${{XS}} \left( {x\_piece} \right)$为物品重量, 以${{VB}} \left( {x\_piece} \right)$为物品价值, 用动态规划方法求解一维背包问题, 得到$x\_strip$并返回. 在为每一种箱子求解$x\_piece$时, 分别以箱子长宽高为$x\_piece$的x轴向尺寸, 预求解出3个备选项, 从中选择出填充率最高的, 然后去掉已经装入的箱子, 在进行新一轮的$x\_piece$生成, 直到该种箱子装完. 这里要去掉箱子过大无法在给定空间中形成$x\_piece$的情况.


算法4. ${\bf{Create\_X\_Strip}}$伪代码


$ {\bf{Create\_X\_Strip}}\left( {xr,yr,zr,B} \right)$

 $ {\text{创建空的 }}x\_piece\_list$

 $ {\rm{for}}\;{\rm{ each}}\;{\rm{box}}\;{\rm{type }}\;{b_i}\;{\rm{ and}}\;{\rm{its}}\;{\rm{number }}\;nu{m_i}\;{\rm{ in }}\;B$

  $ {\rm{while}}\left( {num > 0} \right)$

   $ x\_piece\_a = \emptyset $

   $ {\bf{TrS\_X\_Piece}}\!\left( {x\_piece\_a,{l_i},yr,zr,b,num} \right)\!$

   $ x\_piece\_b = \emptyset $

   $ {\bf{TrS\_X\_Piece}}\!\left(\! {x\_piece\_b,{w_i},yr,zr,b,num}\! \right)\!$

   $ x\_piece\_c = \emptyset $

   $ {\bf{TrS\_X\_Piece}}\!\left(\! {x\_piece\_c,{h_i},yr,zr,b,num} \right)\!$

   $ x\_piece \!=\! {\rm{the}}\;{\rm{one}}\;{\rm{with}}\;{\rm{ highest}}\;{\rm{ Fr}}\;{\rm{ among }}\;x\_$     $piece\_a, x\_piece\_b{\text{和}}x\_piece\_c $

   $ {\text{将 }}x\_piece{\text{ 加入 }}x\_piece\_list$

   $ num{\rm\;{ = }}\;num{\rm{ }} - {\rm{ }}x\_piece{\text{ 中 }}b{\text{ 的数量}}$

$ x\_strip = {\text{一维书包}}( xr\;{\rm{as}}{\text{ 背包容量}},x\_piece\_list\;$  ${\rm{as}}\;{\text{物品列表}}) $

$ {\rm{return }}\;x\_strip$


${\rm{TrS \_X\_Piece}}$、${\rm{TrS \_Y\_Piece}}$和${\rm{TrS \_Z\_Piece}}$是三个树搜索过程, 分别求解$x\_piece$、$y\_piece$和$z\_piece$. 三个过程是类似的, 限于篇幅, 仅以过程${\rm{TrS \_X\_Piece}}$求解$x\_piece$为例展开, 如图6所示. 根据算法4可知在过程${\rm{TrS \_X\_Piece}}$中箱子在x轴向尺寸已经固定, 所以此时最多考虑两种摆放方向, 分别称为方向1和方向2. 对于每个节点, 其第1个子节点是将箱子以方向1沿y轴向摆放一排; 第2个子节点是将箱子以方向1沿z轴向摆放一排; 第3个子节点是将箱子以方向2沿y轴向摆放一排; 第4个子节点是将箱子以方向2沿z轴向摆放一排. 图中的数字表示箱子是在树的第几层摆放到相应$piece$中的. 实际求解过程中, 一旦找到填充率为1的$piece$立即结束搜索, 从而加快计算速度.


6.jpg

图 6  TrS_X_piece搜索树

Fig. 6  The searching tree of TrS_X_piece


2.3   算法加速


由于MLTrS算法包含三层搜索树, 因此计算量非常大, 为了加快算法运行速度, 本文采用了以下两种加速机制.


1) 记录每一个片、条、层的创建输入和输出, 形成历史库, 在创建一个新的片、条、层之前, 首先查找历史库中有无类似记录. 如果有, 则直接复制该记录对应的输出, 从而节约大量计算时间. 以创建一个$x\_strip$为例, 假设输入中的三维空间长宽高分别为$x\_s$, $y\_s$和$z\_s$, 箱子集合为${B_i}$, 如果给定的历史库中存在一条$x\_strip$创建记录, 其输入中的三维空间长宽高分别等于$x\_s$, $y\_s$和$z\_s$, 其输入输出箱子集合分别为${B_h}$和$x\_stri{p_h}$, 如果${B_i}$是${B_h}$的子集, 且$x\_stri{p_h}$是${B_i}$的子集, 则该记录是类似记录, 此时直接以$x\_stri{p_h}$作为求解结果.


2) 树搜索${\rm{TrS \_Entity}}$在搜索最优$entity$时, 从某一节点向下搜索之前, 首先计算当前$entity$不可利用空间(即容器中所有$layer$的母长方体体积和减去容器中所有$layer$中的所有箱子体积和)占容器体积的百分比, 再用1减去该百分比得到当前树分枝可得结果的填充率上限$fr\_UB.$ 如果$fr\_UB$小于已找到的最优$entity$的填充率, 则不再沿该树分枝往下搜索, 从而减少计算时间.


2.4   对完全支撑的处理


按照第2.2节的算法流程求解出的装载方案满足摆放方向约束(C1). 为了满足完全支撑约束(C2), 需要对MLTrS算法流程进行如下调整.


1) 在创建片$(piece)$时, 仅考虑箱子体积等于最小包围长方体体积的情况, 即$piece$构成一个完整的长方体, 不存在缺角. 最小包围长方体和母长方体的区别在于: 母长方体是在$piece$创建之前给定的长方体边界, $piece$的最小包围长方体体积小于等于其母长方体体积.


2) 树搜索${\rm{TrS \_Entity}}$在搜索最优$entity$时, 仅创建$yz\_layer$和$xz\_layer$两种$layer$, 不创建$xy\_layer$, 因此${\rm{TrS \_Entity}}$在考虑完全支撑时由三叉树变成了二叉树.


3) 在创建$x\_strip$($y\_strip$)时, 以所有箱子与$x\_strip$($y\_strip$)母长方体的上表面接触面的最大正交内接长方形(不超过接触面的边界, 且各边平行于容器的水平边的面积最大的长方形, 称为$x\_strip$($y\_strip$)最大平顶长方形)面积最大为选优标准, 而不是以${{Fr}} \left( {x\_strip} \right)$(${{Fr}} \left( {y\_strip} \right)$)为选优标准. 当$x\_strip$($y\_strip$)放入相应$ xz\_$$layer$($yz\_layer$)时, 仅$x\_strip$($y\_strip$)的最大平顶长方形正上方的空间可以用于装载剩余的箱子.


4) 在创建$z\_strip$时, 除最下方的$piece$外, 其他$piece$的下表面必须与其紧下方$piece$的上表面完全接触. 在生成所有$piece$且尚未创建$z\_strip$时(不失一般性, 对所有$piece$, 令${{XS}} \left( {piece} \right) ≥\; {{YS}} \left( {piece} \right)$), 先将所有$piece$按照${{XS}} \left( {piece} \right)$值降序排列, 对于${{XS}} \left( {piece} \right)$相同的多个$piece$, 再按${{YS}} \left( {piece} \right)$值降序排列, 从而得到一个新的$piece$列表. 在利用动态规划求解一维背包时, 就可以较为容易地剔除不满足完全支撑约束的解.


3.   计算实验


本文MLTrS算法用C#语言实现, 实验程序运行计算机的CPU为Intel Xeon E5 2660@2.20 GHz, 内存为16 GB, 操作系统为64位Windows 7 Ultimate版, 实验程序仅使用CPU的8个核中的一核. 本文的测试数据集来源于文献[9], 该测试数据集包括BR1~BR15, 共15个子集, 每个子集包含100个算例, 同一子集中每个算例包含的箱子种类数相同, BR1~BR15中箱子的种类数分别为3, 5, 8, 10, 12, 15, 20, 30, 40, 50, 60, 70, 80, 90, 100, 问题由弱异构到强异构逐渐过渡, 能够很好地测试算法在不同复杂度装箱问题中的性能. 我们在用MLTrS运行算例时, 针对不同复杂度的算例给定不同的计算时间限制, 限定时间$T$的计算式为: 当仅考虑摆放方向约束(C1)时, 对于弱异构算例BR1~BR7, $T = $$ 600$, 对于强异构算例BR8~BR15, $T = 150\times\sqrt N $, 当同时考虑摆放方向约束(C1)和完全支撑约束(C2)时, 对于弱异构算例BR1~BR7, $T = 500$, 对于强异构算例BR8~BR15, $T = 100\times\sqrt N $, 其中$N$为算例的箱子种类数.


许多研究者全部或部分测试了BR1~BR15. 其中组合启发式算法(Combinational heuristics, CH)[16]、H_B(Heuristics of Bischoff)算法[22]测试了BR1~BR7; A2(Algorithm 2)算法[12]测试了BR8~BR15; GA_GB(Genetic algorithm of gehring and bortfeldt)算法[16]、贪心随机自适应搜索算法(Greedy random adaptive search procedure, GRASP)[23]、混合模拟退火算法(Hybrid simulated annealing, HSA)[21]、maximal-space算法[24]、基于整数拆分的树搜索算法(Container loading tree search, CLTRS)[7]、FDA算法(Fit degree algorithm)[11]、多层启发式搜索算法(Multiple layer heuristic algorithm, MLHS)[31]测试了BR1$\sim $BR15全部实例.


上述算法全部满足C1约束, 部分满足C2约束, 算法的计算结果直接来自于相应文献. 表1列出了这些算法与本文MLTrS算法对BR1~BR7的计算结果, 表1中所有数据表示每个算法针对一类实例所得到的平均填充率.


1.png


从表1可以看出, 针对BR1~BR7这7组弱异构算例, MLTrS无论在满足C1约束还是在同时满足C1和C2约束的前提下, 都要弱于现有基于Block building构造方式的算法, 如CLTRS[7]、MLHS[31], 从文献[32-33]和本文的算例测试结果来看, 基于Wall-building构造方式的算法对弱异构问题的求解性能弱于基于Block building构造方式的算法.


接下来观察本文算法对强异构算例的测试结果. 表2列出了各个算法对BR8~BR15的计算结果, 表2中所有数据表示每个算法针对一类实例所得到的平均填充率.


2.png


从表2可以看出, 在同时满足C1和C2约束的前提下, 当箱子种类数在60种以上时, 填充率超过了目前已知的所有算法. 在同时满足C1和C2约束的前提下, 与CLTRS[7]、MLHS[31]算法的对比如下: 当箱子种类数为70时, MLTrS填充率分别提高1.7%和0.62%; 当箱子种类数为80时, MLTrS填充率分别提高2.05%和1.04%; 当箱子种类数为90时, MLTrS填充率分别提高2.52%和1.44%; 当箱子种类数为100时, MLTrS填充率分别提高3.02%和2.05%. 另外, 针对BR8~BR15总平均值, MLTrS分别提高1.36%和0.35%. 在满足C1约束的前提下, MLTrS比CLTRS[7]提高0.73%, 略高于MLHS[31].


由此可见, 本文算法在箱子种类数大于等于70, 且要求满足摆放方向约束和完全支撑约束时, 填充率高于现有主流算法, 如CLTRS[7]、MLHS[31]等, 而且当箱子种类数越多, 本文算法求得的填充率比现有主流算法求得的填充率高得越多. 而对于箱子种类数小于70的算例, 本文算法要弱于CLTRS[7]和MLHS[31], 并且箱子种类数越少, 本文算法求得的填充率比现有主流算法求得的填充率低得越多. 这表明相对于现有主流算法, 如CLTRS[7]、MLHS[31], 本文算法更适合求解箱子种类数较多的算例, 即强异构算例.


4.   结束语


本文提出了三维装箱问题的多层树搜索算法, 采用墙构造法和水平层构造法相结合的装载方案构造方式. 该算法包括3层搜索树, 第1层搜索树也是最顶层搜索树, 用于搜索最优装载方案, 该树为三叉树, 每个树节点的三个分叉分别对应生成平行于XY面的层、生成平行于XZ面的层、生成平行于YZ面的层; 第2层搜索树用于为第1层树的每个节点搜索最优的层, 该树为二叉树, 每个树节点的两个分叉分别对应生成两个相互垂直的条; 第3层搜索树用于将每一类箱子生成片, 该树为四叉树, 由于生成片时限定空间比较小, 同类型的箱子数量相对小, 四叉树搜索速度可以接受. 本文提出的多层树搜索算法搜索量比较大, 难以在可接受时间内完成对整个搜索树的遍历, 为此采用了加速策略, 并且限定算法的运行时间. 利用通用算例的运行结果显示本文算法具有一定的竞争力. 我们在运行该算法时也发现一些问题, 例如当箱子体积相对于容器容积越小时, 树搜索深度就越深, 计算时间就越长, 有时甚至不能在限定时间内生成一个完整的装载方案, 因此本算法还有进一步改进的余地.


参考文献:

Document2.png




https://m.sciencenet.cn/blog-2374-1275886.html

上一篇:[转载]【重磅】《自动化博览》2021年第二期暨《边缘计算2021专辑》精彩来袭~
下一篇:[转载]2021湛庐年度大会落幕 青岛智能院揽获两项大奖

1 王安良

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-28 23:10

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部