三维装箱问题的智能启发式算法

An Intelligent Heuristic Approach to Three-Dimensional Bin-packing Problem

三维装箱问题是一类典型的NP-hard组合优化问题,找到一个高效快速的算法具有重要的现实意义.模拟人们在实际装箱时总是尽量保证每一层装的比较"平直"思想,设计了一种智能启发式算法,借以克服一般启发式算法依赖"经验"的不足.给出了详细算法流程和关键数组的定义.该算法结构简单,实验表明算法收敛速度快,能有效解决三维装箱问题.

The three-dimensional bin-packing problem is very hard to solve but there is a high level of interest in developing an effective way to solve this it in order to reduce the time, energy and other resources spent in bin packing. This paper develops a powerful intelligent approach to its solution, imitating human intelligence to pack bins straight and flat as far as possible. This approach is of simple structure and overcomes the deficiency in general heuristic algorithms depending on private experience. The paper also provides a detailed algorithm process and key definitions of the array. Tests on such problems show that our approach makes the most of volume utilization.