Abstract: A Three-Dimensional Residual-Space-Optimized algorithm（3D-RSO） is proposed to efficiently solve 3D container loading problems. Under the condition of satisfying three famous constraints, 3D-RSO transforms a 3D problem into a 2D problem with height constraint. Through state analysis of the remaining space, it puts forward a probability-based spatial segmentation method and box layout rule respectively. Compared with traditional algorithms, 3D-RSO doesn’t need any preprocessing or searching operation during the solving process, and is a direct solving algorithm with the worst computational complexity [O(2n2)]. Experiments on strongly heterogeneous data-sets show 3D-RSO can efficiently solve 3D packing problem within very short time. Thus, this heuristic is suitable for some cases that are at large scale or should be solved quickly.

Key words: three-dimensional container loading problem, heuristic algorithm, fast solving algorithm, scheduling optimization

摘要： 为实现三维装箱问题的高效求解，提出了一个三维的剩余空间最优化算法（Three-Dimensional Residual-Space-Optimized Algorithm，3D-RSO）。在满足3个著名约束的条件下，该算法将三维问题转化为带有高度约束的二维问题，通过对箱子放置后的剩余空间状态分析，提出了基于概率较优的空间分割方法和箱子布置规则。相比于传统算法，3D-RSO在求解过程中不需要任何的预处理和搜索操作，是一种最坏计算复杂度为[O(2n2)]的直接求解算法。针对强异构体的实验表明，该算法能够在极短的时间内对算例进行高效求解，适合应用在大规模或者需要被快速求解的三维装箱问题中。

关键词: 三维装箱问题, 启发式算法, 快速求解, 调度优化