Efficient Heuristic Algorithms For The Two-dimensional Rectangular Packing Problem

This paper addresses a typical NP-hard problem, the two-dimensional rectangularpacking problem. Based on a quasi-human approach, a caving degree algorithm proposedby Huang Wenqi et al, we propose an action space based efficient algorithm, by definingthe conception of action space such that the calculation of caving degree is simplified andthe evaluation on different placements is reduced considerably. Therefore, the proposedalgorithm not only inherits the advantages of a caving degree algorithm, but also obtainsgood layouts in a short time.This paper focuses on researching the two-dimensional rectangular packing problem,and gives six important definitions, namely iteration, action space, corner action, smoothdegree, evaluation criteria and comparison strategies. Based on the action space, thecalculation of caving degree is simplified and the evaluation on different placements isreduced considerably. This paper outlines the crucial aspects for the two-dimensionalrectangular packing problem, how to split the remaining space of a rectangular sheet tomake the placing item closer with other placed items, which data structure is to be used tomake the remaining space update more quickly; the evaluation criteria of the corneractions should follow the sustainable lines; which search strategy is to be chosen to makethe solution closer to the optimal solution and will not be trapped in the local optimalsolution.Furthermore, we adapt the proposed algorithm for the two-dimensional strip packingproblem and the two-dimensional rectangular packing problem for the optimization value.For the two-dimensional strip packing problem, the algorithm is combined with the plus1method or the dichotomy one to solve the problem whether the optimal height of therectangular sheet is known or not. For the two-dimensional rectangular packing problemfor the optimization value, we modify the comparison strategies of the placement and addthe unit value of the placing item as one of the factors. And the objective is modified tocalculate the total value of all the placed items.For the two-dimensional rectangular packing problem, two-dimensional strip packingproblem and the two-dimensional rectangular packing problem for the optimization value,we tested the proposed algorithms on the famous international benchmarks. These algorithms could obtain good results in a short time. Especially when we tested the21famous instances provided by Hopper and Turton, the proposed algorithm for thetwo-dimensional rectangular packing problem achieved optimal layout whose areautilization was100%for each instance. For the13famous instances provided by Burke etal, the algorithm achieved7instances and the average area utilization was99.84%. Thecomputational results are better than the results reported in the literature. And thealgorithms for the strip packing problem and the rectangular packing problem for theoptimization value achieved the results which are very close to the current best resultsreported in the literature.