Solving the packing problem of rectangles with improved genetic algorithm based on statistical analysis

ABSTRACT

The genetic algorithm and the surplus rectangle algorithm are used for solving the orthogonal packing problem of rectangles. Based on statistical analysis of rectangular packing problem, a comparable standard for judgment of a solution has been proposed, which is adopted in classification of the parent population. A surplus rectangle algorithm is introduced to decode the permutation of rectangles to the corresponding packing pattern uniquely. For different constructions, corresponding genetic operations have been designed. And then an improved genetic algorithm has been constructed. Several rectangles packing problems have been solved by using this improved algorithm and the optimum packing results have been achieved. This shows that the improved genetic algorithm is efficacious.

REFERENCES

• 1: Stefan Jakobs. 1996. Theory and Methodology on genetic algorithms for the packing of polygons. European Journal of Operational Research 88, 165--181.
• 2: Patrick Healy. 1999. An optimal algorithm for rectangle placement. Operation Research Letters 24, 73 -- 80.
• 3: Liu Dequan and Teng Hongfei. 1991. On genetic algorithm for the orthogonal packing of rectangles. Mini-Micro Systems 19 (21), 20--25.
• 4: LI Manjiang, Meng Xiangxu and Wang Zhiqiang. 2002. Algorithm and application of rectangular and polygonal packing problem. Journal of Guizhou University of Technology (Natural Science Edition) 31 (4), 126 -- 130.
• 5: Xing Wenxun and Xie Jinxing. 1990. Modern Optimization Computing Method. Tsinghua University Press, Beijing, 129 -- 136.
• 6: Han Xijun, Ding Genhong. 2006. The Optimum Packing of Rectangles Based on Improved Genetic Algorithm. Computer Engineering and Applications 25 (42), 63 -- 65, 68.
• 7: Fogel D B. 1994. An introduction to simulated evolutionary optimization. IEEE Trans. on Neural Networks 5 (1), 3 -- 14.
• 8: Hopper E, Turton B C H. 2001. An empirical investigation of metaheuristic and heuristic algorithm for a 2D packing problem. European Journal of Operational Research 128 (1), 34--57.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout; Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms; Permutations and combinations

General Terms:
Algorithms, Theory

Keywords:
genetic algorithm, orthogonal packing, packing pattern, statistical analysis, surplus rectangle