Research On Genetic And Recursive Algorithms For Packing Problem

The bin packing problem is to put some objects with various sizes into a defined space in order to obtain the specified optimal benefit. Bin packing is a combinatorial optimization and NP-complete problem and widely applied to the mechanical manufacture and traffic transportation industries. The study of algorithm for bin packing problem is of great significance not only in theory but also in practice. Up to now, the heuristic algorithm is one of the most efficient algorithms for the packing problem because the problem is of high complexity.In this paper, we propose GA+HR algorithm, GA+IHR algorithm and GA+OIHR algorithm for 2D-packing problem. They are based on the Heuristic Recursive algorithm (HR). GA+HR algorithm is to combine genetic algorithm with global search capability with HR algorithm. It can search the better sequence to make the solution further improvement. In the GA+IHR algorithm, we define the concepts of the reference rectangle and the combined layer. We find all combined layers and calculate the solutions of each combined layers, and then find the best solution and the best combined layers from these solutions. In the GA+OIHR algorithm, we integrate the exhaustive idea into the HR algorithm, that is, the first rectangle of each layer can be placed horizontally or vertically. Calculate the space utilization of two placements and then use the placement with the greater utilization to form the layer. Furthermore, we search the rectangle whose height or width is the same as the height or width of subspace firstly. This method can reduce the number of subspace and improve the space utilization.In this paper we also develop HR and GA+HR to solve the 3D-packing problem. The computational results on well-known benchmark problems show that the running time of HR algorithm is short but the space utilization is not ideal, the running time of GA+HR algorithm is longer but the space utilization is higher than HR. Especially, the result of GA+HR can complete with Bischoff algorithm.