高效求解三维装箱问题的剩余空间最优化算法

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

Efficient Residual-Space-Optimization Algorithm for Three Dimensional Container Loading Problem

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.