求解三维装箱问题的混合模拟退火算法

A Hybrid Simulated Annealing Algorithm for the Three-Dimensional Packing Problem

提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟退火算法.三维装箱问题要求装载给定箱子集合的一个子集到容器中,使得被装载的箱子总体积最大.文中介绍的混合模拟退火算法基于三个重要算法:(1)复合块生成算法,与传统算法不同的是文中提出的复合块不只包含单一种类的箱子,而是可以在一定的限制条件下包含任意种类的箱子.(2)基础启发式算法,该算法基于块装载,可以按照指定装载序列生成放置方案.(3)模拟退火算法,以复合块生成和基础启发式算法为基础,将装载序列作为可行放置方案的编码,在编码空间中采用模拟退火算法进行搜索以寻找问题的近似最优解.文中采用1500个弱异构和强异构的装箱问题数据对算法进行测试.实验结果表明,混合模拟退火算法的填充率超过了目前已知的优秀算法.

This paper presents an efficient hybrid simulated annealing algorithm for three dimensional container loading problem （3D-CLP）. The 3D-CLP is the problem of loading a subset of a given set of rectangular boxes into a rectangular container so that the stowed volume is maximized. The algorithm introduced in this paper is based on three important algorithms. First, complex block generating, complex block can contain any number boxes of different types, which differs from the traditional algorithm. Second, basic heuristic, which is a new construction heuristic algorithm used to generate a feasible packing solution from a packing sequence. Third, simulated annealing algorithm, based on the complex block and basic heuristic, it encodes a feasible packing solution as a packing sequence, and searches in the encoding space to find an approximated optimal solution. 1500 benchmark instances with weakly and strongly heterogeneous boxes are considered in this paper. The computational results show that the volume utilization of hybrid algorithm outperforms current excellent algorithms for the considered problem.