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

Quick Algorithm for the Three-dimensional Bin Packing Problem with Support Surface Constraints

针对三维装箱(3D-BP)问题,已有的算法大都没有考虑货物支撑限制问题.本文提出一种基于带支撑面装载空间的算法来解决这一问题,并提出了判断两个立方体是否有空间重叠、以及装载空间更新的算法.算例测试中,对不同装载策略和货物排序方法的结果进行比较,并针对货物能否转向进行计算;选择最优的策略分别计算装载系数为0.6、0.75、0.9、1时所对应的装载效果,同时还给出了在考虑货物易碎性约束时的结果.实验表明,相比关键点思想,本文提出的带支撑面的装载空间的概念,计算结果的质量更高、求解速度更快,对实际应用及后续的研究有较好的借鉴意义.

Dealing with the three-dimensional bin packing problem （3D-BP）,most of the existing algorithms ignore the support constraint.A loading space with support surface is presented to solve 3D-BP with support constraint,and a method is proposed to decide whether or not the overlapping exists between two boxes and the algorithm to update the loading space.Computational efforts between different loading strategies and sorting methods are compared,according to whether goods can be rotated or not.The loading effect corresponding to different loading coefficient,0.6,0.75,0.9 and 1.0,respectively,are computed by the optimal strategy.Finally,the optimization result considering fragility is given.The experiment demonstrates that the loading space with support surface is superior to key point strategy,which has great significance for practical application and further research.