Dynamic Programming Algorithm For The Container-Loading Of Identical Boxes

In various countries, container transport plays a very important role in transport industry, and it is difficult to be replaced by the other form of transportation. However, due to the problem of the bin-packing pattern, most of the space of container in industrial transportation cannot be fully utilized, which leads to a lower actual utilization. What’s more, the complex bin-packing pattern results in time-consuming packing process. Undertaking a study of packing algorithm to increase capacity utilization of the container and make bin-packing pattern simple has both theoretical value and practical significance.The key point of this research is the three-dimensional packing problem for same size items, which means that putting the same size rectangular objects (small boxes) into a rectangular container, making the number of small boxes to be maximum. We can convert the three-dimensional bin-packing problem to a series of two-dimensional bin-packing problems by designing a double-layer dynamic programming algorithm for three-dimensional packing:The first layer packs the slices into the container and the second layer determines the box layout of each slice. Through the analysis of the solution structure, we use the idea of the one-dimensional knapsack problem to exclude some of the states to reduce the solution space, improving the efficiency of the algorithm. In order to shorten the computation time further, we analyze the characteristics of the proposed algorithm, divide the container into groups of small cubes, and obtain the solutions of the states in the cubes of the same group by parallel computation. Furthermore, the proposed algorithm is adapted to consider the practical constraints that appear when the slices are packed from bottom to top and from right to left, making the solution operational.Experimental computation is performed to compare the proposed algorithm against published algorithms. The computational results indicate that the proposed algorithm has the following features.(1) The average solution quality is relatively high.(2) The solution is simpler than those of other algorithms.(3) The layout structure is stable, which is useful for safe transportation.(4) The parallel implementation can effectively shorten the computation time, providing guarantee for on-line packing.(5) The algorithm is adequate for practical applications because of the consideration of the constraints appearing in practical packing processes.