A new iterative-doubling Greedy-Lookahead algorithm for the single container loading problem
A new iterative-doubling Greedy-Lookahead algorithm for the single container loading problem
复制标题
DOI：
10.1016/j.ejor.2012.04.036
复制
发表时间：
2012-11
期刊：
影响因子：
--
通讯作者：
Wenbin Zhu;A. Lim
中科院分区：
文献类型：
--
作者：
Wenbin Zhu;A. Lim
单集装箱装载问题（SCLP）的目标是将三维盒子装入三维集装箱中，从而最大化集装箱的体积利用率。我们提出了一种新的块构建方法，通过一次放置一个（盒子）块来构建包装，直到无法装载更多盒子为止。获得高质量解决方案的关键是选择正确的块放置到容器中正确的自由空间长方体（或剩余空间）中。我们提出了一种新的启发式方法来评估残差空间的适应性，并使用树搜索来决定每一步的最佳残差空间块对。即使计算资源较少，所得算法的性能也优于基于 1600 个常用基准实例的最著名算法。我们还调整了我们的方法来解决全力支持的限制。 1600 个实例上的完全支持支持变体的计算结果同样显示出相对于现有技术的显着改进，即使在提供的计算资源少得多的情况下也是如此。
The aim of the Single Container Loading Problem (SCLP) is to pack three-dimensional boxes into a three-dimensional container so as to maximize the volume utilization of the container. We propose a new block building approach that constructs packings by placing one block (of boxes) at a time until no more boxes can be loaded. The key to obtaining high quality solutions is to select the right block to place into the right free space cuboid (or residual space) in the container. We propose a new heuristic for evaluating the fitness of residual spaces, and use a tree search to decide the best residual space-block pair at each step. The resultant algorithm outperforms the best known algorithms based on the 1600 commonly used benchmark instances even when given fewer computational resources. We also adapted our approach to address the full support constraint. The computational results for the full support support variant on the 1600 instances similarly show a significant improvement over existing techniques even when given substantially fewer computational resources.