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

doi:10.3778/j.issn.1002-8331.1808-0176

计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (5): 44-50.DOI: 10.3778/j.issn.1002-8331.1808-0176

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

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

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

出版日期:2019-03-01 发布日期:2019-03-06

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

SHANG Zhengyang1, GU Jinan2, TANG Shixi2, SUN Xiaohong2

1.School of Mechanical and Automotive Engineering, Anhui Polytechnic University, Wuhu, Anhui 241000, China
2.Mechanical Information Research Center, Jiangsu University, Zhenjiang, Jiangsu 212000, China

Online:2019-03-01 Published:2019-03-06

摘要/Abstract

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

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

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

尚正阳1，顾寄南2，唐仕喜2，孙晓红2. 高效求解三维装箱问题的剩余空间最优化算法[J]. 计算机工程与应用, 2019, 55(5): 44-50.

SHANG Zhengyang1, GU Jinan2, TANG Shixi2, SUN Xiaohong2. Efficient Residual-Space-Optimization Algorithm for Three Dimensional Container Loading Problem[J]. Computer Engineering and Applications, 2019, 55(5): 44-50.

[1]	张呈玲，李进金，林艺东. 基于OE-概念格的形式背景属性约简[J]. 计算机工程与应用, 2021, 57(15): 82-89.
[2]	孟鑫，杨琴，郝婷婷，张洁，曹策俊. 不同订单分配和算法下的拣货路径优化组合[J]. 计算机工程与应用, 2020, 56(23): 229-236.
[3]	李雅丽，王淑琴，陈倩茹，王小钢. 若干新型群智能优化算法的对比研究[J]. 计算机工程与应用, 2020, 56(22): 1-12.
[4]	易成岐，郭鑫，童楠楠，窦悦，陈东，王建冬. 基于启发式社团发现模型的创新态势研判算法[J]. 计算机工程与应用, 2020, 56(15): 74-79.
[5]	胡晓敏，梁天毅，王明丰，李敏. 新型树启发式搜索算法的机器人路径规划[J]. 计算机工程与应用, 2020, 56(11): 164-171.
[6]	迟宗正，董绍正，郭童，任志磊，周宽久，郭禾. 求解风力发电机布局问题的超启发式算法研究[J]. 计算机工程与应用, 2019, 55(7): 220-225.
[7]	侯屿1，2，秦小林2，彭皓月1，2，张力戈1，2. 全局调距和声特征选择算法[J]. 计算机工程与应用, 2019, 55(2): 21-27.
[8]	陈桂兰，奚宝华，杨兰英. 改进混合粒子群算法的立体车库存取调度[J]. 计算机工程与应用, 2019, 55(19): 263-270.
[9]	张钧，贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39.
[10]	刘竹松，李生. 正余混沌双弦鲸鱼优化算法[J]. 计算机工程与应用, 2018, 54(7): 159-163.
[11]	王长宝1，杨习贝1，2，窦慧莉1，陈向坚1，王平心3. 邻域决策错误率的局部约简方法研究[J]. 计算机工程与应用, 2018, 54(6): 95-99.
[12]	吴伟民，李泽熊，林志毅，吴汪洋，方典禹. 飞蛾纵横交叉混沌捕焰优化算法[J]. 计算机工程与应用, 2018, 54(3): 136-141.
[13]	王转，裴泽平. 启发式路径下节约里程的订单分批算法[J]. 计算机工程与应用, 2018, 54(23): 203-209.
[14]	徐雪松1，徐歆尧2. 一种多结构数据的同步拟合方法[J]. 计算机工程与应用, 2017, 53(6): 73-79.
[15]	王严欣，崔耀东，李华. 应用精确两阶段排样图的板材下料算法[J]. 计算机工程与应用, 2017, 53(5): 236-240.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics