Content area
Translation from original language as provided by author
This paper addresses a typical NP-hard problem, the two-dimensional rectangular packing problem. Based on a quasi-human approach, a caving degree algorithm proposed by Huang Wenqi et al, we propose an action space based efficient algorithm, by defining the conception of action space such that the calculation of caving degree is simplified and the evaluation on different placements is reduced considerably. Therefore, the proposed algorithm not only inherits the advantages of a caving degree algorithm, but also obtains good 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, smooth degree, evaluation criteria and comparison strategies. Based on the action space, the calculation of caving degree is simplified and the evaluation on different placements is reduced considerably. This paper outlines the crucial aspects for the two-dimensional rectangular packing problem, how to split the remaining space of a rectangular sheet to make the placing item closer with other placed items, which data structure is to be used to make the remaining space update more quickly; the evaluation criteria of the corner actions should follow the sustainable lines; which search strategy is to be chosen to make the solution closer to the optimal solution and will not be trapped in the local optimal solution. Furthermore, we adapt the proposed algorithm for the two-dimensional strip packing problem and the two-dimensional rectangular packing problem for the optimization value. For the two-dimensional strip packing problem, the algorithm is combined with the plus 1 method or the dichotomy one to solve the problem whether the optimal height of the rectangular sheet is known or not. For the two-dimensional rectangular packing problem for the optimization value, we modify the comparison strategies of the placement and add the unit value of the placing item as one of the factors. And the objective is modified to calculate the total value of all the placed items. For the two-dimensional rectangular packing problem, two-dimensional strip packing problem 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 the 21 famous instances provided by Hopper and Turton, the proposed algorithm for the two-dimensional rectangular packing problem achieved optimal layout whose area utilization was 100% for each instance. For the 13 famous instances provided by Burke et al, the algorithm achieved 7 instances and the average area utilization was 99.84%. The computational results are better than the results reported in the literature. And the algorithms for the strip packing problem and the rectangular packing problem for the optimization value achieved the results which are very close to the current best results reported in the