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

来源：计算机工程与应用杂志2019年第5期北京时间：

作者：尚正阳1，顾寄南2，唐仕喜2，孙晓红2

单位：1.安徽工程大学 机械与汽车工程学院，安徽 芜湖 241000；2.江苏大学 制造业信息化研究中心，江苏 镇江 212000

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

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