ANALYSIS OF PARAMETERS OF GENETIC ALGORITHM FOR SOLVING TWO-DIMENSIONAL PACKING PROBLEM
DOI:
https://doi.org/10.35546/kntu2078-4481.2025.2.2.6Keywords:
two-dimensional packing problem, genetic algorithm, genetic operators, optimizationAbstract
The task of packaging is a topical one and is encountered in many industrial productions. It belongs to the class of NP-hard problems, so the use of an exact enumeration algorithm is possible only for small-dimensional problems.Metaheuristic methods are a popular tool for the approximate solution of complex combinatorial optimization problems.The article considers solving the problem of packing rectangles into a semi-infinite strip of fixed width using a genetic algorithm. The purpose of the article is to study the influence of genetic operators of crossover and selection on the efficiency of the algorithm. The paper provides a statement of the problem, presents the genetic operators of crossover and selection used in the algorithm. The solution of the packing problem is divided into two steps: determining the permutation for the packing sequence of rectangular elements using a genetic algorithm, and applying a decoding algorithm to place them in the strip. The BLF algorithm was used as a decoder. A computational experiment was carried out on test examples known from literary sources, as well as on two generated sets of rectangles. All test problems used in this study have an optimal solution with the minimum admissible length of the occupied part of the strip. The program is implemented using the Python programming language and the Deap package. Analysis of the experimental results showed that the best solutions to the problem of packing rectangles into a semi-infinite strip were obtained when using the PMX crossover operator and the tournament selection operator in the genetic algorithm. The genetic algorithm showed the worst result when using the UPMX crossover operator and roulette selection.
References
Iori M., de Lima V. L., Martello S., Miyazawa F., Monaci M. Exact Solution Techniques for Two-dimensional Cutting and Packing. European Journal of Operational Research. 2020. Vol. 289(2). P. 399–415. DOI: 10.1016/j.ejor.2020.06.050
Lodi A., Martello S., Monaci M. Two-dimensional Packing Problems: A survey. European Journal of Operational Research. 2002. Vol. 141(2). P. 241–252. https://doi.org/10.1016/S0377-2217(02)00123-6
Iori M., Martello S., Monaci M. Metaheuristic Algorithms for the Strip Packing Problem. Optimization and Industry: New Frontiers. Applied Optimization. 2003. Vol. 78. P. 159–179. DOI:10.1007/978-1-4613-0233-9_7
Jakobs S. On genetic algorithms for the packing of polygons. European Journal of Operational Research. 1996. Vol. 88(1). P. 165–181. https://doi.org/10.1016/0377-2217(94)00166-9
Hopper E., Turton B. C. H. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. European Journal of Operational Research. 2001. Vol. 128(1). P. 34–57. DOI:10.1016/S0377-2217(99)00357-4
Baker B. S., Coffman E. G., Rivest R. L. Orthogonal packings in two dimensions. SIAM Journal on Computing. 1980. Vol. 9(4). P. 846–855. DOI:10.1137/0209064
Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. European Journal of Operational Research. 1999. Vol. 112(2). P. 413–420. https://doi.org/10.1016/S0377-2217(97)00437-2
Chazelle B. J. The bottom-left bin-packing heuristic: an efficient implementation. IEEE Transactions on Computers. 1983. Vol. 32, No.8. P. 697–707. https://doi.org/10.1109/TC.1983.1676307
Michalewiсz Z. Genetic Algorithms + Data Structures = Evolution Programs. Berlin: Springer-Verlag. 1992. 388 p.
Cicirello V. A. A Survey and Analysis of Evolutionary Operators for Permutations. Proceedings of the 15th International Joint Conference on Computational Intelligence ECTA. 2023. Vol. 1. P. 288–299. DOI:10.5220/0012204900003595
