计算机工程与应用2019，Vol.55Issue(5)：44-50,7.DOI:10.3778/j.issn.1002-8331.1808-0176
高效求解三维装箱问题的剩余空间最优化算法
Efficient Residual-Space-Optimization Algorithm for Three Dimensional Container Loading Problem
摘要
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分类
信息技术与安全科学引用本文复制引用
尚正阳,顾寄南,唐仕喜,孙晓红..高效求解三维装箱问题的剩余空间最优化算法[J].计算机工程与应用,2019,55(5):44-50,7.基金项目
国家自然科学基金河南省联合基金(No.U1604149) （No.U1604149）
河南省教育厅自然科学重点基金(No.19A520006,No.18A520041) （No.19A520006,No.18A520041）
河南省教育厅青年骨干教师资助项目(No.2016GGJS-158) （No.2016GGJS-158）
洛阳理工学院高层次人才资助计划(No.2017BZ07). （No.2017BZ07）
