基于启发式拟人算法的三维装箱问题求解

摘要

三维装箱问题是一个NP完全组合优化问题.根据三维装箱问题的特点,在研究三维装箱问题的约束条件的基础上,提出一种基于模拟人工装载的启发式算法,采用三维分割来处理装箱空间结构,利用递归方法提高层中空间的利用率,采用人工智能方法处理待装物体得出装箱结果,实验结果表明,该算法是行之有效的,并具有一定的通用性.%The 3D packing problem is a complete NP combinational optimization problem. According to the characteristic of the problem and on the basis of an investigation of the constraints in 3D packing, we proposed a heuristic algorithm based on simulated manual loading and adopted the 3D cutting method to process the spatial structure of the cartons, the recursive method to improve the utility rate of the space between layers and the artificial intelligent method to obtain the final packing plan. The result of the experiment showed that such algorithm was effective in solving this problem and was of some generality.