A Heuristics Multi-layer Search Algorithm For Three Dimensional Container Loading Problem

Container loading problem exists in a wide range of issues in the industrial field, especially for transporting and materials manufacturing. The efficiency and effectiveness of the solution to this problem has a direct impact on the costs and benefits of the industry. As the development of China's economy, the scale of industrial and commercial activities increases quickly. How to solve container loading problem will become more and more important. As a key method to increase the utilization rate of resources, packing algorithms have a great influence on making full use of transport capacity, reducing materials and saving natural resources.Although the transporting business and materials industry develop quickly, the quantity and quality of the software for container loading problem have not been greatly improved. So far, scholars have done plenty of research in this field and presented a variety of ways to solve this problem. In this paper, based on previous studies, we proposed a new packing algorithm to solve container loading problem in a more efficient way.This paper presents an efficient heuristics multi-layer search algorithm for three-dimensional container loading problem. It includes the following parts: First, we introduce the basic block-based heuristic algorithm, this algorithm loads one block, which is determined by block selecting algorithm, in one packing phase according to a fixed strategy until no blocks are available; Second, we proposed the concept of complex block, the difference between traditional block and this concept is that it can contain multiple types of objects in one block under some restrictions instead of just single type per block; Third, based on the depth-first search algorithm, we developed a multi-layer search algorithm for determining the selected block in each packing phase, and making this result as close to the optimal solution as possible. In this paper, the Bischoff and Ratcliff's 1600 test data of three-dimensional container problem are tested. The experimental results show that our heuristic multi-layer search algorithm outperforms the best known algorithm in almost all the test data.