Research On Heuristic Algorithms For The Packing Problems

Packing problem is faced in many industries, for example, the container loading, the sheet cutting, the design of VLSI and the newspaper editor. It is a NP complete problem; the research on this problem is of great significance in both theory and practice. It is high complexity if we use the general exact algorithm to solve the packing problem, so a lot of heuristic algorithms have been proposed to solve it.In this paper, we first study the 2D-packing problem. Based on the known algorithm, we present a binary search heuristic algorithm (BSHA) for the 2D strip packing problem. Firstly, by introducing the binary search algorithm, we transform the 2D strip packing problem into the 2D knapsack packing problem. Then, for the 2D knapsack packing problem, we present a least wasted first strategy based on the way of finding positions to pack rectangles and introduce the conception of "the wasted area" and "variable flat point" to evaluate a pack. Lastly, a random local search is introduced to improve the results. The computational results on several classes of benchmark problems have shown that BSHA can find better solution than other known algorithms, such as GRASP, SPGAL, HRBB, especially, BSHA can find an optimal solution for many instances in short time.For the 3D-packing problem, we present a combinational heuristic algorithm. Firstly, we develop a personification heuristics, which is inspired by the strategy of building wall in the daily life. Similar to the personification heuristics for the 2D-packing problem, we introduce the "reference box" and the "reference line" to guide the process of packing. Lastly, a simulated annealing algorithm is further used to improve the personification heuristics. Computational results on benchmark instances show the algorithm can compete with excellent heuristics from the literatures.